COMP9024: Data Structures and Algorithms
COMP9024: Data Structures and
Algorithms
Self-Balancing Search Trees
1
Contents
• AVL trees
• Splay trees
• 2-4 trees
• Red-black trees
2
3
AVL Trees
AVL Tree Definition
• AVL trees are balanced.
• An AVL Tree is a binary search
tree such that for every
internal node v of T, the
heights of the children of v can
differ by at most 1.
• We call it height difference
constraint.
An example of an AVL tree
where the heights are shown
next to the nodes:
44
17 78
32 50 88
48 62
0
0
1
1 0
2
3
0
4
Height of an AVL Tree
• Fact: The height of an AVL tree storing n keys is O(log n).
• Proof: Let us bound n(h): the minimum number of nodes of an AVL tree of height h.
• We easily see that n(0) = 1 and n(1) = 2
• For n > 1, an AVL tree of height h contains the root node, one AVL subtree of height h-1 and
another of height h-2.
• That is, n(h) = 1 + n(h-1) + n(h-2)
• Knowing n(h-1) > n(h-2), we get n(h) > 2n(h-2). So
n(h) > 2n(h-2), n(h) > 4n(h-4), n(h) > 8n(n-6), … (by induction),
n(h) > 2in(h-2i)
• Let h-2i=0. We have i=h/2 and n(h) > 2 h/2
• Taking logarithms: h < 2log n(h) • Thus the height of an AVL tree is O(log n) 5 Insertion in an AVL Tree • Insertion is as in a binary search tree • Example: insert 54 44 17 78 32 50 88 48 62 54w b=x a=y c=z44 17 78 32 50 88 48 62 before insertion after insertion 6 7 Trinode Restructuring (1/4) After inserting a new entry into an AVL tree, the height difference property may be violated. In order to restore the height difference property, we perform the trinode restructuring: Find the first ancestor z of the new node that violates the height difference constraint along the path from the new node to the root. Find a child y of z with the larger height, and find a child x of y with the larger height . Rename x, y and z as a, b and c, respectively, in in-order traversal order. Perform trinode restructuring on a, b and c so that b becomes of the new root of the subtree previously rooted at z. 88 Trinode Restructuring (Single Rotations) (2/4) Single Rotations: T0 T1 T2 T3 c = x b = y a = z T0 T1 T2 T3 c = x b = y a = z single rotation T3 T2 T1 T0 a = x b = y c = z T3T2T1 T a = x b = y c = z single rotation 0 9 Trinode Restructuring (Double Rotations) (3/4) double rotations: double rotationa = z b = x c = y T0 T2 T1 T3 T0 T2 T3T1 a = z b = x c = y double rotationc = z b = x a = y T0 T2 T1 T3 T0 T2 T3 T1 c = z b = x a = y Trinode Restructuring (Double Rotations) (4/4) Inserting a new node into an AVL tree may increase the height of the tree by one. The objective of a trinode restructuring is to reduce the height of the subtree rooted at node z by one while maintaining the binary tree property. 10 Insertion Example, continued 88 44 17 7832 50 48 621 3 0 1 1 2 54 0 x (b) y (a) z (c) unbalanced balanced 44 17 8832 50 48 781 4 0 0 2 1 3 62 0 z (c) y (a) x (b) 54 0 0 0 11 Removal in an AVL Tree • Removal begins as in a binary search tree, which means the node removed will become an empty external node. Its parent, w, may cause an imbalance. • Example: delete 32 44 17 7832 50 8848 62 54 44 17 7850 8848 62 54 before deletion of 32 after deletion 12 Rebalancing after a Removal • Let z be the first unbalanced node encountered while travelling up the tree from w. Also, let y be the child of z with the larger height, and let x be the child of y with the larger height. • Perform trinode restructing on x, y and z to restore balance at z. After this restructuring, the whole tree becomes balanced. 44 17 7850 8848 62 54 w c=x b=y a=z 44 17 78 50 88 48 62 54 13 Running Times for AVL Trees • a single restructure is O(1) • using a linked-structure binary tree • find is O(log n) • height of tree is O(log n), no restructures needed • insert is O(log n) • initial find is O(log n) • Restructuring up the tree, maintaining heights is O(log n) • delete is O(log n) • initial find is O(log n) • Restructuring up the tree, maintaining heights is O(log n) 14 Splay Trees 15 all the keys in the yellow region are ≤ 20 all the keys in the blue region are ≥ 20 Splay Trees are Binary Search Trees • BST Rules: • entries stored only at internal nodes • keys stored at nodes in the left subtree of v are less than or equal to the key stored at v • keys stored at nodes in the right subtree of v are greater than or equal to the key stored at v • An inorder traversal will return the keys in order (20,Z) (37,P)(21,O) (14,J) (7,T) (35,R)(10,A) (1,C) (1,Q) (5,G)(2,R) (5,H) (6,Y)(5,I) (8,N) (7,P) (36,L) (10,U) (40,X) note that two keys of equal value may be well- separated 16 Searching in a Splay Tree: Starts the Same as in a BST • Search proceeds down the tree to find the item or an empty node. • Example: Search for an item with key 11. (20,Z) (37,P)(21,O) (14,J) (7,T) (35,R)(10,A) (1,C) (1,Q) (5,G)(2,R) (5,H) (6,Y)(5,I) (8,N) (36,L) (10,U) (40,X) 17 Example Searching in a BST, continued • search for key 8, ends at a non-empty node. (20,Z) (37,P)(21,O) (14,J) (7,T) (35,R)(10,A) (1,C) (1,Q) (5,G)(2,R) (5,H) (6,Y)(5,I) (8,N) (7,P) (36,L) (10,U) (40,X) 18 Splay Trees do Rotations after Every Operation (Even Search) • new operation: splay • splaying moves a node to the root using rotations right rotation makes the left child x of a node y into y’s parent; y becomes the right child of x y x T1 T2 T3 y x T1 T2 T3 left rotation makes the right child y of a node x into x’s parent; x becomes the left child of y y x T1 T2 T3 y x T1 T2 T3 (structure of tree above y is not modified) (structure of tree above x is not modified) a right rotation about y a left rotation about x 19 Splaying: is x the root? stop is x a child of the root? right-rotate about the root left-rotate about the root is x the left child of the root? is x a left-left grandchild? is x a left-right grandchild? is x a right-right grandchild? is x a right-left grandchild? right-rotate about g, right-rotate about p left-rotate about g, left-rotate about p right-rotate about p, left-rotate about g left-rotate about p, right-rotate about g start with node x “x is a left-left grandchild” means x is a left child of its parent, which is itself a left child of its parent p is x’s parent; g is p’s parent no yes yes yes yes yes yes no no yes zig-zig zig-zag zig-zag zig-zig zigzig 20 Visualizing the Splaying Cases zig-zag y x T2 T3 T4 z T1 y x T2 T3 T4 z T1 y x T1 T2 T3 z T4 zig-zig y z T4T3 T2 x T1 zig x w T1 T2 T3 y T4 y x T2 T3 T4 w T1 21 Splaying Example • let x = (8,N) • x is the right child of its parent, which is the left child of the grandparent • left-rotate around p, then right- rotate around g (20,Z) (37,P)(21,O) (14,J) (7,T) (35,R)(10,A) (1,C) (1,Q) (5,G)(2,R) (5,H) (6,Y)(5,I) (8,N) (7,P) (36,L) (10,U) (40,X) x g p (10,A) (20,Z) (37,P)(21,O) (35,R) (36,L) (40,X)(7,T) (1,C) (1,Q) (5,G)(2,R) (5,H) (6,Y)(5,I) (14,J)(8,N) (7,P) (10,U) x g p (10,A) (20,Z) (37,P)(21,O) (35,R) (36,L) (40,X) (7,T) (1,C) (1,Q) (5,G)(2,R) (5,H) (6,Y)(5,I) (14,J) (8,N) (7,P) (10,U) x g p 1. (before rotating) 2. (after first rotation) 3. (after second rotation) x is not yet the root, so we splay again 22 Splaying Example, Continued • now x is the left child of the root • right-rotate around root (10,A) (20,Z) (37,P)(21,O) (35,R) (36,L) (40,X) (7,T) (1,C) (1,Q) (5,G)(2,R) (5,H) (6,Y)(5,I) (14,J) (8,N) (7,P) (10,U) x (10,A) (20,Z) (37,P)(21,O) (35,R) (36,L) (40,X) (7,T) (1,C) (1,Q) (5,G)(2,R) (5,H) (6,Y)(5,I) (14,J) (8,N) (7,P) (10,U) x 1. (before applying rotation) 2. (after rotation) x is the root, so stop 23 Example Result of Splaying • tree might not be more balanced • e.g. splay (40,X) • before, the depth of the shallowest leaf is 2 and the deepest is 6 • after, the depth of shallowest leaf is 3 and deepest is 7 (20,Z) (37,P)(21,O)(7,T) (35,R)(10,A) (1,C) (1,Q) (5,G)(2,R) (5,H) (6,Y)(5,I) (8,N) (7,P) (36,L) (10,U) (40,X) (20,Z) (37,P) (21,O) (14,J) (7,T) (35,R) (10,A) (1,C) (1,Q) (5,G)(2,R) (5,H) (6,Y)(5,I) (8,N) (7,P) (36,L)(10,U) (40,X) (20,Z) (37,P) (21,O) (14,J) (7,T) (35,R) (10,A) (1,C) (1,Q) (5,G)(2,R) (5,H) (6,Y)(5,I) (8,N) (7,P) (36,L) (10,U) (40,X) before after first splay after second splay (14,J) 24 Splay Tree Definition • a splay tree is a binary search tree where a node is splayed after it is accessed (for a search or update) • deepest node accessed is splayed • splaying costs O(h),where h is height of the tree – which is still O(n) worst-case • O(h) rotations, each of which is O(1) 25 Splay Trees & Ordered Dictionaries • which nodes are splayed after each operation? use the parent of the node that was actually removed from the tree (the parent of the node that the removed item was swapped with) delete(k) use the new node containing the entry insertedinsert(k,v) if key found, use that node if key not found, use the node where the search stops find(k) splay nodemethod 26 Amortized Analysis of Splay Trees • Running time of each operation is proportional to time for splaying. • Define rank(v) as the logarithm (base 2) of the number of nodes in subtree rooted at v. • Costs: zig = $1, zig-zig = $2, zig-zag = $2. • Thus, cost for splaying a node at depth d = $d. • Imagine that we store rank(v) & cyber-dollars at each node v of the splay tree (just for the sake of analysis). 27 Cost per zig • Doing a zig at x costs at most rank’(x) - rank(x): • cost = rank’(x) + rank’(y) - rank(y) - rank(x) < rank’(x) - rank(x). zig x w T1 T2 T3 y T4 y x T2 T3 T4 w T1 28 Cost per zig-zig and zig-zag • Doing a zig-zig or zig-zag at x costs at most 3(rank’(x) - rank(x)) - 2. • Proof: See Proposition 9.2, Page 440. y x T1 T2 T3 z T4 zig-zig y z T4T3 T2 x T1 zig-zag y x T2 T3 T4 z T1 y x T2 T3 T4 z T1 29 Cost of Splaying • Cost of splaying a node x at depth d of a tree rooted at r: • at most 3(rank(r) - rank(x)) - d + 2: • Proof: Splaying x takes d/2 splaying substeps: .2))(rank)(rank(3 2)/(2))(rank)(rank(3 2)2))(rank)(rank(3( cost cost 0 1 2/ 1 2/ 1 +−−≤ +−−= +−−≤ ≤ − = = ∑ ∑ dxr ddxr xx i d i i i d i 30 Performance of Splay Trees • Recall: rank of a node is logarithm of its size. • Thus, amortized cost of any splay operation is O(log n). • In fact, the analysis goes through for any reasonable definition of rank(x). • This implies that splay trees can actually adapt to perform searches on frequently-requested items much faster than O(log n) in some cases. 31 32 (2,4) Trees Multi-Way Search Tree • A multi-way search tree is an ordered tree such that • Each internal node has at least two children and stores d −1 key- element items (ki, oi), where d is the number of children • For a node with children v1 v2 … vd storing keys k1 k2 … kd−1 • keys in the subtree of v1 are less than k1 • keys in the subtree of vi are between ki−1 and ki (i = 2, …, d − 1) • keys in the subtree of vd are greater than kd−1 11 24 2 6 8 15 30 27 32 33 Multi-Way Inorder Traversal • We can extend the notion of inorder traversal from binary trees to multi-way search trees • Namely, we visit item (ki, oi) of node v between the recursive traversals of the subtrees of v rooted at children vi and vi + 1 • An inorder traversal of a multi-way search tree visits the keys in increasing order 11 24 2 6 8 15 30 27 32 1 2 3 7 9 4 6 5 8 34 Multi-Way Searching • Similar to search in a binary search tree • A each internal node with children v1 v2 … vd and keys k1 k2 … kd−1 • k = ki (i = 1, …, d − 1): the search terminates successfully • k < k1: we continue the search in child v1 • ki−1 < k < ki (i = 2, …, d − 1): we continue the search in child vi • k > kd−1: we continue the search in child vd
• Example: search for 30
11 24
2 6 8 15 27 30 32
35
(2,4) Trees
• A (2,4) tree (also called 2-4 tree or 2-3-4 tree) is a multi-way search with the
following properties
• Node-Size Property: every node is either a 2-node, or a 3-node, or a 4-node,
and holds one element, or two elements, or three elements, respectively.
• Depth Property: all the external (leaf) nodes have the same depth.
10 15 24
2 8 12 27 3218
36
Height of a (2,4) Tree
• Theorem: A (2,4) tree storing n items has height O(log n)
Proof:
• Let h be the height of a (2,4) tree with n items
• Since there are at least 2i items at depth i = 0, … , h − 1 and no
items at depth h, we have
n ≥ 1 + 2 + 4 + … + 2h−1 = 2h − 1
• Thus, h ≤ log (n + 1)
• Searching in a (2,4) tree with n items takes O(log n) time
1
2
2h−1
items
0
1
h-1
depth
37
Insertion
• We insert a new item (k, o) at a leaf node reached by searching for k
• We preserve the depth property but
• We may cause an overflow (i.e., node v may become a 5-node)
• Example: inserting key 30 causes an overflow
27 32 35
10 15 24
2 8 12 18
10 15 24
2 8 12 27 30 32 3518
v
v
38
Overflow and Split
• We handle an overflow at a 5-node v with a split operation:
• let v1 … v5 be the children of v and k1 … k4 be the keys of v
• node v is replaced by nodes v’ and v”
• v’ is a 3-node with keys k1 k2
• v” is a 2-node with key k4
• key k3 is inserted into the parent u of v (a new root may be created)
• The overflow may propagate to the parent node u
15 24
12 27 30 32 3518
v
u
15 24 32
12 27 3018
v’
u
35
v”
39
Analysis of Insertion
Algorithm insert(k, o)
{
search for key k to locate the insertion
node v;
add the new entry (k, o) at node v;
while ( overflow(v) )
{ if ( isRoot(v) )
create a new empty root above v;
v = split(v);
}
}
• Let T be a (2,4) tree with n
items
• Tree T has O(log n) height
• Step 1 takes O(log n) time
because we visit O(log n)
nodes
• Step 2 takes O(1) time
• Step 3 takes O(log n) time
because each split takes O(1)
time and we perform O(log
n) splits
• Thus, an insertion in a (2,4)
tree takes O(log n) time
40
Deletion
• We reduce deletion of an entry to the case where the item is at a leaf
node
• Otherwise, we replace the entry with its inorder successor (or,
equivalently, with its inorder predecessor) and delete the latter entry
• Example: to delete key 24, we replace it with 27 (inorder successor)
27 32 35
10 15 24
2 8 12 18
32 35
10 15 27
2 8 12 18
41
Underflow and Fusion
• Deleting an entry from a node v may cause an underflow, where
node v becomes a 1-node with one child and no keys
• To handle an underflow at node v with parent u, we consider two
cases
• Case 1: the adjacent siblings of v are 2-nodes
• Fusion operation: we merge v with an adjacent sibling w and move an entry
from u to the merged node v’
• After a fusion, the underflow may propagate to the parent u
9 14
2 5 7 10
u
v
9
10 14
u
v’w
2 5 7
42
Underflow and Transfer
• To handle an underflow at node v with parent u, we consider two
cases
• Case 2: an adjacent sibling w of v is a 3-node or a 4-node
• Transfer operation:
1. we move an item from u to v
2. we move an item from w to u
• After a transfer, no underflow occurs
4 9
6 82
u
vw
4 8
62 9
u
vw
43
Analysis of Deletion
• Let T be a (2,4) tree with n items
• Tree T has O(log n) height
• In a deletion operation
• We visit O(log n) nodes to locate the node from which
to delete the entry
• We handle an underflow with a series of O(log n)
fusions, followed by at most one transfer
• Each fusion and transfer takes O(1) time
• Thus, deleting an item from a (2,4) tree takes
O(log n) time
44
45
Red-Black Trees
From (2,4) to Red-Black Trees
A red-black tree is a representation of a (2,4) tree by means of a
binary tree whose nodes are colored red or black
In comparison with its associated (2,4) tree, a red-black tree has
same logarithmic time performance
simpler implementation with a single node type
2 6 73 54
4 6
2 7
5
3
3
5OR
46
Red-Black Trees
A red-black tree is a binary search tree that satisfies
the following properties:
Color Properties:
Each node is either black or red
The root is black
There are no two adjacent red nodes.
Depth Property: the number of black nodes on every path
from the root to each leaf is the same
9
154
62 12
1
21
47
Height of a Red-Black Tree
Theorem: A red-black tree storing n entries has
height O(log n)
Proof:
The height of a red-black tree is at most twice the height of
its associated (2,4) tree, which is O(log n)
The search algorithm for a binary search tree is the
same as that for a binary search tree
By the above theorem, searching in a red-black tree
takes O(log n) time
48
Insertion
To perform operation insert(k, o), we execute the insertion
algorithm for binary search trees and color red the newly inserted
node z unless it is the root
We preserve the color and depth properties
If the parent v of z is black, we are done
Else (v is red ) we have a double red (i.e., a violation of the color
properties), which requires a restructuring of the tree
Example where the insertion of 4 causes a double red:
6
3 8
6
3 8
4
v v
z
49
Remedying a Double Red
Consider a double red with child z and parent v, and let w be the sibling of v
4
6
7
z
vw
2
4 6 7
.. 2 ..
Case 1: w is black
The double red is an incorrect
replacement of a 4-node
Restructuring: we change the
4-node replacement
Case 2: w is red
The double red corresponds
to an overflow
Recoloring: we perform the
equivalent of a split
4
6
7
z
v
2 4 6 7
2
w
50
Restructuring (1/2)
A restructuring remedies a child-parent double red when the
parent red node has a black sibling
It is equivalent to restoring the correct replacement of a 4-node
The internal property is restored and the other properties are
preserved
4
6
7
z
vw
2
4 6 7
.. 2 ..
4
6
7
z
v
w
2
4 6 7
.. 2 ..
51
Restructuring (2/2)
There are four restructuring configurations depending on
whether the double red nodes are left or right children
2
4
6
6
2
4
6
4
2
2
6
4
2 6
4
52
Recoloring
A recoloring remedies a child-parent double red when the parent
red node has a red sibling
The parent v and its sibling w become black and the grandparent u
becomes red, unless it is the root
It is equivalent to performing a split on a 5-node
The double red violation may propagate to the grandparent u
4
6
7
z
v
2 4 6 7
2
w 4
6
7
z
v
6 7
2
w
… 4 …
2
u
53
Analysis of Insertion
Algorithm insert(k, o)
{ search for key k to locate the
insertion node z;
add the new entry (k, o) at node z
and color z red;
while doubleRed(z)
{ if ( isBlack(sibling(parent(z))))
{ z = restructure(z);
return; }
else // sibling(parent(z) is red
z = recolor(z);
}
Recall that a red-black tree
has O(log n) height
Step 1 takes O(log n) time
because we visit O(log n)
nodes
Step 2 takes O(1) time
Step 3 takes O(log n) time
because we perform
O(log n) recolorings, each
taking O(1) time, and
at most one restructuring
taking O(1) time
Thus, an insertion in a red-
black tree takes O(log n) time
54
Deletion (1/9)
To perform operation delete(k), we first execute the deletion algorithm for binary
search tree. We search for a node u storing such an entry. If node u has two
children, we find the node v following u or preceding u in the inorder
traversal of T, move the entry at v to u, and perform the removal at v.
Thus, we only consider the removal of an entry with key k stored at a node
v with at most one child.
Example: delete 9
9
154
62 12
7
21
12
154
62 x
7
21
v
u u
v
55
Deletion (2/9)
If v has no child, we are done.
9
154
62 12
7
21
12
154
62
7
21
v
u
56
Deletion (3/9)
Assume v has one child. Let r be the child of v and x be the parent
of v. We remove nodes v, and make r a child of x. If v was red
(hence r is black) or r is red (hence v was black), we color r black
and we are done.
Example: delete 6.
9
154
62 12
7
21
12
154
72 x 21v
x
r
57
Deletion (4/9)
If, instead, r is black and v was black, then, to preserve the depth
property, we give r a fictitious double black color. We now have a
color violation, called the double black problem. A double black in T
denotes an underflow in the corresponding (2,4) tree T.
10
7 15
v
r 18
63
5
x
10
7 18
63
5
x
r
58
Deletion (5/9)
Recall that x is the parent of the double black node r. Let y be the
sibling of r. To remedy the double-black problem at r, we consider
three cases:
Case 1: y is black and has a red child
We perform a restructuring, equivalent to a transfer, and we are done
Case 2: y is black and its children are both black
We perform a recoloring, equivalent to a fusion, which may propagate up the
double black violation
Case 3: y is red
We perform an adjustment, equivalent to choosing a different representation of a 3-
node, after which either Case 1 or Case 2 applies
59
Deletion (6/9)
Case 1: y is black and has a red child
10
7 15
v
r
5
10
5 15
v
r
7
7
5 10
v
r
15
10
5 7
15
y (a)
y (b)
z (a)
x (c)
z (b)
x (c)
We perform tri-node
restructuring. Color a and c
black, give b the former color of
x, and color r black. This tri-node
restructuring eliminates the
double black problem.
60
Deletion (7/9)
Case 2: The sibling y of r is black and both children of y are black.
10
15 r7
7
5 10
15
y
x
We do a recoloring: color r black, color y red, and, if x is red, color it black; otherwise,
color x double black. After this recoloring, the double black problem may reappear at the
parent x of r.
10
15 r7 y
x
10
15 r7 y
x
10
15 r7 y
x
7 10
5
15
5
5 5
5
61
Deletion (8/9)
Case 3: The sibling y of r is red.
In this case, we perform an adjustment operation as follows:
1. If y is the right child of x, let z be the right child of y; otherwise, let z be the left child of y.
2. Execute the trinode restructuring operation restructure (z), which makes y the parent of
x.
3. Color y black and x red.
An adjustment corresponds to choosing a different representation of a 3-node in the (2,4)
tree. After the adjustment operation, the sibling of r is black, and either Case 1 or Case 2
applies, with a different meaning of x and y. Note that if Case 2 applies, the double-black
problem cannot reappear. Thus, to complete Case 3 we make one more application of either
Case 1 or Case 2 above and we are done. Therefore, at most one adjustment is performed in
a removal operation.
62
Deletion (9/9)
Case 3: The sibling y of r is red.
7 15
r
5
y
x
10
z
7
15 r
5
y
x 10z
63
Red-Black Tree Reorganization
Insertion remedy double red
Red-black tree action (2,4) tree action result
restructuring change of 4-node representation double red removed
recoloring split double red removed or propagated up
Deletion remedy double black
Red-black tree action (2,4) tree action result
restructuring transfer double black removed
recoloring fusion double black removed or propagated up
adjustment change of 3-node representation
restructuring or recoloring
follows 64
Summary
• AVL Trees
• Splay Trees
• (2,4)-Trees
• Read-black Trees
• Suggested reading:
• Sedgewick, Ch.13
65
COMP9024: Data Structures and Algorithms
Contents
AVL Trees
AVL Tree Definition
Height of an AVL Tree
Insertion in an AVL Tree
Trinode Restructuring (1/4)
Trinode Restructuring (Single Rotations) (2/4)
Trinode Restructuring (Double Rotations) (3/4)
Trinode Restructuring (Double Rotations) (4/4)
Insertion Example, continued
Removal in an AVL Tree
Rebalancing after a Removal
Running Times for AVL Trees
Splay Trees
Splay Trees are Binary Search Trees
Searching in a Splay Tree: Starts the Same as in a BST
Example Searching in a BST, continued
Splay Trees do Rotations after Every Operation (Even Search)
Splaying:
Visualizing the Splaying Cases
Splaying Example
Splaying Example, Continued
Example Result of Splaying
Splay Tree Definition
Splay Trees & Ordered Dictionaries
Amortized Analysis of Splay Trees
Cost per zig
Cost per zig-zig and zig-zag
Cost of Splaying
Performance of Splay Trees
(2,4) Trees
Multi-Way Search Tree
Multi-Way Inorder Traversal
Multi-Way Searching
(2,4) Trees
Height of a (2,4) Tree
Insertion
Overflow and Split
Analysis of Insertion
Deletion
Underflow and Fusion
Underflow and Transfer
Analysis of Deletion
Red-Black Trees
From (2,4) to Red-Black Trees
Red-Black Trees
Height of a Red-Black Tree
Insertion
Remedying a Double Red
Restructuring (1/2)
Restructuring (2/2)
Recoloring
Analysis of Insertion
Deletion (1/9)
Deletion (2/9)
Deletion (3/9)
Deletion (4/9)
Deletion (5/9)
Deletion (6/9)
Deletion (7/9)
Deletion (8/9)
Deletion (9/9)
Red-Black Tree Reorganization
Summary