Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Implementing AVL Trees

Having already implemented a binary search tree class, BinarySearchTree, we can make use of much of the existing code to implement an AVL tree class. Program  introduces the AVLTree class which extends the BinarySearchTree class introduced in Program . The AVLTree class inherits most of its functionality from the binary tree class. In particular, it uses the inherited insert and withdraw methods! However, the inherited balance, attachKey and detachKey methods are overridden and a number of new methods are declared.

  
Program: AVLTree class __init__ method.

• Instance Attributes
• __init__ Method
• adjustHeight and getHeight Methods and balanceFactor Property

Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.