Balanced Binary Search Tree

Red Black

• Each node has an additional attribute : color (RED, BLACK)
• Root is always Black
• Leaf is all NIL pointer
• all simple paths from any node to leaf should have equal number of black nodes
• all operation take log(n) instead of log(h)

AVL Tree

• Each node has an additional attribute : height

B-Tree and B+ Tree ?

• Suitable for databases and filesystems
• non-binary tree. m-ary tree