An AVL tree is a self-balancing Binary Search Tree (BST) where the difference between the heights of left and right subtrees cannot be more than one for all nodes. Please complete the leftRotate, rightRotate and insert functions of AVL tree data structure.
#include<iostream>
using namespace std;
class Node
{
public:
int key;
Node *left;
Node *right;
int height;
};
int max(int a, int b){
return (a > b)? a : b;
}
int height(Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
int getBalance(Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
Node* newNode(int key)
{
Node* node = new Node();
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
}
Node *rightRotate(Node *y)
{
}
Node *leftRotate(Node *x)
{
}
Node* insert(Node* node, int key)
{
}
void preOrder(Node *root)
{
if(root != NULL)
{
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}
int main()
{
Node *root = NULL;
int n, key;
cin >> n;
for(int i =0 ;i<n ;i++){
cin >> key;
root = insert(root, key);
}
preOrder(root);
cout << endl;
return 0;
}
The first line of input is total number of the keys.
The second line of input is consist of a sequence of number. Every number is a new key being inserted to the AVL tree.
The output is the sequence of number that represents the preorder traversal of the constructed AVL tree.