Search Trees

Search Trees

1. Balanced Search Trees

   • Rotation: rotate a child to be above its parent

2. AVL Trees

   • Add a rule to the binary search-tree definition that will maintain a logarithmic height for the tree
   • O(log n)

3. Splay Trees

   • Splaying: Given a node x of a binary search tree T, we splay x by moving x to the root of T through a sequence of restructurings.
     • zig-zig zig-zag zig

4. Multiway search tree

   • (2,4) tree
   • Map entries stored in a search tree are pairs of the form (k,v), where k is the key and v is the value associated with the key.

5. Red-Black Trees

   • Binary search tree with nodes colored red and black
     • Root property: the root is black
     • External Property: every external node is black
     • Red property: the children of a red node are black
     • Depth property: all external nodes have the same black depth (number of proper ancestors that are black)

Images and files in the map