You can't. Either add a pointer to parent to your structure, or write your recursion in a way that passes node and parent on each level, so you can pass the parent as a second parameter to your rotate functions.
AVL Tree Deletion using Recursion
-
19-06-2023 - |
Question
Let x = the node to be deleted
How can I reassign the left or right pointer of x's parent to x's left or right sub tree during rotation without a parent pointer in node's struct declaration using recursion in an AVL Tree Implementation coded in C?
My Node's struct declaration:
typedef struct Node{
int key;
struct Node *left;
struct Node *right;
int height;
}node;
Currently, these are my rotation codes:
void rotateRight(node **n){
node *lChild = (*n)->left;
node *subtree = lChild->right;
// Rotate Right
lChild->right = *n;
(*n)->left = subtree;
*n = lChild;
// Update Height
lChild->right->height = max(getHeight(lChild->right->left), getHeight(lChild->right->right)) + 1;
(*n)->height = max(getHeight((*n)->left), getHeight((*n)->right)) + 1;
}
void rotateLeft(node **n){
node *rChild = (*n)->right;
node *subtree = rChild->left;
// Rotate Left
rChild->left = *n;
(*n)->right = subtree;
*n = rChild;
// Update Height
rChild->left->height = max(getHeight(rChild->left->left), getHeight(rChild->left->right)) + 1;
(*n)->height = max(getHeight((*n)->left), getHeight((*n)->right)) + 1;
}
When I execute these rotation codes, I lose some elements that should have not been deleted.
Solution
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow