Section 32.13 Vocabulary and Comparison
Subsection 32.13.1 Comparison of Self-Balancing Trees
Here is a summary of the self-balancing tree data structures we have discussed. Given big-O values are for insertion, deletion, and search operations:
| Algorithm | Best Case | Worst Case | Kind of Guarantee | Notes |
|---|---|---|---|---|
| Binary Search Tree | \(O(\log n)\) | \(O(n)\) | None | Data inserted in random order likely results in logarithmic performance, but there are no guarantees. Data inserted in sorted order will result in linear performance.
|
| AVL Tree | \(O(\log n)\) | \(O(\log n)\) | Strong | Maintains a balance requirement at each node.
|
| B-Tree | \(O(\log n)\) | \(O(\log n)\) | Strong |
Base of the logarithm depends on the degree of the tree.
Used in situations where minimizing height is important (e.g., databases, file systems).
|
| Red Black Tree | \(O(\log n)\) | \(O(\log n)\) | Strong |
Corresponds to a B tree of degree 4 (2, 3, or 4 children per node).
Less “strictly” balanced than AVL trees.
|
| Splay Tree | \(O(\log n)\) | \(O(n)\) | Amortized |
In a sequence of operations, the average time complexity is O(log n). Any one operation may take longer.
Recently accessed nodes are near the root, so access patterns with locality of reference can be very efficient.
|
| Treap | \(O(\log n)\) | \(O(n)\) | Probabilistic |
Each node is assigned a random priority that helps determine the tree’s structure.
Very likely to have a balanced structure, but no worst-case guarantee.
|
| Skip List | \(O(\log n)\) | \(O(n)\) | Probabilistic |
Random numbers used to determine the number of levels of each node.
Very likely to have logarithmic performance, but no worst-case guarantee.
Easier than some other strategies to implement concurrency in.
|
Subsection 32.13.2 Vocabulary
- AVL Tree
- A self-balancing binary search tree that keeps left and right subtree heights close at every node.
- B-tree
- A balanced search tree where each node can contain multiple keys and children.
- degree
- The maximum number of children a node can have in a tree.
- double rotation
- A two-step rebalancing operation that performs one rotation on a child and one on its parent.
- left rotation
- A local tree transformation that promotes a node’s right child and moves the node down to the left.
- pivot
- The node around which a rotation is performed.
- Red-Black Tree
- A self-balancing binary search tree that uses node colors and structural rules to keep height logarithmic.
- right rotation
- A local tree transformation that promotes a node’s left child and moves the node down to the right.
- Skip List
- A layered linked-list structure that supports fast search, insertion, and deletion.
- splay
- The operation of moving a node toward the root through rotations after access.
- splay tree
- A self-adjusting binary search tree that splays recently accessed nodes toward the root.
You have attempted of activities on this page.
