• Height - Balanced BST
• BST properties
• Balance Factor of node x: bf(x) = height(left(x)) - height(right(x)) *height(leaf)=0, height(empty)=-1 AVL property: -1 < bf(x) < 1 for every node x
• Insert, delete
  1. Use BST
  2. Check AVL property
• AVL Violations→Rotate Tree when bf≠-1,0,1 Set Pivot node = deepest unbalanced node from root
• Then rotate tree at Pivot

  1. LL(Pivot = a)

     

  2. RR(pivot = a)

     

  3. LR=RR+LL(pivot= b → a)

     

  4. RL=LL+RR(pivot = c → a)

     

2-3 Tree

• 2 or 3 children

• perfectly height balanced

  • internal nodes: store 1 or 2 key values
  • leaf nodes: store (key, info)
  • h level →2^(h-1) ~ 3^(h-1) leaves

• Search tree

  • Left ≤ first < middle < second ≤right

    

• Insertion, Deletion Since children should be 2 or 3, insertion may cause overflow → split nodes [→increase height] and deletion cause underflow → use spare / delete node [→decrease height]

• root has at least 2 children

• internal node: [m/2]children

• leaves at same level

• Insert, delete, search: O(log(n))

  

• actual records are only in leaves
• each leaf: [m/2]~m records

• each node: 2/3 full

• B Tree Easy Update, Faster search More space, complex implementation