Search Trees

Balanced Search Trees
1. Rotation: rotate a child to be above its parent
AVL Trees
1. Add a rule to the binary search-tree definition that will maintain a logarithmic height for the tree
2. O(log n)
Splay Trees
1. 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.
  1. zig-zig zig-zag zig
Multiway search tree
1. (2,4) tree
2. 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.
Red-Black Trees
1. Binary search tree with nodes colored red and black
  1. Root property: the root is black
  2. External Property: every external node is black
  3. Red property: the children of a red node are black
  4. Depth property: all external nodes have the same black depth (number of proper ancestors that are black)

Resource summary

	Created by Angelica Cordero over 3 years ago