Raw AVL, C++ (gcc)

Raw AVL

//g++  7.4.0

#include <iostream>

int main()
{
    std::cout << "Hello, world!\n";
}

1 2 3 4 5 6

1 
 2
  3
   4 
    5
     6
     
     3
    2 5
   1   6
   
      _
   x     x
   [abs(L_SZ - R_SZ) <= 2] --> Almost equal
   
        N
    N/2   N/2
   N/4   N/4
  N/8  N/8
 N/16 ..

N/2^x = 1
     
O(N)

O(logN)

[T] X [T+2]
     Y     X1
   Z   Y1   \\\\

Y
     Z   X
        y1 X1

[T+2] X [T]
      Y.  Z
         Z1 Z2

Z
      X    Z2
    Y  Z1

Balance factor = (lft_size - rgt_size)

[T+2]   X  [T] -> [2]
        
 [1] Y      Z  -> [-1]
 
  Y1 Y2.  Z1 Z2

Y [0]
  [T]Y1       X [0] [T]
        [T-1]Y2  Z (-1) [T-1]
             ....

=============================================

[T+2]   X  [T] -> [2]
        
 [-1]Y      Z  -> [1]
 
  Y1 Y2.  Z1 Z2

Y [-2]
  [T-1]Y1       X [1] [T+1]
          [T]Y2  Z (+1) [T-1]
             ....
             
            
            
1. Balance factor
2. Not almost eq node
3. Decide where to rotate (depend which is heavier)
4. Compre the sign of the node which is going to be new root with the current root's balance factor
    - Make the sign same with appropraite rotation
5. Do the rotation

struct node {
    node *lft, *rgt;
    int val;
    
    int bal;
    int hei;
    
    node(int v) : val(v), lft(NULL), rgt(NULL), bal(0), hei(1) {}
};

int height (node* root) {
    if (!root) return 0;
    
    int lft = root -> lft ? root -> lft -> hei : 0;
    int rgt = root -> rgt ? root -> rgt -> hei : 0;
    
    return (max(lft, rgt) + 1);
}

/*
  [T+2] X [T]
      Y.  Z
         Z1 Z2

Z
      X    Z2
    Y  Z1
*/
node* lft_rotate(node* root) {
    node* new_root = root -> rgt;
    
    root -> rgt = new_root -> lft;
    new_root -> lft = root;
    
    compute (root);
    compute (new_root);
    
    return new_root;
}

[T] X [T+2]
     Y     X1
   Z   Y1   \\\\

Y
     Z   X
        y1 X1

*/
node* rgt_rotate(node* root) {
    node* new_root = root -> lft;
    
    root -> lft = new_root -> rgt;
    new_root -> rgt = root;
    
    compute (root);
    compute (new_root);
    
    return new_root;
}

node* compute (node* root) {
    root -> hei = height(root);
    
    int lft_hei = height(root -> lft);
    int rgt_hei = height(root -> rgt);
    root -> bal = lft_hei - rgt_hei;
    
    return root;
}

/*
4. Compre the sign of the node which is going to be new root with the current root's balance factor
    - Make the sign same with appropraite rotation
5. Do the rotation
*/
node* balance(node* root) {
    if (abs(root -> bal) <= 1) return root;
    
    if (root -> bal == 2) {
        if (root -> lft -> bal == -1) root -> lft = lft_rotate(root -> lft);
        return rgt_rotate(root);
    }
    else {
        // -2
        if (root -> rgt -> bal == 1) root -> rgt = rgt_rotate(root -> rgt);
        return lft_rotate(root);
    }
}

node* insert(node* root, int new_val) {
    if (!root) {
        return new node(new_val);
    }
    
    if (root -> val < new_val) {
        root -> rgt = insert (root -> rgt, new_val);
    }
    else {
        root -> lft = insert (root -> lft, new_val);
    }
    
    compute (root);
    
    return balance(root);
}


run \| edit \| history \| help	0

Please log in to post a comment.