Question

(C++) Funtion code only

AVL Trees

1) Determine if a tree is an AVL tree

2) Characteristics of an AVL tree

3) Algorithm for balancing in all situations

4) Big O

Answer 1

1. Checking if a given binary tree is an AVL tree or not.

#include <bits/stdc++.h>
using namespace std;
class nod { //node declaration
   public:
   int data;
   nod* l;
   nod* r;
};
nod* newNod(int d) { //creation of new node
   nod* Nod = new nod();
   Nod->data = d;
   Nod->l = NULL;
   Nod->r = NULL;
   return(Nod);
}
int max(int x, int y) { //return maximum between two values
   return (x >= y)? x: y;
}
int height(nod* node) { //get the height means the number of nodes along the longest path from the root
//node down to the farthest leaf node of the tree. 
   if(node == NULL)
      return 0;
   return 1 + max(height(node->l), height(node->r));
}
bool AVL(nod *root) {
   int lh;
   int rh;
   if(root == NULL)
      return 1;
   lh = height(root->l); // left height
   rh = height(root->r); // right height
   if(abs(lh-rh) <= 1 && AVL(root->l) && AVL(root->r)) return 1;
   return 0;
}
int main() {
   //take the nodes of the tree as input
   nod *root = newNod(7);
   root->l = newNod(6);
   root->r = newNod(12);
   root->l->l = newNod(4);
   root->l->r = newNod(5);
   root->r->r = newNod(13);
   if(AVL(root))
      cout << "The Tree is AVL Tree"<<endl;
   else
      cout << "The Tree is not AVL Tree "<<endl;
   nod *root1 = newNod(7);
   root1->l = newNod(6);
   root1->r = newNod(12);
   root1->l->l = newNod(4);
   root1->l->r = newNod(5);
   root1->r->r = newNod(13);
   root1->r->r->r = newNod(26);
   if(AVL(root1))
      cout << "The Tree is AVL Tree"<<endl;
   else
      cout << "The Tree is not AVL Tree "<<endl;
   return 0;
}

OUTPUT

The Tree is AVL Tree

The Tree is not AVL Tree

____________________________________________________________________________________________

2.Characteristics of an AVL Tree

1. AVL Trees are self balancing binary search trees.

2. Balancing factor of each node is either 0 or 1 or -1 .

3. AVL tree balances itself through the following rotation techniques :

i) Left Rotation

ii) Right Rotation

iii) Left-Right Rotation

iv) Right-Left Rotation

____________________________________________________________________________________________

3.Algorithm for balancing in all situations (in C++)

#include<bits/stdc++.h> 
using namespace std; 

// An AVL tree node 
class Node 
{ 
        public: 
        int key; 
        Node *left; 
        Node *right; 
        int height; 
}; 

// A utility function to get maximum 
// of two integers 
int max(int a, int b); 

// A utility function to get the 
// height of the tree 
int height(Node *N) 
{ 
        if (N == NULL) 
                return 0; 
        return N->height; 
} 

// A utility function to get maximum 
// of two integers 
int max(int a, int b) 
{ 
        return (a > b)? a : b; 
} 

/* Helper function that allocates a 
new node with the given key and 
NULL left and right pointers. */
Node* newNode(int key) 
{ 
        Node* node = new Node(); 
        node->key = key; 
        node->left = NULL; 
        node->right = NULL; 
        node->height = 1; // new node is initially 
                                        // added at leaf 
        return(node); 
} 

// A utility function to right 
// rotate subtree rooted with y 
// See the diagram given above. 
Node *rightRotate(Node *y) 
{ 
        Node *x = y->left; 
        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; 
} 

// A utility function to left 
// rotate subtree rooted with x 
// See the diagram given above. 
Node *leftRotate(Node *x) 
{ 
        Node *y = x->right; 
        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; 
} 

// Get Balance factor of node N 
int getBalance(Node *N) 
{ 
        if (N == NULL) 
                return 0; 
        return height(N->left) - height(N->right); 
} 

// Recursive function to insert a key 
// in the subtree rooted with node and 
// returns the new root of the subtree. 
Node* insert(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 (key > node->key) 
                node->right = insert(node->right, key); 
        else // Equal keys are not allowed in BST 
                return node; 

        /* 2. Update height of this ancestor node */
        node->height = 1 + max(height(node->left), 
                                                height(node->right)); 

        /* 3. Get the balance factor of this ancestor 
                node to check whether this node became 
                unbalanced */
        int balance = getBalance(node); 

        // If this node becomes unbalanced, then 
        // there are 4 cases 

        // Left Left Case 
        if (balance > 1 && key < node->left->key) 
                return rightRotate(node); 

        // Right Right Case 
        if (balance < -1 && key > node->right->key) 
                return leftRotate(node); 

        // Left Right Case 
        if (balance > 1 && key > node->left->key) 
        { 
                node->left = leftRotate(node->left); 
                return rightRotate(node); 
        } 

        // Right Left Case 
        if (balance < -1 && key < node->right->key) 
        { 
                node->right = rightRotate(node->right); 
                return leftRotate(node); 
        } 

        /* return the (unchanged) node pointer */
        return node; 
} 

// A utility function to print preorder 
// traversal of the tree. 
// The function also prints height 
// of every node 
void preOrder(Node *root) 
{ 
        if(root != NULL) 
        { 
                cout << root->key << " "; 
                preOrder(root->left); 
                preOrder(root->right); 
        } 
} 

// Driver Code 
int main() 
{ 
        Node *root = NULL; 
        
        /* Constructing tree given in 
        the above figure */
        root = insert(root, 10); 
        root = insert(root, 20); 
        root = insert(root, 30); 
        root = insert(root, 40); 
        root = insert(root, 50); 
        root = insert(root, 25); 
        
        /* The constructed AVL Tree would be 
                                30 
                        / \ 
                        20 40 
                        / \ \ 
                10 25 50 
        */
        cout << "Preorder traversal of the "
                        "constructed AVL tree is \n"; 
        preOrder(root); 
        
        return 0; 
} 

OUTPUT Preorder traversal of the constructed AVL tree is 30 20 10 25 40 50

___________________________________________________________________________________________

4.Big O

Time complexity

Because of Balancing property , the insertion , deletion and search operations take O(logn) in both the average and the worst cases.

Space Complexity

O(n) in both the average and the worst case.