Chapter 8: Balanced trees
The chapter introduction motivates balanced trees as a way to improve tree performance when other data structures fall short.
After this chapter you will be able to
- Motivation for balanced trees. Explain why a balanced tree is worth considering when arrays or linked lists do not deliver the desired performance: binary trees can be slow in the worst case, and balancing helps them perform effectively.
- Search and insertion tradeoff. Explain why a sorted array supports O(log n) binary search but takes O(n) time to insert a value, and contrast this with linked-list insertion and search.
- Binary search tree ordering. Describe how a BST is organized: each node has up to two children, with smaller values on the left and greater values on the right, including across the subtrees.
- Directional BST search. Trace a search from the root by comparing the target with each node and choosing the left or right subtree; explain how reaching the target or its missing position settles the search.
- Tree height and search time. Explain how tree height affects search time: a short binary search tree can be searched in O(log n) time, while a tree whose nodes form a line takes O(n) time.
- Larger insertions and balancing. Describe how repeatedly adding values larger than the existing nodes can extend a BST to the right, and explain why the resulting height motivates balancing.
- AVL tree self-balancing. Explain that an AVL tree is a self-balancing binary search tree that uses rotations to keep its height O(log n).
- Left Rotation and Root Change. Describe how a left rotation rearranges a tree, using the example that starts with A as the root and ends with B as the root.
- AVL Balance and Rotations. Explain when the AVL example calls for a rotation and what repeated rotations accomplish as nodes are added.
- Balance factors and thresholds. Explain what an AVL node stores to detect imbalance and which balance-factor values call for rebalancing.
- Post-insertion balance updates. Trace how an AVL tree checks for imbalance after adding a node and what it does when it finds one.
- Recently accessed nodes at top. Explain that looking up a node in a splay tree makes it the new root, so looking it up again is instant and other recently accessed nodes tend to be faster to find.
- Search costs and overall guarantee. Distinguish a splay tree’s possible slow single search from its guaranteed total time across many searches, including the cost of moving a node to the root.
- B-tree node structure. Distinguish B-trees from binary trees by explaining that a B-tree node can have more than two children and more than one key.
- B-tree seek time advantage. Explain why reading more data per B-tree node can make lookups faster, especially when retrieving data from disk.
- BST performance and tree height. Explain that balanced binary search trees offer the same Big O search performance as arrays with better insertion performance, and that a tree’s height affects its performance.
- B-tree nodes and seek time. Describe B-trees as generalized BSTs whose nodes can hold multiple keys and children, and explain that they try to minimize seek time by reading more data in one go.
What it builds on
- Binary trees (chapter 7) · The reader has encountered binary trees.
- Arrays and linked lists (chapter 2) · The reader has encountered arrays and linked lists.
- Binary search (chapter 1) · Assumes familiarity with binary search.
- Inserting into the middle of a list (chapter 2) · Assumes familiarity with inserting into lists.
- Linked lists (chapter 2) · Linked-list insertion behavior
- Arrays (chapter 2) · Array behavior
- Big O notation (chapter 1) · Big O notation for comparing how running time grows.
Section by section
Introduction
The chapter introduction motivates balanced trees as a way to improve tree performance when other data structures fall short.
- Motivation for balanced trees: Explain why a balanced tree is worth considering when arrays or linked lists do not deliver the desired performance: binary trees can be slow in the worst case, and balancing helps them perform effectively.
Why it matters: This is the performance problem that motivates the rest of the chapter.
Key terms: arrays, linked lists, binary trees, balanced tree, worst-case scenario
8.1 A balancing act
This section contrasts fast searching in a sorted array with fast insertion in a linked list, motivating a way to get both advantages.
- Search and insertion tradeoff: Explain why a sorted array supports O(log n) binary search but takes O(n) time to insert a value, and contrast this with linked-list insertion and search.
Why it matters: This tradeoff explains why the chapter looks for a way to combine fast searching and insertion.
Key terms: binary search, sorted array, linked list, O(log n), O(n)
8.2 Improving insertion speed with trees
This section introduces binary search trees as a way to seek fast searches and insertions, then shows how their ordering rule guides a search.
- Search and insertion tradeoff: Explain why the section introduces trees: it seeks the search speed of a sorted array alongside faster insertion, as found in linked lists.
Why it matters: The tradeoff explains why the chapter turns to trees rather than sticking with arrays or linked lists. - Binary search tree ordering: Describe how a BST is organized: each node has up to two children, with smaller values on the left and greater values on the right, including across the subtrees.
Why it matters: This ordering rule is what lets a search rule out whole parts of the tree. - Directional BST search: Trace a search from the root by comparing the target with each node and choosing the left or right subtree; explain how reaching the target or its missing position settles the search.
Why it matters: Following just the possible path is the reason the section says BST searches can be fast.
Key terms: sorted array, linked lists, balanced binary search tree (BST), binary search tree, BST, node, left child, right child, subtree, root node
8.3 Shorter trees are faster
This section shows why a binary search tree’s height determines search speed and why repeatedly adding larger values can produce a slow, one-sided tree.
- Tree height and search time: Explain how tree height affects search time: a short binary search tree can be searched in O(log n) time, while a tree whose nodes form a line takes O(n) time.
Why it matters: It explains why two trees containing the same number of nodes can have very different search speeds. - Larger insertions and balancing: Describe how repeatedly adding values larger than the existing nodes can extend a BST to the right, and explain why the resulting height motivates balancing.
Why it matters: It shows why a BST may need balancing rather than relying on its insertion order to keep it short.
Key terms: height, worst-case tree, best-case tree, O(n), O(log n), BST, balanced BST
8.4 AVL trees: A type of balanced tree
Introduces AVL trees as self-balancing binary search trees that use rotations to keep their height O(log n).
- AVL tree self-balancing: Explain that an AVL tree is a self-balancing binary search tree that uses rotations to keep its height O(log n).
Why it matters: This connects the desired short tree height to a tree that maintains its own balance.
Key terms: AVL trees, self-balancing BST, O(log n) height, rotations
8.5 Rotations
This section shows how left rotations rearrange nodes to restore balance in an AVL tree.
- Left Rotation and Root Change: Describe how a left rotation rearranges a tree, using the example that starts with A as the root and ends with B as the root.
Why it matters: A rotation lets the tree regain balance by rearranging its existing nodes. - AVL Balance and Rotations: Explain when the AVL example calls for a rotation and what repeated rotations accomplish as nodes are added.
Why it matters: This connects rotations to the balance problem that arises as an AVL tree grows.
Key terms: rotation, left rotation, root node, AVL trees, balanced, unbalanced
8.6 How does the AVL tree know when it’s time to rotate?
The section explains how an AVL tree detects imbalance after insertion and why a balanced BST supports fast searches and insertions.
- Balance factors and thresholds: Explain what an AVL node stores to detect imbalance and which balance-factor values call for rebalancing.
Why it matters: The balance factor gives the tree a way to detect when an uneven shape needs fixing. - Post-insertion balance updates: Trace how an AVL tree checks for imbalance after adding a node and what it does when it finds one.
Why it matters: Checking ancestors after an insertion lets the tree find the imbalance caused by the new node. - Balanced BST operation speed: Explain why the section presents a balanced BST as providing fast searches and insertions.
Why it matters: This connects the balancing mechanism to the chapter’s goal of fast searches and inserts.
Key terms: height, balance factor, rebalance, ancestors, rotation, balanced BST, AVL tree, O(log n), insertion
8.7 Splay trees
This section explains how splay trees make recently accessed nodes faster to find and why their overall search performance can be good despite slow individual searches.
- Recently accessed nodes at top: Explain that looking up a node in a splay tree makes it the new root, so looking it up again is instant and other recently accessed nodes tend to be faster to find.
Why it matters: This explains why repeated lookups, such as requests for the same zip code, can get faster. - Search costs and overall guarantee: Distinguish a splay tree’s possible slow single search from its guaranteed total time across many searches, including the cost of moving a node to the root.
Why it matters: It prevents the overall performance guarantee from being mistaken for a guarantee about every search.
Key terms: splay trees, root, recently, balanced, rotate, O(log n), linear time, O(n log n)
8.8 B-trees
Introduces B-trees as a generalization of binary search trees whose nodes can hold multiple keys and have more than two children.
- B-tree node structure: Distinguish B-trees from binary trees by explaining that a B-tree node can have more than two children and more than one key.
Why it matters: This structural difference is the starting point for understanding why B-trees are useful.
Key terms: B-trees, binary trees, nodes, children, keys
8.9 What is the advantage of B-trees?
Explains why B-trees can retrieve data efficiently and describes their key ordering and node structure.
- B-tree seek time advantage: Explain why reading more data per B-tree node can make lookups faster, especially when retrieving data from disk.
Why it matters: The cost of retrieving data can matter as much as the amount of data read. - B-tree key ordering: Describe how keys remain ordered in the B-tree shown, including where smaller and larger keys lie relative to a key.
Why it matters: The ordering explains how a node can hold multiple keys while preserving the search-tree property. - B-tree keys and children: State the relationship between the number of keys and children in a B-tree node as described here.
Why it matters: This relationship makes the structure of the illustrated B-tree easier to read.
Key terms: B-trees, seek time, nodes, B-tree, BST, keys, children, root node
8.10 Recap
This recap summarizes the performance benefits of balanced binary search trees and how AVL trees and B-trees pursue them.
- BST performance and tree height: Explain that balanced binary search trees offer the same Big O search performance as arrays with better insertion performance, and that a tree’s height affects its performance.
Why it matters: This is the performance tradeoff that motivates balanced trees. - AVL tree balancing: State that AVL trees are a popular kind of balanced BST and that they balance themselves through rotation.
Why it matters: It identifies rotation as the way AVL trees maintain balance. - B-tree nodes and seek time: Describe B-trees as generalized BSTs whose nodes can hold multiple keys and children, and explain that they try to minimize seek time by reading more data in one go.
Why it matters: It connects the B-tree’s structure with the performance cost it aims to reduce.
Key terms: balanced binary search trees (BSTs), Big O, height, AVL trees, balanced BST, rotation, B-trees, generalized BSTs, keys, child nodes
Concepts explained in this chapter
- binary search treeA binary search tree is a binary tree whose nodes are ordered so that values in the left subtree precede the node's value and values in the right subtree follow it.
- tree heightTree height is the maximum number of edges or steps on a downward path from the root to a leaf or other node.
- AVL treeAn AVL tree is a self-balancing binary search tree that maintains subtree heights within a bounded difference by performing rotations.
- tree rotationA tree rotation is a local restructuring operation that changes parent-child relationships while preserving the tree's ordering.
- binary treeA binary tree is a tree in which each node has at most two children.
- treeA tree is a connected graph with no cycles, so no path of edges leads back to an earlier vertex.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.