Transcript CSE 3358 Note Set 1

CSE 3358
NOTE SET 13
Data Structures and Algorithms
Tree Balancing

Binary Search Based Method
 Needed all
data a priori
 Needed a separate array to store data

DSW Algorithm
 In-place
balance
 Still need to have data first
 Or
perform periodically on the tree to re-balance
DSW

Based on two symmetrical rotation operations,
right and left.
rotateRight(Gr, Par, Ch)
If Par is not the root
Gr of Ch becomes Ch’s parent
Right subtree of Ch becomes left subtree of Ch’s parent Par
Ch acquires Par as its right child
Gr
Gr
Par
Ch
P
Ch
R
Q
Par
P
Q
R
DSW Algorithm

Idea
 Convert
any binary tree into a backbone (sometimes
called vine)
 In a series of passes, backbone is transformed into a
perfectly balanced tree
 Repeatedly
rotating every second node of the backbone
about its parent
CreateBackbone(root, n)
tmp = root
while (tmp != 0)
if tmp has left child
rotate this child about tmp
set tmp to the child that just became parent
else
tmp = tmp->right
Example – Convert to Backbone
5
5
tmp
5
10
10
10
15
15
20
15
30
25
23
20
20
40
28
tmp
30
25
23
40
28
tmp
25
30
23
28
40
Example
5
5
10
10
15
15
20
20
23
23
25
25
tmp
30
28
30
28
40
40
tmp
DSW Algorithm
CreatePerfectTree(n)
m = 2floor(lg(n+1))-1
make n – m rotations starting from the top of the backbone
while(m > 1)
m = m/2
make m rotations starting from the top of the backbone