deep-photo-styletransfer

Simple AVL Tree in C++

An AVL tree is a binary search tree(BST) however, unlike binary search trees, an AVL tree (named after Georgy Adelson-Velsky and Evgenii Landis) is self balancing. So no matter how many nodes you insert into the tree, it will adjust it’s branches and ensure the tree is balanced at all times. Making sure the subtree heights only differ by at most 1. BSTs are great for segregating and storing data with a O(log n) search time. Downside with BST is that it can get weighted on one side and doesn’t have an restrictions to prevent it from getting skewed. By switching to an AVL, data is balanced in the tree and the search time is decreased to log n.

So it is more efficient in most cases to use the AVL tree, below is an example of how to code this in C++. Note that the AVL tree uses a lot of the same code the BST did from this post.

#pragma once

#include <iomanip>
#include <iostream>

using namespace std;

class AVL
{
public:
    AVL(){
        root = nullptr;
    }
    ~AVL(){
        destroy(root);
    }
    
    //My Node class for storing data, note how I add height
    struct Node{
        int data;
        Node *left;
        Node *right;
        int height;

        Node(int d){
            data = d;
            left = nullptr;
            right = nullptr;
            height = 0;
        }

        void updateHeight(){
            int lHeight = 0;
            int rHeight = 0;
            if (left != nullptr) {
                lHeight = left->height;
            }
            if (right != nullptr) {
                rHeight = right->height;
            }
            int max = (lHeight > rHeight) ? lHeight : rHeight;
            height = max + 1;
        }

    };

    void insert(int val){
        insert(val, root);
    }

    //Rotate a Node branch to the left, in order to balance things
    Node* rotateLeft(Node *&leaf){
        Node* temp = leaf->right;
        leaf->right = temp->left;
        temp->left = leaf;

        //update the Nodes new height
        leaf->updateHeight();

        return temp;
    }

    //Rotate a Node branch to the right, in order to balance things
    Node* rotateRight(Node *&leaf){
        Node* temp = leaf->left;
        leaf->left = temp->right;
        temp->right = leaf;

        //update the Nodes new height
        leaf->updateHeight();

        return temp;
    }

    //Rotate a Node branch to the right then the left, in order to balance things
    Node* rotateRightLeft(Node *&leaf){
        Node* temp = leaf->right;
        leaf->right = rotateRight(temp);
        return rotateLeft(leaf);
    }

    //Rotate a Node branch to the left then the right, in order to balance things
    Node* rotateLeftRight(Node *&leaf){
        Node* temp = leaf->left;
        leaf->left = rotateLeft(temp);
        return rotateRight(leaf);
    }

    //Function that checks each Node's left and right branches to determine if they are unbalanced
    //If they are, we rotate the branches
    void rebalance(Node *&leaf){
        int hDiff = getDiff(leaf);
        if (hDiff > 1){
            if (getDiff(leaf->left) > 0) {
                leaf = rotateRight(leaf);
            } else {
                leaf = rotateLeftRight(leaf);
            }
        } else if(hDiff < -1) {
            if (getDiff(leaf->right) < 0) {
                leaf = rotateLeft(leaf);
            } else {
                leaf = rotateRightLeft(leaf);
            }
        }
    }

private:
    Node *root;
    //Insert a Node (very similar to BST, except we need to update Node height and then check for rebalance)
    void insert(int d, Node *&leaf){
        if (leaf == nullptr){
            leaf = new Node(d);
            leaf->updateHeight();
        }
        else {
            if (d < leaf->data){
                insert(d, leaf->left);
                leaf->updateHeight();
                rebalance(leaf);
            }
            else{
                insert(d, leaf->right);
                leaf->updateHeight();
                rebalance(leaf);
            }
        }
    }

    //Same as BST
    void destroy(Node *&leaf){
        if (leaf != nullptr){
            destroy(leaf->left);
            destroy(leaf->right);
            delete leaf;
        }
    }
    
    //Get the difference between Node right and left branch heights, if it returns positive
    //We know the left side is greater, if negative, we know the right side is greater
    int getDiff(Node *leaf){
        int lHeight = 0;
        int rHeight = 0;
        if (leaf->left != nullptr) {
            lHeight =  leaf->left->height;
        }
        if (leaf->right != nullptr) {
            rHeight = leaf->right->height
        }
        return lHeight - rHeight;
    }
};

Let me know if you have any issues!

deep-photo-styletransfer

Binary Search Tree Traversals in C++

So this will pretty much wrap up our short expedition into binary trees. Remember that these functions rely on my earlier posts dealing with the class and nodes.

The three types of traversals we will look at are:

  • Preorder (root, left, right)
  • Inorder (left, root, right)
  • Postorder (left, right, root)

Preorder Traversal

This type of traversal can be used to create duplicates of a tree and can be used to implement prefixes. Whatever order of values you put into a tree will be the order that preorder traversal gives you. So If I enter, 5 7 4 2 1 9 8 3 6 into a binary tree, when I use preorder traversal, I will expect to see 5 7 4 2 1 9 8 3 6.

void preorderTraversal (Node* n) {
    if (n != nullptr) { //make sure we have a value
        cout << n->data << endl; //Print out the current Node value
        preorderTraversal(n->left); //traverse down the left side
        preorderTraversal(n->right); //Once we return from the left, go down the right
    }
}

Inorder Traversal

This type of traversal will return data sorted in order. So if I entered, 5 7 4 2 1 9 8 3 6, I would expect to see 1 2 3 4 5 6 7 8 9.

  void inorderTraversal (Node* n) {
    if (n != nullptr) { //make sure we have a value
        inorderTraversal(n->left); //traverse down the left side
        cout << n->data << endl; //Print out the current Node value
        inorderTraversal(n->right); //Once we return from the print, go down the right
    }
}

Postorder Traversal

This type of traversal can be used to implement postfixes and can cleanly be used to destroy a tree with out leaving Nodes floating around corrupting memory. So if I entered, 5 7 4 2 1 9 8 3 6, I would expect to see 1 3 2 4 6 8 9 7 5

 void postorderTraversal (Node* n) {
    if (n != nullptr) { //make sure we have a value
        postorderTraversal(n->left); //traverse down the left side
        postorderTraversal(n->right); //Once we return from the left, go down the right
        cout << n->data << endl; //Print out the current Node value
    }
}

For more information on binary trees, I would checkout this article. It goes into detail on how traversals on called on the tree and gives some great visuals. I also liked this interactive visual for binary search trees in general.

Good luck!