Module 0102: Good trees, bad trees and ugly trees

Module 0102: Good trees, bad trees and ugly trees

Tak Auyeung, Ph.D.

December 4, 2006

1 About this module
2 Metrics
3 The good, the bad and the ugly
3.1 The good
3.2 The bad
3.3 The ugly
4 Balancing act
4.1 Remove node
4.2 Make alias
5 AVL tree
5.1 Representation
5.2 Initialization
5.3 Make empty
5.4 Getting and setting ‘h’
5.5 Insertion
  5.5.1 Out of balance
  5.5.2 Where is the lowest leaf?
  5.5.3 Rebalance implementation
  5.5.4 Debugging tree code
5.6 Deletion, in general
5.7 Deletion for an AVL tree