Lesson 13 AVL Tree, 2-3-4 Tree, Red-Black Tree

AVL Tree

Review

• AVL Tree: BST
• RR rotate AVL tree:
  
  An anti-clock rotation

Another special case of AVL tree

simple version

RL case

2 rotations

general version

• 1. After insertion in , root A,B,C become unblanced:

• 1. Rotate C, B

• 1. rotate A, C, return to balance

After insertion, the height of the tree maintain

Summarize

• RR, LL: one rotation
• RL, LR: two rotations

Removal

Similar to insertion, rotate while needed.
When remove the root, pick up a leaf

2-3-4 Tree

AVL tree: rebalance “almost” immediately
2-3-4 tree: temp storage
2-3-4:three types of child node: 2- node, 3-node, 4-node

2-4 tree

• flexible: 2-node, 3-node, 4-node
• strict(compare to BST): all leaves same height

While insertion, extend root to maintain the two limits

When insert 13: overflow How to divide?

Do this operation recursively until the 2-3-4 tree sable

Red-Black Tree

2-3-4 tree to red-black tree

Sequential insert data to the 234 tree:

• 1. insert 1,2,3,
     
• 1. When 4 is inserted, 2 go to the upper layer
     
• 1. Continue to insert 5,6,7,8,9
     
• 1. When insert 10
     

Then, we turn the 2-3-4 tree to a binary search tree:
Let suqre for 2-3-4 node, circle for BST node:

An example for 2-3-4 tree transformed to red-black tree

2-3-4 tree:

one type of RBT:

Insertion for red-black tree

• insert 1.5

just insert a red node after node1

• insert 4.5

just insert a red node after node 4

• insert 1.8

if we just add node 1.8 after node 1.5
This is illegal, we change it like the AVL tree’s rotation:


We summarize into two sentences:
新生先为红
红父不能容

We focus on the two types of insertion seperately:

• 1. new node inserted to a 3-node

黑叔逼爷退

• 1. new node inserted to a 4-node
  • Firstly,the node just inserted to the 4-node:
    
  • Secondly, we split the two sides’ nodes
    
  • Finaly, we change the root’s colour to red and insert it up(recursively until satisfy the RBT rule)
    
    红叔变色龙