• AVL tree
  • Adelson-Velskii and Landis - 1962
  • Keep track of the "balance factor" for each node in the tree (new instance variable) - height of left (or right) subtree - height of right (or left) subtree.
  • Balance factor must be -1, 0, 1
  • Do a rotation if the balance factor is < -1 or > 1 after inserting a new node
    • Single rotation (left or right) if heavyness is on that side for parent and child
    • Double rotation (left or right) if heaviness is on one side for the child and the other side for the parent
  • The height of an AVL tree is floor(log n)
• Splay tree
  • Do search, insert, and delete just like a plain binary search tree
  • then splay the tree starting at the node sought (insert), node inserted (insert), or parent of the node deleted (delete).
    • If the node is the root, terminate the splay
    • If the node has a parent but no grandparent - do a single rotation
    • If the node has a parent and a grandparent - do a super single rotation (if both parent and node are on the same side of the tree) or a double rotation (if they are on opposite sides of the tree)
  • At the end of a splay, the start node is the root of the tree.
  • The basic idea is that if you get a "bad tree" (height = n), you aren't stuck with it.
• Red-Black tree
  • Keep track of the color of the link to your parent, or the colors of the links to your children.
    • The root node is always black
    • All the paths from the root to the leaves have the same number of black nodes
    • No path from the root to a leaf may contain two consecutive nodes colored red
  • Do search, insert, and delete just like a plain binary search tree
  • Only insert and delete can cause problems
  • Problems are fixed by recoloring or by rotations
  • The height of a red-black tree is at most 2*log n.
• 2-3 tree ( demo)
• B-tree
  • A B-tree is a balanced m-way search tree
    • the root has at most m subtrees and m-1 keys
    • the keys are ordered
    • all data is stored in the leaves which are all at the same depth
    • Every nonleaf node (except possibly the root) has between m/2 and m children inclusive.
  • B-trees are used when you have more data than the RAM of your computer can hold. In this case, you have to get the nodes in the search tree from the disk. The bottleneck is disk access time, so you want your nodes to be big - ideally the max size of a disk access. This increases your chance of finding what you are searching for in the current node, decreases the depth of the tree (access is logmn << log 2n for m >> 2), and optimizes your disk access.
  • A B-tree of order 2 is a full binary search tree, of order 3 is a 2-3 tree.