Tree Balancing
L09 Tree Balancing CX1007 Data Structures 2013/14 S2
Mark Yong
Today • Importance of balance for BSTs • Balancing operaGons in self-‐balancing BSTs • Pseudocode + worked examples
CX1007 Data Structures 2013/14 S2
2
Recall: Why use BSTs? • BSTs are a special form of BT L • At every node, L < C ≤ R – At every node, we always know whether to conGnue searching in the leW or right subtree – If we conGnue searching in the leW subtree, all nodes in the right subtree can be ignored
H E B
A
CX1007 Data Structures 2013/14 S2
C L
F C
R
G
J I
M K
D
3
Recall: Efficient search with BSTs • Search is efficient because we traverse one external path • # operaGons is proporGonal to path length • Try to keep path length low H > D H – Ie, try to keep tree balanced
E
E > D B
A
B < D C
C < D CX1007 Data Structures 2013/14 S2
L F G
J I
M K
D 4
Recall: Efficient search with BSTs • But an imbalanced BST starts to look more like a linked list! • Path length is high A
A
E
B
B C
C E
Mark Yong
Today • Importance of balance for BSTs • Balancing operaGons in self-‐balancing BSTs • Pseudocode + worked examples
CX1007 Data Structures 2013/14 S2
2
Recall: Why use BSTs? • BSTs are a special form of BT L • At every node, L < C ≤ R – At every node, we always know whether to conGnue searching in the leW or right subtree – If we conGnue searching in the leW subtree, all nodes in the right subtree can be ignored
H E B
A
CX1007 Data Structures 2013/14 S2
C L
F C
R
G
J I
M K
D
3
Recall: Efficient search with BSTs • Search is efficient because we traverse one external path • # operaGons is proporGonal to path length • Try to keep path length low H > D H – Ie, try to keep tree balanced
E
E > D B
A
B < D C
C < D CX1007 Data Structures 2013/14 S2
L F G
J I
M K
D 4
Recall: Efficient search with BSTs • But an imbalanced BST starts to look more like a linked list! • Path length is high A
A
E
B
B C
C E