C++ Data Structures and Algorithms

Implementing AVL ADT

By now, we will have the AVL class declaration, as follows:

class AVL : public BST{private:    BSTNode * root;    int GetHeight(BSTNode * node);    BSTNode * RotateLeft(BSTNode * node);    BSTNode * RotateRight(BSTNode * node);    BSTNode * Insert(BSTNode * node, int key);    BSTNode * Remove(BSTNode * node, int key);public:    AVL();    void Insert(int v);    void Remove(int v);};

As we can see in the preceding declaration code, we derive the AVL class from the BST class, which we discussed earlier. So, we just need to define the Insert() and Remove() operations. Also, since we have to maintain the tree's balance, we need to use the RotateLeft() and RotateRight() operations.

We are now going to balance our preceding skewed left BST tree example ...