AVL tree for inserting and searching

Question

I have made an AVL tree. It works and does what it needs to do. I only need it to insert and search. I am comparing how long it takes to load and search a dictionary file in relation to other various data structures. My AVL tree takes 25 seconds to load the file.

This is in comparison to hash tables that took only three.

Is there any way I can make it faster?

MyDS stands for "My Data Structure", in case anyone was wondering.

//MyDS.h

#ifndef MyDS_H
#define MyDS_H
#include <iostream>
#include <string>


class MyDS {
private:
    struct treeNode
    {
        treeNode* left;
        treeNode* right;
        int height;
        std::string data;
        treeNode() {left = NULL; right = NULL;};
        treeNode(const std::string &v, treeNode* l, treeNode* r, int h){data = v; left = l;  right = r; height = h;};
    };

    treeNode* root;
    void push(const std::string & n, treeNode * & v);
    bool search( const std::string& s, treeNode * & tree) ;
public:
    MyDS();
    ~MyDS();
    void push(const std::string & n);
    void printPreOrder() const;
    void preOrder(treeNode* pre) const;
    void clear(treeNode* & tree);
    void singleRightRotate(treeNode * & n);
    void doubleRightRotate(treeNode * & n);
    void singleLeftRotate(treeNode * & n);
    void doubleLeftRotate(treeNode * & n);
    bool search(const std::string & s);
    int avlHeight (treeNode * h);
    int max(int v1, int v2);
};
MyDS::MyDS()
{
    root = NULL;

}

MyDS::~MyDS()
{
    clear(root);
}

void MyDS::push(const std::string & n)
{
    push(n,root);
}

void MyDS::singleRightRotate(treeNode * & n)
{
    treeNode * temp;
    temp = n->right;
    n->right = temp->left;
    temp->left = n;
    n = temp;
    n->height = max(avlHeight(n->left),avlHeight(n->right)) + 1;
    temp->height = max(n->height,avlHeight(temp->right)) + 1;


}

void MyDS::singleLeftRotate(treeNode * & n)
{
    treeNode * temp;
    temp = n->left;
    n->left = temp->right;
    temp->right = n;
    n = temp;
    n->height = max(avlHeight(n->left),avlHeight(n->right)) + 1;
    temp->height = max(avlHeight(temp->left),n->height) + 1;
}

void MyDS::doubleRightRotate(treeNode * & n)
{
    singleLeftRotate(n->right);
    singleRightRotate(n);
}

void MyDS::doubleLeftRotate(treeNode * & n)
{
    singleRightRotate(n->left);
    singleLeftRotate(n);
}

int MyDS::max(int v1, int v2)
{
    return ((v1 > v2) ? v1 : v2);
}

int MyDS::avlHeight(treeNode * h)
{
    int n;
    if( h == NULL)
    {
        return -1;
    }
    else
    {
        n = h->height;
        return n;
    }

}


bool MyDS::search(const std::string& s, treeNode *& tree)
{
    if(tree == NULL)
    {
        return false;
    }
    else if(s < tree->data)
    {
        return search(s, tree->left);
    }
    else if(tree->data < s)
    {
        return search(s, tree->right);
    }
    else
    {
        ;
    }
}

bool MyDS::search(const std::string &x)
{
    if (search(x, root)){
        return true;
    }
    else
        return false;
}

void MyDS::clear(treeNode* & tree)
{
    if(tree != NULL)
    {
        clear(tree->left);
        clear(tree->right);
        delete tree;

    }

    tree = NULL;
}

void MyDS::push(const std::string & n, treeNode* & v)
{
    if (v == NULL)
    {
        v = new treeNode(n , NULL, NULL, 0);
    }
    else
    {
        if ( n < v->data)
        {
            push(n, v->left);   // goes to left node

            if ((avlHeight(v->left) - avlHeight(v->right))==2)
            {
                if (n < v->left->data)
                {
                    singleLeftRotate(v);
                }
                else
                {
                    doubleLeftRotate(v);
                }
            }
        }
        else if ( v->data < n)
        {
            push(n, v->right);  // goes to right node
            if ((avlHeight(v->right) - avlHeight(v->left))==2)
            {
                if (n > v->right->data)
                {
                    singleRightRotate(v);
                }
                else
                {
                    doubleRightRotate(v);
                }
            }
        }
        else
        {
            ; // duplicate; do nothing.
        }
    }
    int a,b,c;
    a = avlHeight(v->left);
    b = avlHeight(v->right);
    c = max(a,b);
    v->height = c + 1;

}

void MyDS::printPreOrder() const
{
    preOrder(root);
}


void MyDS::preOrder(treeNode* pre) const
{
    if(pre != NULL)
    {
        std::cout << " " << pre->data << " ";
        preOrder(pre->left);
        preOrder(pre->right);
    }
}
#endif

Answer 1

In addition to the things that others have already written, I thought I would add a few things that will help you improve your code.

Fix height recalculations after rotations

I added some instrumentation to your code. In particular, I added these three functions:

void MyDS::preOrder(std::ostream &out, treeNode* pre) const
{
    if(pre != NULL)
    {
        out << pre->data << "[label=\"" << pre->data 
            << "\\n" << avlHeight(pre) << "\"];\n";
        if (pre->left)
            out << pre->data << " -> " 
                << pre->left->data << ";\n";
        if (pre->right)
            out << pre->data << " -> " 
                << pre->right->data << ";\n";
        preOrder(out, pre->left);
        preOrder(out, pre->right);
    }
}

std::string MyDS::dot() const 
{
    std::stringstream stm;
    stm << "digraph {\n";
    preOrder(stm, root);
    stm << "}\n";
    return stm.str();
}

void MyDS::display() const 
{
    std::ofstream out("/tmp/out.gv");
    out << dot() << std::endl;
    out.close();
    system("dot -Tpng /tmp/out.gv -o /tmp/out.png");
    system("eog /tmp/out.png");
}

These were implemented to create a graphical representation of the tree using dot. I then wrote this test routine:

int main()
{
    std::string months[]{"January", "February", "March", "April", 
        "May", "June", "July", "August", "September", 
        "October", "November", "December"};
    MyDS tree;
    for (const auto &mon : months) {
        tree.push(mon);
        tree.display();
    }
}

When I run the program, it inserts the names of the months in English into the tree. Everything works OK until we insert November, which results in this tree:

This tree is unbalanced and the heights are incorrect on the left side of the tree, so there is an error in the code. In a proper AVL tree, the heights of the child subtrees differ at most by one, but in this tree, the right node has a depth of 2 higher than the right node. There should have been a left rotation through the root node.

The problem is in the code for the single rotations. The code for singleRightRotate ends with these three lines:

n = temp;
n->height = max(avlHeight(n->left),avlHeight(n->right)) + 1;
temp->height = max(n->height,avlHeight(temp->right)) + 1;

However, that's not correct since you're recalculating the height of n immediately after assigning it a new value. It should be done before as with this code:

n->height = max(avlHeight(n->left),avlHeight(n->right)) + 1;
n = temp;
temp->height = max(n->height,avlHeight(temp->right)) + 1;

The same fix needs to be applied to singleLeftRotate.

When this is done we get the correct tree:

Use const where possible

The avlHeight and search functions do not (and should not) alter the tree and should therefore be declared const.

Speed testing

Note that testing the speed of AVL tree insertion with a sorted list (as a dictionary file usually is) is going to tend to be slow because AVL trees will have to do many rotations due to the sorted input. A better test would be to use a file of unsorted words. On this machine, I read in the text of Dracula, by Bram Stoker into the AVL tree and emitted the sorted list (with a function inOrder that I added to the code) in less than 300ms. That text contains 164423 words, 19028 of which are unique.

Doing the same thing with the words file on my machine (479828 unique words) took 1.44 seconds.

Answer 2

Personally I would move memory management from MyDS into the tree structure (disable the assignment and copy constructor just to remove the possibility of incorrect usage. Add a constructor that moves the data into the tree.

struct treeNode
{
    std::string data;
    int height;
    treeNode* left;
    treeNode* right;

    treeNode()
    {
        delete left;
        delete right;
    };
    treeNode(std::string const& v, treeNode* l, treeNode* r, int h)
        : data(v)
        , height(h)
        , left(l)
        , right(r)
    {}
    treeNode(std::string&& v, treeNode* l, treeNode* r, int h)
        : data(std::forward(v))
        , height(h)
        , left(l)
        , right(r)
    {}
    treeNode(treeNode const&)            = delete;
    treeNode& operator=(treeNode const&) = delete;
};

Answer 3

Cool, you plan on using C++11, so things your should try:

• Use nullptr, the modern way to initialize a null pointer in C++.

• Get familiar with move semantics and move constructors. push() should be provided with a version that takes the string by move ref (std::string &&) or just take the string by value and move it inside the function. This would eliminate the potentially unnecessary copy it currently does.

---

Default constructor of treeNode

treeNode() {left = NULL; right = NULL;};

is not initializing the height field. This seems like a bug or the beginning of one.

Also, you should initialize data in constructors by calling the constructors of the sub-objects:

treeNode() 
    : left(nullptr), right(nullptr), height(0) { } // <--- No ';' here BTW!

With C++11 you can directly initialize data members, which can help avoiding errors like forgetting to init a certain field:

struct treeNode
{
    treeNode*   left   = nullptr;
    treeNode*   right  = nullptr;
    int         height = 0;
    std::string data;

    treeNode(std::string v, treeNode* l, treeNode* r, int h)
        : data(std::move(v)), left(l), right(r), height(h) { }
};

The above code also shown an instance of std::move() for data.

---

You have implemented a max() function, whereas you could have used std::max().

---

On MyDS::search() since each if statement returns from the function, don't build-up the long if-then-else chain, keep it simple:

bool MyDS::search(const std::string& s, treeNode *& tree)
{
    if(tree == NULL)
    {
        return false;
    }
    if(s < tree->data)
    {
        return search(s, tree->left);
    }
    if(tree->data < s)
    {
        return search(s, tree->right);
    }
    return true; // We found the value.
}

EDIT: Before @LokiAstari's edit, I had not realized that MyDS::search() is actually broken. The final else case is not explicitly returning a value, which means the return value of the function, when it gets there, is going to be random. Sometimes true, others false. Basically undefined behavior. That should produce a warning on any respectable compiler, so keep and eye out!

---

The MyDS::preOrder printing method could take an std::ostream so that you are not bound to always printing to cout. But actually, an output operator << would be even nicer.

---

Finally, a little word on naming:

I don't se the reason for not naming the class AvlTree or similar. MyDS is a very vague name that you would never use on a real life scenario. So why not give it a proper name?

treeNode is not using the best naming convention I'd say. camelCase is commonly applied to method/function names and variable names. PascalCase is the most commonly used naming for types (structs, classes, typedefs, and such).