For AVL tree, write C functions to rotate-right, rotate-left,insert and delete, to
check if a BST is a AVL tree.
Solution
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left),height(y->right))+1;
x->height = max(height(x->left),height(x->right))+1;
// Return new root
return x;
}
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left),height(x->right))+1;
y->height = max(height(y->left),height(y->right))+1;
// Return new root
return y;
}
struct Node* insert(struct Node* node, int key)
{
/* 1. Perform the normal BST insertion */
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else if