4
\$\begingroup\$

I've implemented an AVL tree using unique_ptr. The code has been stress-tested and there are no crashes or segmentation faults. I left the program running at night and stopped it manually the next morning and there were a couple of millions of iterations and they all were passed.

Just one note: There could be comments about member variables privacy in class Node I just would like to mention that I'm going to implement that.

Any thoughts, comments?

#include <algorithm>
#include <memory>
#include <vector>

class Node {
    public:
        int data;
        Node* parent;
        std::unique_ptr<Node> left;
        std::unique_ptr<Node> right;
    public:
        Node() : data(0) {
            parent = nullptr;
            left = nullptr;
            right = nullptr;
        }
        explicit Node(int d) : data(d),
                               parent(nullptr) {
            left = nullptr;
            right = nullptr;
        }
};

class Avl {
    private:
        size_t current_size;
        Node* root;
    private:
        int height(Node* node);
        Node* get_min(const Node* node);
        Node* inorder_successor(const Node* node);
        void add_helper(Node* parent, Node* node);
        Node* find_helper(const Node* parent_node, const Node* node);
        Node* find_helper(const Node* parent_node, const int data);
        void transplant(Node* node, Node* second_node);
        std::unique_ptr<Node> left_rotate(Node* node);
        std::unique_ptr<Node> right_rotate(Node* node);
        std::unique_ptr<Node> left_right_rotate(Node* node);
        std::unique_ptr<Node> right_left_rotate(Node* node);
        void check_balance(Node* node);
        std::unique_ptr<Node> rebalance(Node* node);
        void traverse_inorder_helper(std::unique_ptr<Node>& node, std::vector<int>& out);
        void traverse_preorder_helper(std::unique_ptr<Node>& node, std::vector<int>& out);
        void traverse_postorder_helper(std::unique_ptr<Node>& node, std::vector<int>& out);
    public:
        Avl() : current_size(0),
                root(nullptr) {}
        ~Avl() {
            delete root;
        }
        void add(Node* node);
        void add(int data);
        Node* find(Node* node);
        Node* find(int data);
        void remove(Node* node);
        void remove(const int& data);
        void destroy();
        void traverse_inorder(std::vector<int>& out);
        void traverse_preorder(std::vector<int>& out);
        void traverse_postorder(std::vector<int>& out);
        size_t size() const {
            return current_size;
        }
        bool empty() const {
            return !(static_cast<bool>(current_size));
        }
};

int Avl::height(Node* node) {
    if(!node) {
        return 0;
    }
    int left = height(node->left.get());
    int right =  height(node->right.get());
    return std::max(left, right) + 1;
}

Node* Avl::get_min(const Node* node) {
    Node* temp = node->right.get();
    while(temp->left) {
        temp = temp->left.get();
    }
    return temp;
}

void Avl::remove(Node* node) {
    Node* successor(nullptr);
    if(!node->left) {
        transplant(node, node->right.get());
        check_balance(node);
    } else if(!node->right) {
        transplant(node, node->left.get());
        check_balance(node);
    } else {
        successor = inorder_successor(node);
        if(successor->parent != node) {
            transplant(successor, successor->right.get());
            check_balance(successor->parent);
            successor->right.release();
            successor->right.reset(node->right.get());
            if(successor->right) {
                successor->right->parent = successor;
            }
        }
        transplant(node, successor);
        successor->left.release();
        successor->left.reset(node->left.get());
        if(successor->left) {
            successor->left->parent = successor;
        }
        successor->parent = node->parent;
        check_balance(successor);
    }
}

void Avl::remove(const int& data) {
    Node* node = find(data);
    if(!node) {
        return;
    }
    Node* successor(nullptr);
    if(!node->left) {
        transplant(node, node->right.get());
        check_balance(node);
    } else if(!node->right) {
        transplant(node, node->left.get());
        check_balance(node);
    } else {
        successor = inorder_successor(node);
        if(successor->parent != node) {
            transplant(successor, successor->right.get());
            check_balance(successor->parent);
            successor->right.release();
            successor->right.reset(node->right.get());
            if(successor->right) {
                successor->right->parent = successor;
            }
        }
        transplant(node, successor);
        successor->left.release();
        successor->left.reset(node->left.get());
        if(successor->left) {
            successor->left->parent = successor;
        }
        successor->parent = node->parent;
        check_balance(successor);
    }
}

Node* Avl::find_helper(const Node* parent_node, const Node* node) {
    if(!parent_node || parent_node->data == node->data) {
        return const_cast<Node*>(parent_node);
    }
    if(node->data > parent_node->data) {
        return find_helper(parent_node->right.get(), node);
    } else if(node->data < parent_node->data) {
        return find_helper(parent_node->left.get(), node);
    }
    return nullptr;
}

Node* Avl::find_helper(const Node* parent_node, const int data) {
    if(!parent_node || data == parent_node->data) {
        return const_cast<Node*>(parent_node);
    }
    if(data > parent_node->data) {
        return find_helper(parent_node->right.get(), data);
    } else if(data < parent_node->data) {
        return find_helper(parent_node->left.get(), data);
    }
    return nullptr;
}

Node* Avl::find(Node* node) {
    return find_helper(root, node);
}

Node* Avl::find(int data) {
    return find_helper(root, data);
}

void Avl::destroy() {
    delete root;
}

void Avl::transplant(Node* node, Node* second_node) 
{
    if(!node->parent) {
        root = second_node;
    }
    if(node->parent && node->parent->right.get() == node) {
        node->parent->right.release();
        node->parent->right.reset(second_node);
    } else if(node->parent && node->parent->left.get() == node) {
        node->parent->left.release();
        node->parent->left.reset(second_node);
    }
    if(node->parent && second_node) {
        second_node->parent = node->parent;
    }
}

Node* Avl::inorder_successor(const Node* node) {
    Node* temp = const_cast<Node*>(node);
    if(temp->right) {
        return get_min(temp);
    }
    Node* parent = temp->parent;
    while(parent && temp == parent->right.get()) {
        temp = parent;
        parent = parent->parent;
    }
    return parent;
}

std::unique_ptr<Node> Avl::left_rotate(Node* node) {
    std::unique_ptr<Node> temp = std::unique_ptr<Node>(new Node);
    temp = std::move(node->right);
    node->right = std::move(temp->left);
    temp->left.reset(node);
    if(node->right.get()) {
        node->right->parent = node;
    }
    temp->parent = node->parent;
    Node* temp_raw = temp.release();
    if(node->parent) {
        if(node == node->parent->left.get()) {
            Node* npl = node->parent->left.release();
            npl = temp_raw;
            node->parent->left.reset(npl);
        } else if(node == node->parent->right.get()) {
            Node* npr = node->parent->right.release();
            npr = temp_raw;
            node->parent->right.reset(npr);
        }
    }
    node->parent = temp_raw;
    return std::unique_ptr<Node>(temp_raw);
}

std::unique_ptr<Node> Avl::right_rotate(Node* node) {
    std::unique_ptr<Node> temp = std::unique_ptr<Node>(new Node);
    temp = std::move(node->left);
    node->left = std::move(temp->right);
    temp->right.reset(node);
    if(node->left.get()) {
        node->left->parent = node;
    }
    temp->parent = node->parent;
    Node* temp_raw = temp.release();
    if(node->parent) {
        if(node == node->parent->left.get()) {              
            Node* npl = node->parent->left.release();
            npl = temp_raw;
            node->parent->left.reset(npl);
        } else if(node == node->parent->right.get()) {
            Node* npr = node->parent->right.release();
            npr = temp_raw;
            node->parent->right.reset(npr);
        }
    }
    node->parent = temp_raw;       
    return std::unique_ptr<Node>(temp_raw);
}

std::unique_ptr<Node> Avl::left_right_rotate(Node* node) {
    Node* left = node->left.release();
    node->left = std::move(left_rotate(left));
    return right_rotate(node);

}

std::unique_ptr<Node> Avl::right_left_rotate(Node* node) {
    Node* right = node->right.release();
    node->right = std::move(right_rotate(right));
    return left_rotate(node);
}

void Avl::add_helper(Node* parent, Node* node) {
    if(node->data > parent->data) {
        if(!parent->right.get()) {
            parent->right.reset(node);
            node->parent = parent;
            ++current_size;
        } else {                
            add_helper(parent->right.get(), node);
        }
    } else if(node->data < parent->data) {
        if(!parent->left.get()) {
            parent->left.reset(node);
            node->parent = parent;
            ++current_size;
        } else {
            add_helper(parent->left.get(), node);
        }

    } else {
        return;
    }
    check_balance(node);
    return;
}

void Avl::add(Node* node) {
    if(!root) {
        root = node;
        return;
    }
    add_helper(root, node);
}

void Avl::add(int data) {
    if(!root) {
        root = new Node(data);
        return;
    }        
    Node* node = new Node(data);
    add_helper(root, node);
}

void Avl::check_balance(Node* node) {
    int left = height(node->left.get());
    int right = height(node->right.get());
    if(left - right > 1 || left - right < -1) {
        std::unique_ptr<Node> uptr = std::move(rebalance(node));
        node = uptr.release();
    } 
    if(!node->parent) {
        return;
    }
    check_balance(node->parent);
}

std::unique_ptr<Node> Avl::rebalance(Node* node) {
    int left = height(node->left.get());
    int right = height(node->right.get());
    std::unique_ptr<Node> uptr = std::unique_ptr<Node>();
    if(left - right > 1) {
        if(height(node->left->left.get()) >= height(node->left->right.get())) {
            uptr = std::move(right_rotate(node));
        } else {
            uptr = std::move(left_right_rotate(node));
        }

    }
    left = height(node->left.get());
    right = height(node->right.get());
    if(left - right < -1) {
        if(height(node->right->right.get()) >= height(node->right->left.get())) {
            uptr = std::move(left_rotate(node));                
        } else {
            uptr = std::move(right_left_rotate(node));
        }
    }       
    if(!uptr->parent) {
        root = uptr.release();
        return std::unique_ptr<Node>(root);
    }
    return uptr;
}

void Avl::traverse_inorder(std::vector<int>& out) {
    std::unique_ptr<Node> root_ptr(root);
    traverse_inorder_helper(root_ptr, out);
    root = root_ptr.release();
}

void Avl::traverse_preorder(std::vector<int>& out) {
    std::unique_ptr<Node> root_ptr(root);
    traverse_preorder_helper(root_ptr, out);
    root = root_ptr.release();
}

void Avl::traverse_postorder(std::vector<int>& out) {
    std::unique_ptr<Node> root_ptr(root);
    traverse_postorder_helper(root_ptr, out);
    root = root_ptr.release();
}

void Avl::traverse_inorder_helper(std::unique_ptr<Node>& node, std::vector<int>& out) {
    if(!node) {
        return;
    }
    traverse_inorder_helper(node->left, out);
    out.push_back(node->data);
    traverse_inorder_helper(node->right, out);
}

void Avl::traverse_preorder_helper(std::unique_ptr<Node>& node, std::vector<int>& out) {
    if(!node) {
        return;
    }
    out.push_back(node->data);
    traverse_preorder_helper(node->left, out);
    traverse_preorder_helper(node->right, out);
}

void Avl::traverse_postorder_helper(std::unique_ptr<Node>& node, std::vector<int>& out) {
    if(!node) {
        return;
    }
    traverse_postorder_helper(node->left, out);
    traverse_postorder_helper(node->right, out);
    out.push_back(node->data);
}

Here is a given a minimal version of the stress-test code. As a golden has been used rosetta-avl:

#include <ctime>
#include <vector>
#include <iostream>

#include "../src/mset.hpp"
#include "../shared_src/avl.h"

int generate_random_int(int min, int max) {
    return min + (rand() % (int)(max - min + 1));
}

void generate_random_vector(std::vector<int>& out, const int min, 
        const int max, const size_t max_size) {
    size_t size = generate_random_int(0, max_size);
    for(size_t i = 0; i < size; ++i) {  
        int num = generate_random_int(min, max);
        out.push_back(num);
    }
}

void show(const std::vector<int>& out) {
    for(int i = 0; i < out.size(); ++i) {
        std::cout << out[i] << ", ";
    }
    std::cout << "\n";
}

void init_sets(Avl* set, AVLtree<int>* set_golden, int min, int max, size_t max_size) {
    std::vector<int> out;
    generate_random_vector(out, min, max, max_size);   
    for(auto const& item : out) {
        set->add(item);
        set_golden->insert(item);
    }
    if(!out.empty()) {
        size_t random_index = generate_random_int(0, out.size() - 1);
#ifdef DEBUG
        std::cout << "The initial vector:\n\t";
        show(out);
#endif
        set->remove(out[random_index]);
        set_golden->deleteKey(out[random_index]);
#ifdef DEBUG
        std::cout << "The removed element:\n\t";
        std::cout << out[random_index] << "\n";
#endif
    }
}

bool stress_test(const int min, const int max, const size_t max_size) {
    int i = 0;
    while(1) {  
        Avl* set = new Avl();
        AVLtree<int>* set_golden = new AVLtree<int>();
        std::cout << "##############################################" << "\n";
        init_sets(set, set_golden, min, max, max_size);
        std::vector<int> out;
        //set->traverse_preorder(out);
        set->traverse_postorder(out);
        std::vector<int> out_golden;
        //set_golden->preorder(out_golden);
        set_golden->postorder(out_golden);
        if(out == out_golden) {
            std::cout << "PASS\n ";
        } else {
            std::cout << "FAIL\n ";
            break;
        }
        std::cout << "\tout: ";
        show(out);
        std::cout << "\tgolden: ";
        show(out_golden);
        std::cout << "\n";
        std::cout << "##############################################" << "\n";
        delete set;
        delete set_golden;
        std::cout << "Iteration: " << i << "\n";
        ++i;        
    }  
    return 0;
}

int main() {    
    int result = stress_test(0, 1000000000, 1000);  
}
\$\endgroup\$
2
  • \$\begingroup\$ Could you provide a test case, showing this code in action? \$\endgroup\$
    – dfhwze
    Commented Jun 23, 2019 at 14:51
  • \$\begingroup\$ dfhwze - I've added a test case. Please see the below-given code. \$\endgroup\$ Commented Jun 23, 2019 at 15:15

1 Answer 1

6
\$\begingroup\$

Prefer default member initialization

You can use default member initialization to avoid repeating common initialization in the constructors. Also, std::unique_ptr will already initialize itself, there is no need to do this explicitly. So:

class Node {
        int data{};
        Node* parent{};
        std::unique_ptr<Node> left;
        std::unique_ptr<Node> right;

    public:
        Node() = default;
        explicit Node(int d) : data(d) {}
};

Move class Node inside class Avl

Class Node is just an implementation detail of Avl. Move it inside class Avl, this will also avoid polluting the global namespace with the very generic name Node. This might require you to write Avl::Node in some places. So:

class Avl {
public:
    class Node {
        ...
    };

    ...
};

Make member functions that do not modify the tree const

This helps the compiler generate better code, and will let the compiler report an error if you accidentily do modify any of the member variables of Avl. For example, height() doesn't modify the tree, so it should be marked const:

int height(const Node* node) const;

There are many more functions that can be made const. You do seem to know about this because you did it for size() and empty().

Avoid unnecessary initialization

Initializing a std::unique_ptr with a default constructed temporary is redundant. Instead of:

std::unique_ptr<Node> uptr = std::unique_ptr<Node>();

Just write:

std::unique_ptr<Node> uptr;

Use std::make_unique to construct new Nodes

You can avoid manual calls to new and repeating types by using auto and std::make_unique. For exampe, instead of writing:

std::unique_ptr<Node> temp = std::unique_ptr<Node>(new Node);

You can write:

auto temp = std::make_unique<Node>();

Make use of std::unique_ptr's automatic pointer moving functionality

I see you use release() and reset() a lot, but instead of manually releasing pointers, you can make use of the fact that assigning one std::unique_ptr will do all these tasks automatically for you. For example, instead of:

successor->right.release();
successor->right.reset(node->right.get());

You can just write:

successor->right.reset(node->right.get());

The call to reset() already implies that it will release the old pointer. Furthermore, instead of:

Node* temp_raw = temp.release();
Node* npl = node->parent->left.release();
npl = temp_raw;
node->parent->left.reset(npl);

You can write:

node->parent->left = std::move(temp);

Since the move assignment operator will take care of releasing correctly for both the left and right hand side. You can also do this in a return statement. So instead of:

root = uptr.release();
return std::unique_ptr<Node>(root);

Just write:

return std::move(uptr);

Finally, you can also use std::swap() if you need to swap two std::unique_ptrs, so instead of:

std::unique_ptr<Node> temp = std::unique_ptr<Node>(new Node);
temp = std::move(node->right);
node->right = std::move(temp->left);
temp->left.reset(node);

You can write:

auto temp = std::make_unique<Node>();
std::swap(node->right, temp->left);

Consider avoiding signed integers for things that cannot be negative

You store the height as an int. However, a negative height for an AVL tree does not make sense. You could make it an unsigned int instead. This does mean a little care is necessary, for example instead of:

if(left - right > 1 || left - right < -1) {

You should write:

if(left > right + 1 || right > left + 1) {

On the other hand, it's only used internally, using unsigned int might actually introduce a bug if you don't take care of wraparound if you subtract values, and the height is only ever a very small value, so this is just me being very pedantic.

Expose iterators for tree traversal

The functions for traversing the tree are particularly bad. They force the use of a std::vector that will contain a copy of all the data, which wastes memory and potentially time if not all elements are going to be necessary. Also, ideally you would want to write something like this:

Avl tree;
...
for (auto &item: tree.pre_order()) {
    std::cout << item << ", ";
}

This would require you to write classes that represents the in-order, pre-order and post-order views of the tree, and each of these classes would contain a begin() and end() member function that return iterators that will iterate in the given order. I would also make the Avl class itself expose begin() and end() that do in-order traversal, so you get the items in sorted order, as you would expect from a std::set for example.

Consider making it look more like a STL container

You already have some member function names that are the same as those used in STL containers, such as empty(), size(), and remove(). Some others can be renamed to match the STL naming conventions:

  • add() -> insert()`
  • destroy() -> clear()

Also consider adding functions from std::set, such as equal_range(), lower_bound(), and so on. Furthermore, add a constructor that takes an initializer list of elements to add to the tree, so you can write:

Avl tree{3, 6, 2, 9};

Consider making this a template

Your AVL tree can only store ints. Consider making it a template, so you can store different types, and perhaps have a different comparison function as well.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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