4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I have been doing some research, but is it because my push function is being used recursively? Is the recursion of inserting an element slowing down my tree? Not only am I using recursion to insert an element, but I am using it to rotate too. I can see this slowing down my tree real quick. \$\endgroup\$ – SilverSidewalkStew Nov 25 '14 at 23:01
  • \$\begingroup\$ Have you tried std::map \$\endgroup\$ – Martin York Nov 26 '14 at 5:49
3
\$\begingroup\$

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:

unbalanced AVL 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: correctly balanced AVL 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.

\$\endgroup\$
  • \$\begingroup\$ Wow, thank you for your very thorough response. I appreciate this greatly. I did not notice I had an error in my calculations. \$\endgroup\$ – SilverSidewalkStew Nov 28 '14 at 2:06
3
\$\begingroup\$

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;
};
\$\endgroup\$
  • \$\begingroup\$ Wouldn't forward be the most adequate on the second constructor? \$\endgroup\$ – glampert Nov 26 '14 at 16:37
  • \$\begingroup\$ @glampert: Yes thanks. I am still getting used to move semantics. \$\endgroup\$ – Martin York Nov 26 '14 at 17:42
  • \$\begingroup\$ We all are, I guess ;) \$\endgroup\$ – glampert Nov 26 '14 at 17:47
  • \$\begingroup\$ Thank you also for your thorough responses, I appreciate this greatly. This will only better me and give me better insight. \$\endgroup\$ – SilverSidewalkStew Nov 28 '14 at 2:08
1
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Taking a parameter by value and then moving still performs a copy. Also, neither the standard library nor boost uses PascalCase or camelCase, so I wouldn't say that this is the "preferred" style of naming. \$\endgroup\$ – Yuushi Nov 26 '14 at 15:32
  • \$\begingroup\$ @Yuushi, what I meant by a "potentially unnecessary copy" is this: push("hello") - With a const ref, that would create a temp, then copy that temp to its final storage. If you pass by value and move instead, it is just the creation of the temp string plus the cheap move operation. No additional copy involved. \$\endgroup\$ – glampert Nov 26 '14 at 16:29
  • \$\begingroup\$ @Yuushi, about the naming, yes quite arguable. Though I would still avoid snake_case on application code for the exact reason that it is a naming used by standard (or quasi-standard) libraries (Boost, std). snake_case has a standard library feel to it. It seems to me like a good idea to differentiate what belongs to your code from what belongs to the standard lib. \$\endgroup\$ – glampert Nov 26 '14 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.