Validating AVL Trees

mgcadmin 05-07-2024

When implementing data structures, its crucial to validate that your implementation is working as expected. A suite of tests is essential to not only debugging, but also optimizing performance one your implementation is correct. In the past I've discussed validation of various of flavors of Red/Black Tree, and in todays post I am going to discuss how we can validate an AVL tree.

AVL Tree's are the oldest self balancing binary search tree, and the main contender to the Red/Black Tree. Like Red/Black trees, AVL trees maintain balance by performing rotations. The decision of when to rotate and which nodes is made by obtaining the balance factor of a given node, and if it exceeds acceptable tolerances, we rotate. For a more detailed discussion of implementing AVL Trees, check my earlier posts on the subject.

There are two properties which we need to check to determine whether a tree is an AVL tree or not: The BST property, and of course, the AVL property. This is done via tree traversal and takes O(N) time. I use recursive preorder traversal for simplicity, but you could also use breadth first traversal, or in order traversal, or which ever tree traversal you like so long as you can compare a node to its two children.

Ensuring the BST Property

The binary search tree property holds that at any given node, the key at the root is greater than all of the keys in its right subtree. Every AVL tree is a binary search tree, and so if the tree being examined is not a binary search tree, it can't be an AVL tree either. Determining whether a given tree is a binary search tree is a straightforward affair, keeping the rules for a BST in mind, the following recursive procedure practically writes its self:

bool validateBST(Node* node) {
     if (node == nullptr)
        return true; //an empty tree is a valid tree.
    if (node->left != nullptr && node->key < node->left->key)
        return false; //In a BST, the left key should be less then the root key.
    if (node->right != nullptr && node->key > node->right->key)
        return false; //In a BST, the right key should be greater than the root key.
    //continue checking the rest of the tree
    return validateBST(node->left) && validateBST(node->right);
}

With that part handled, we can now focus on the real reason we're testing our tree.

Ensuring the AVL Property

The AVL property holds that at any given node, the difference in height between its left and right subtree can be no greater than one. This is done using the same checks used during insertion to determine when to rotate, except instead of rotating, we mark the tree as invalid, as a balanced AVL tree should require no rotations. It should also be noted that we don't need to bother testing the double rotation cases, as they would still fail for the single rotation test. Thus, testing if a tree is a valid AVL tree is as simple as checking is the balance factor is greater than 1 or less then -1:

bool validateAVL(Node* node) {
    if (node == nullptr)
       return true; //An empty tree is balanced.
     
    if (balfactor(node) > 1 || balfactor(node) < -1) {
         return false;
    }
    return validateAVL(node->left) && validateAVL(node->right);
}

And of course, there is no need to traverse the tree twice to validate it, as with red black trees we combine the routines so the checks are done simultaneously:

 
bool validateAVLBST(Node* node) {
    if (node == nullptr)
       return true;
    if (node->left != nullptr && node->key < node->left->key)
        return false; 
    if (node->right != nullptr && node->key > node->right->key)
        return false; 
    if (balfactor(node) > 1 || balfactor(node) < -1)
         return false;
    return validateAVLBST(node->left) && validateAVLBST(node->right);
} 

I wasn't kidding when I said it was a straight forward affair!

 

---