CS61B Lecture #30
• Balanced search structures (DS(IJ), Chapter 9 Coming Up:
• Pseudo-random Numbers (DS(IJ), Chapter 11)
Last modified: Tue Jan 21 15:11:05 2020
Copyright By PowCoder代写 加微信 powcoder
CS61B: Lecture #30 1
Balanced Search: The Problem
• Why are search trees important?
– Insertion/deletion fast (on every operation, unlike hash table,
which has to expand from time to time).
– Support range queries, sorting (unlike hash tables)
• But O(lg N ) performance from binary search tree requires remaining keys be divided ≈ by some some constant > 1 at each node.
• In other words, that tree be “bushy”
• “Stringy” trees (most inner nodes with one child) perform like linked
• Suffices that heights of any two subtrees of a node always differ
by no more than constant factor K.
Last modified: Tue Jan 21 15:11:05 2020 CS61B: Lecture #30 2
Example of Direct Approach: B-Trees
25 55 90 125
10 20 30 40 50 60 95 100 120 130140150
• Order M B-tree is an M-ary search tree, M > 2.
• Obeys search-tree property:
– Keys are sorted in each node.
– All keys in subtrees to left of a key, K, are < K, and all to right
• Children at bottom of tree are all empty (don’t really exist) and
equidistant from root.
• Searching is simple generalization of binary search.
Last modified: Tue Jan 21 15:11:05 2020 CS61B: Lecture #30 3
Example of Direct Approach: B-Trees
25 55 90 125
10 20 30 40 50 60 95 100 120 130140150
Idea: If tree grows/shrinks only at root, then two sides always have same height.
• Each node, except root, has from ⌈M/2⌉ to M children, and one key “between” each two children.
• Root has from 2 to M children (in non-empty tree).
• Insertion: add just above bottom; split overfull nodes as needed,
moving one key up to parent.
Last modified: Tue Jan 21 15:11:05 2020 CS61B: Lecture #30 4
Sample Order 4 B-tree ((2,4) Tree)
25 55 90 125
10 20 30 40* 50 60 95 100 120 130140150
• Crossed lines show path when finding 40.
• Keys on either side of each child pointer in path bracket 40.
• Each node has at least 2 children, and all leaves (little circles) are at the bottom, so height must be O(lg N ).
• In real-life B-tree, order typically much bigger
– comparable to size of disk sector, page, or other convenient unit
Last modified: Tue Jan 21 15:11:05 2020 CS61B: Lecture #30 5
Inserting in B-tree (Simple Case)
5 10 202530 40 50
• Insert 7:
5 7*10 202530 40 50
Last modified: Tue Jan 21 15:11:05 2020
CS61B: Lecture #30 6
• Insert 27:
Inserting in B-Tree (Splitting)
202527*30 40 50
15 25* 35 45
20 27 30 40 50
(new root) 25* 15
Last modified: Tue Jan 21 15:11:05 2020
CS61B: Lecture #30 7
20 27 30 40 50
• Remove 20 from last tree. 25
Deleting Keys from B-tree
(too small) 27 30
Last modified: Tue Jan 21 15:11:05 2020
CS61B: Lecture #30 8
• Red-black tree is a binary search tree with additional constraints that limit how unbalanced it can be.
• Thus, searching is always O(lg N ).
• Used for Java’s TreeSet and TreeMap types.
• When items are inserted or deleted, tree is rotated and recolored as needed to restore balance.
Last modified: Tue Jan 21 15:11:05 2020 CS61B: Lecture #30 9
Red- Constraints
10 20 30 40 50
1. Each node is (conceptually) colored red or black.
2. Root is black.
3. Every leaf node contains no data (as for B-trees) and is black. 4. Every leaf has same number of black ancestors.
5. Every internal node has two children.
6. Every red node has two black children.
• Conditions 4, 5, and 6 guarantee O(lg N ) searches.
Last modified: Tue Jan 21 15:11:05 2020 CS61B: Lecture #30 10
Red- and (2,4) Trees
• Every red-black tree corresponds to a (2,4) tree, and the operations on one correspond to those on the other.
• Each node of (2,4) tree corresponds to a cluster of 1–3 red-black nodes in which the top node is black and any others are red.
5 10 202530
10 20 30 40 50
Last modified: Tue Jan 21 15:11:05 2020
CS61B: Lecture #30 11
Additional Constraints: Left-Leaning Red-
• A node in a (2,4) or (2,3) tree with three children may be repre- sented in two different ways in a red-black tree:
• We can considerably simplify insertion and deletion in a red-black tree by always choosing the option on the left.
• With this constraint, there is a one-to-one relationship between (2,4) trees and red-black trees.
• The resulting trees are called left-leaning red-black trees.
• As a further simplification, let’s restrict ourselves to red-black trees that correspond to (2,3) trees (whose nodes have no more than 3 children), so that no red-black node has two red children.
Last modified: Tue Jan 21 15:11:05 2020 CS61B: Lecture #30 12
Red- and Rotations
• Insert at bottom just as for binary tree (color red except when tree initially empty).
• Then rotate (and recolor) to restore red-black property, and thus balance.
• Rotation of trees preserves binary tree property, but changes bal- ance.
D D.rotateRight() B
BD E B.rotateLeft() A
Last modified: Tue Jan 21 15:11:05 2020 CS61B: Lecture #30 13
Rotations and Recolorings
• For our purposes, we’ll augment the general rotation algorithms with some recoloring.
• Transfer the color from the original root to the new root, and color the original root red. Examples:
AD BE CE AC
• Neither of these changes the number of black nodes along any path between the root and the leaves.
Last modified: Tue Jan 21 15:11:05 2020 CS61B: Lecture #30 14
Splitting by Recoloring
• Our algorithms will temporarily create nodes with too many children, and then split them up.
• A simple recoloring allows us to split nodes. We’ll call it colorFlip: 10 10
515 515 ······ ···10···
5 1015 5 15
• Here, key 10 joins the parent node, splitting the original.
Last modified: Tue Jan 21 15:11:05 2020 CS61B: Lecture #30 15
The Algorithm (Sedgewick)
• We posit a binary-tree type RBTree: basically ordinary BST nodes plus color.
• Insertion is the same as for ordinary BSTs, but we add some fixups to restore the red-black properties.
RBTree insert(RBTree tree, KeyType key) { if (tree == null)
return new RBTree(key, null, null, RED);
int cmp = key.compareTo(tree.label());
else if (cmp < 0) tree.setLeft(insert(tree.left(), key)); else tree.setRight(insert(tree.right(), key));
return fixup(tree); // Only line that’s all new! }
Last modified: Tue Jan 21 15:11:05 2020 CS61B: Lecture #30 16
Fixing Up the Tree
• As we return back up the BST, we restore the left-leaning red-black properties, and limit ourselves to red-black trees that correspond to (2,3) trees by applying the following (in order) to each node:
• Fixup 1: Convert right-leaning trees to left-leaning:
if (tree.right().isRed()
&& tree.left().isBlack()) {
tree.rotateLeft();
• Fixup 2: Rotate linked red nodes into a normal 4-node (temporarily). FD
Sometimes, node B will be red, so that both B and D end up red. This is fixed by. . .
DGBF EACEG
Last modified: Tue Jan 21 15:11:05 2020
if (tree.left().isRed() &&
tree.left().left().isRed())
tree.rotateRight();
CS61B: Lecture #30 17
Fixing Up the Tree (II)
• Fixup 3: Break up 4-nodes into 3-nodes or 2-nodes.
B F B F tree.right().isRed())
if (tree.left().isRed() &&
colorFlip(tree);
• Fixup 4: As a result of other fixups, or of insertion into the empty tree, the root may end up red, so color the root black after the rest of insertion and fixups are finished. (Not part of the fixup function; just done at the end).
Last modified: Tue Jan 21 15:11:05 2020 CS61B: Lecture #30 18
Example of Left-Leaning 2-3 Red-
• Insert 0 into initial tree on left. No fixups needed.
Last modified: Tue Jan 21 15:11:05 2020
CS61B: Lecture #30 19
Insertion Example (II)
• Instead of 0, let’s insert 6, leading to the tree on the left. This is right-leaning, so apply Fixup 1:
5 20 50 90 6 20
Last modified: Tue Jan 21 15:11:05 2020
CS61B: Lecture #30 20
Insertion Example (III)
• Now consider inserting 85. We need fixup 1 first. 30 30
10 70 10 70
5 20 50 90 5 20 50
40 60 80 85
Last modified: Tue Jan 21 15:11:05 2020
CS61B: Lecture #30 21
• Now apply fixup 2. 30
Insertion Example (IIIa)
40 60 85 80
40 60 80 90
Last modified: Tue Jan 21 15:11:05 2020
CS61B: Lecture #30 22
Insertion Example (IIIb)
• This gives us a 4-node, so apply fixup 3.
10 70 10 70
5 20 50 85 40 60 80 90
5 20 50 85 40 60 80 90
Last modified: Tue Jan 21 15:11:05 2020
CS61B: Lecture #30 23
Insertion Example (IIIc)
• This gives us another 4-node, so apply fixup 3 again. 30 30
10 70 10 70
5 20 50 85 40 60 80 90
5 20 50 85 40 60 80 90
Last modified: Tue Jan 21 15:11:05 2020
CS61B: Lecture #30 24
Insertion Example (IIId)
• This gives us a right-leaning tree, so apply fixup 1. 30
40 60 80 90
10 50 85 20 40 60 80 90
Last modified: Tue Jan 21 15:11:05 2020
CS61B: Lecture #30 25
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com