4. 2-3 Trees

Problem: Binary search trees can become unbalanced, destroying $\log n$ access times.

2-3-Tree Rules

1. All leaves are at the same depth.
2. Keys within a node are ordered.
3. Subtrees respect the BST property: for any key, all keys in the left subtree are smaller, and all keys in the right subtree are larger.

Find

How it works: Always compare the key of the element to the node. If the key is smaller, go the the left. If it is larger, go to the right.

Runtime: $\mathcal{O}({\log }_{2}n)$ to $\mathcal{O}({\log }_{3}n)$ $=\mathcal{O}(\log n)$ since all leaves at same depth

Add

How it works:

• Run modified find to get the closest node
• Add element
• If the parent node now has more than 3 children, split it.
• Propagate upwards if necessary.

Why it works: 2-3-tree rules maintained.

Runtime

• $\mathcal{O}(\log n)$ for find
• $\mathcal{O}(1)$ to add element and split.
• $\mathcal{O}(\log n)$ for propagating b/c it involves at most all the $\log n$ ancestor nodes

Total: $\mathcal{O}(\log n)$

Remove

How it works:

• Run find to get element
• Remove element
• If the node now has 1 child:
  • A neighbor to the left or right has 3 children: adopt child of neighbor
  • If a left or right neighbor has 2 children: merge child into neighbor. Propagate upwards if necessary
  • No priority given in script. However, merging is computationally more expensive b/c it may involve propagation.

Why it works: 2-3-tree rules maintained.

Runtime

• $\mathcal{O}(\log n)$ for find
• $\mathcal{O}(1)$ to remove element and adopting/merging.
• $\mathcal{O}(\log n)$ for propagating b/c it involves at most all the $\log n$ ancestor nodes

Total: $\mathcal{O}(\log n)$