Balanced trees
Three trees that keep a logarithmic height: the AVL tree (balance factor, single and double rotations), the red-black tree (its properties) and the B-tree (order, full node, splitting).
- 24 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- Scenarios
- Understand
A few cards from the deck
Self-balancing tree: what is it?
Show the answer
A search tree that reorganises itself on each insertion or deletion so that its height stays on the order of log n.
It guarantees an O(log n) cost for search, insertion and deletion, whatever the order in which keys arrive.
We insert 40, 20, 60, 10, 30 then 5 into an empty AVL tree. After rebalancing, what is the root and where is 30?
- Root 20; 30 is the left child of 40
- Root 20; 30 stays the right child of 20
- Root 10; 30 is the right child of 20
- Root 40; 30 stays the right child of 20
Show the answer
Root 20; 30 is the left child of 40
After 5, node 40 has a factor of +2 and 5 went down to the left of its left child 20: left-left case, right rotation on 40. 20 rises to the root and 40 becomes its right child; 20's right subtree, that is 30, becomes 40's left child, which keeps the order 20 < 30 < 40.
In an AVL tree, a 'left-left' imbalance is fixed by a … rotation, a 'right-right' imbalance by a … rotation.
Show the answer
In an AVL tree, a 'left-left' imbalance is fixed by a right rotation, a 'right-right' imbalance by a left rotation.
The unbalanced node is pivoted to the side opposite the heavy branch. The 'left-right' and 'right-left' cases need two rotations.
Balance factor: what is it?
Show the answer
The difference between the height of a node's left subtree and that of its right subtree.
In an AVL tree, it is −1, 0 or +1 at every node. A value of ±2 after an insertion flags an unbalanced node to repair.
A database index on disk must find a row among tens of millions while reading as few blocks as possible. Which structure suits best?
- A B-tree, with wide nodes and a very low height
- An AVL tree, each node of which holds a single key
- An ordinary binary search tree, simpler to write
- A sorted linked list, for a sequential walk
Show the answer
A B-tree, with wide nodes and a very low height
On disk, what costs is the number of blocks read. A B-tree node fills a block with several hundred keys: the height fits in three or four levels. A binary AVL tree would need dozens.