### CSCI 2720

```Data Structures
Balanced Trees
CSCI 2720
Spring 2007
Outline
 Balanced Search Trees
•
2-3 Trees
•
2-3-4 Trees
•
Red-Black Trees
CSCI 2720
Slide 2
Same entries, different insertion sequence:
 Not good! Would like to keep tree balanced.
CSCI 2720
Slide 3
2-3 Trees
Features
 each internal node has either 2 or 3 children
 all leaves are at the same level
CSCI 2720
Slide 4
2-3 Trees with Ordered Nodes
2-node
3-node
• leaf node can be either a 2-node or a 3-node
CSCI 2720
Slide 5
Example of 2-3 Tree
CSCI 2720
Slide 6
Traversing a 2-3 Tree
inorder(in ttTree: TwoThreeTree)
if(ttTree’s root node r is a leaf)
visit the data item(s)
else if(r has two data items)
{
inorder(left subtree of ttTree’s root)
visit the first data item
inorder(middle subtree of ttTree’s root)
visit the second data item
inorder(right subtree of ttTree’s root)
}
else
{
inorder(left subtree of ttTree’s root)
visit the data item
inorder(right subtree of ttTree’s root)
}
CSCI 2720
Slide 7
Searching a 2-3 Tree
retrieveItem(in ttTree: TwoThreeTree,
in searchKey:KeyType,
out treeItem:TreeItemType):boolean
if(searchKey is in ttTree’s root node r)
{
treeItem = the data portion of r
return true
}
else if(r is a leaf)
return false
else
{
return retrieveItem(appropriate subtree,
searchKey, treeItem)
}
CSCI 2720
Slide 8
What did we gain?
What is the time efficiency of searching for an item?
CSCI 2720
Slide 9
Gain: Ease of Keeping the Tree Balanced
Binary Search
Tree
both trees after
inserting items
39, 38, ... 32
2-3 Tree
CSCI 2720
Slide 10
Inserting Items
Insert 39
CSCI 2720
Slide 11
Inserting Items
Insert 38
insert in leaf
divide leaf
and move middle
value up to parent
result
CSCI 2720
Slide 12
Inserting Items
Insert 37
CSCI 2720
Slide 13
Inserting Items
Insert 36
insert in leaf
divide leaf
and move middle
value up to parent
overcrowded
node
CSCI 2720
Slide 14
Inserting Items
... still inserting 36
divide overcrowded node,
move middle value up to parent,
attach children to smallest and largest
result
CSCI 2720
Slide 15
Inserting Items
After Insertion of 35, 34, 33
CSCI 2720
Slide 16
Inserting so far
CSCI 2720
Slide 17
Inserting so far
CSCI 2720
Slide 18
Inserting Items
How do we insert 32?
CSCI 2720
Slide 19
Inserting Items
 creating a new root if necessary
 tree grows at the root
CSCI 2720
Slide 20
Inserting Items
Final Result
CSCI 2720
Slide 21
Deleting Items
Delete 70
70
80
CSCI 2720
Slide 22
Deleting Items
Deleting 70: swap 70 with inorder successor (80)
CSCI 2720
Slide 23
Deleting Items
Deleting 70: ... get rid of 70
CSCI 2720
Slide 24
Deleting Items
Result
CSCI 2720
Slide 25
Deleting Items
Delete 100
CSCI 2720
Slide 26
Deleting Items
Deleting 100
CSCI 2720
Slide 27
Deleting Items
Result
CSCI 2720
Slide 28
Deleting Items
Delete 80
CSCI 2720
Slide 29
Deleting Items
Deleting 80 ...
CSCI 2720
Slide 30
Deleting Items
Deleting 80 ...
CSCI 2720
Slide 31
Deleting Items
Deleting 80 ...
CSCI 2720
Slide 32
Deleting Items
Final Result
comparison with
binary search tree
CSCI 2720
Slide 33
Deletion Algorithm I
Deleting item I:
1. Locate node n, which contains item I
2. If node n is not a leaf  swap I with inorder successor
 deletion always begins at a leaf
3. If leaf node n contains another item, just delete item I
else
try to redistribute nodes from siblings (see next slide)
if not possible, merge node (see next slide)
CSCI 2720
Slide 34
Deletion Algorithm II
Redistribution
A sibling has 2 items:
 redistribute item
between siblings and
parent
Merging
No sibling has 2 items:
 merge node
 move item from parent
to sibling
CSCI 2720
Slide 35
Deletion Algorithm III
Redistribution
Internal node n has no item left
 redistribute
Merging
Redistribution not possible:
 merge node
 move item from parent
to sibling
 adopt child of n
If n's parent ends up without item, apply process recursively
CSCI 2720
Slide 36
Deletion Algorithm IV
If merging process reaches the root and root is without item
 delete root
CSCI 2720
Slide 37
Operations of 2-3 Trees
all operations have time complexity of log n
CSCI 2720
Slide 38
2-3-4 Trees
• similar to 2-3 trees
• 4-nodes can have 3 items and 4 children
4-node
CSCI 2720
Slide 39
2-3-4 Tree Example
CSCI 2720
Slide 40
2-3-4 Tree: Insertion
Insertion procedure:
• similar to insertion in 2-3 trees
• items are inserted at the leafs
• since a 4-node cannot take another item,
4-nodes are split up during insertion process
Strategy
• on the way from the root down to the leaf:
split up all 4-nodes "on the way"
 insertion can be done in one pass
(remember: in 2-3 trees, a reverse pass might be necessary)
CSCI 2720
Slide 41
2-3-4 Tree: Insertion
Inserting 60, 30, 10, 20, 50, 40, 70, 80, 15, 90, 100
CSCI 2720
Slide 42
2-3-4 Tree: Insertion
Inserting 60, 30, 10, 20 ...
... 50, 40 ...
CSCI 2720
Slide 43
2-3-4 Tree: Insertion
Inserting 50, 40 ...
... 70, ...
CSCI 2720
Slide 44
2-3-4 Tree: Insertion
Inserting 70 ...
... 80, 15 ...
CSCI 2720
Slide 45
2-3-4 Tree: Insertion
Inserting 80, 15 ...
... 90 ...
CSCI 2720
Slide 46
2-3-4 Tree: Insertion
Inserting 90 ...
... 100 ...
CSCI 2720
Slide 47
2-3-4 Tree: Insertion
Inserting 100 ...
CSCI 2720
Slide 48
2-3-4 Tree: Insertion Procedure
Splitting 4-nodes during Insertion
CSCI 2720
Slide 49
2-3-4 Tree: Insertion Procedure
Splitting a 4-node whose parent is a 2-node during insertion
CSCI 2720
Slide 50
2-3-4 Tree: Insertion Procedure
Splitting a 4-node whose parent is a 3-node during insertion
CSCI 2720
Slide 51
2-3-4 Tree: Deletion
Deletion procedure:
• similar to deletion in 2-3 trees
• items are deleted at the leafs
 swap item of internal node with inorder successor
• note: a 2-node leaf creates a problem
Strategy
(different strategies possible)
• on the way from the root down to the leaf:
turn 2-nodes (except root) into 3-nodes
 deletion can be done in one pass
(remember: in 2-3 trees, a reverse pass might be necessary)
CSCI 2720
Slide 52
2-3-4 Tree: Deletion
Turning a 2-node into a 3-node ...
Case 1: an adjacent sibling has 2 or 3 items
 "steal" item from sibling by rotating items and moving subtree
30 50
20 50
40
10 20
30 40
10
"rotation"
25
25
CSCI 2720
Slide 53
2-3-4 Tree: Deletion
Turning a 2-node into a 3-node ...
Case 2: each adjacent sibling has only one item
 "steal" item from parent and merge node with sibling
(note: parent has at least two items, unless it is the root)
30 50
50
40
10
10 30 40
merging
25
35
25
35
CSCI 2720
Slide 54
2-3-4 Tree: Deletion Practice
Delete 32, 35, 40, 38, 39, 37, 60
CSCI 2720
Slide 55
Red-Black Tree
• binary-search-tree representation of 2-3-4 tree
• 3- and 4-nodes are represented by equivalent binary trees
• red and black child pointers are used to distinguish between
original 2-nodes and 2-nodes that represent 3- and 4-nodes
CSCI 2720
Slide 56
Red-Black Representation of 4-node
CSCI 2720
Slide 57
Red-Black Representation of 3-node
CSCI 2720
Slide 58
Red-Black Tree Example
CSCI 2720
Slide 59
Red-Black Tree Example
CSCI 2720
Slide 60
Red-Black Tree Operations
Traversals
 same as in binary search trees
Insertion and Deletion
 analog to 2-3-4 tree
 need to split 4-nodes
 need to merge 2-nodes
CSCI 2720
Slide 61
Splitting a 4-node that is a root
CSCI 2720
Slide 62
Splitting a 4-node whose parent is a 2-node
CSCI 2720
Slide 63
Splitting a 4-node whose parent is a 3-node
CSCI 2720
Slide 64
Splitting a 4-node whose parent is a 3-node
CSCI 2720
Slide 65
Splitting a 4-node whose parent is a 3-node
CSCI 2720
Slide 66
```