1
\$\begingroup\$

I have implemented an AVL tree using shared_ptr. I know that there is an overhead regarding using shared_ptr and instead a unique_ptr could be used. But the thing is that my node contains also a parent pointer, it turns out so each node can be pointed by two/three other nodes at the same time, one pointer from its parent and the second/third from his child nodes and I can't replace shared_ptr with unique_ptr. Any thoughts about this? The code is shown below:

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

class Node {
    public:
        int data;
        std::shared_ptr<Node> left;
        std::shared_ptr<Node> right;
        std::shared_ptr<Node> parent;
    public:
        Node() : data(0) {}
        explicit Node(int d) : data(d) {}
};

class Avl {
    private:
        size_t current_size;
        std::shared_ptr<Node> root;
    private:
        int height(std::shared_ptr<Node> node);
        std::shared_ptr<Node> get_min(std::shared_ptr<Node> node);
        std::shared_ptr<Node> inorder_successor(std::shared_ptr<Node> node);
        void add_helper(std::shared_ptr<Node> parent, std::shared_ptr<Node> node);
        std::shared_ptr<Node> find_helper(std::shared_ptr<Node> parent_node, std::shared_ptr<Node> node);
        std::shared_ptr<Node> find_helper(std::shared_ptr<Node> parent_node, int data);
        void destroy_helper(std::shared_ptr<Node>& node);
        void transplant(std::shared_ptr<Node> node, std::shared_ptr<Node> second_node);
        std::shared_ptr<Node> left_rotate(std::shared_ptr<Node> node);
        std::shared_ptr<Node> right_rotate(std::shared_ptr<Node> node);
        std::shared_ptr<Node> left_right_rotate(std::shared_ptr<Node> node);
        std::shared_ptr<Node> right_left_rotate(std::shared_ptr<Node> node);
        void check_balance(std::shared_ptr<Node> node);
        std::shared_ptr<Node> rebalance(std::shared_ptr<Node> node);
        void traverse_inorder_helper(std::shared_ptr<Node> node, std::vector<int>& out);
        void traverse_preorder_helper(std::shared_ptr<Node> node, std::vector<int>& out);
        void traverse_postorder_helper(std::shared_ptr<Node> node, std::vector<int>& out);
    public:
        Avl() : current_size(0) {}
        void add(std::shared_ptr<Node> node);
        void add(int data);
        std::shared_ptr<Node> find(std::shared_ptr<Node> node);
        std::shared_ptr<Node> find(int data);
        void remove(std::shared_ptr<Node> node);
        void remove(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);
        inline size_t size() const {
            return current_size;
        }
        inline bool empty() const {
            return !(static_cast<bool>(current_size));
        }
};

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

std::shared_ptr<Node> Avl::get_min(std::shared_ptr<Node> node) {
    std::shared_ptr<Node> temp = node->right;
    while(temp->left) {
        temp = temp->left;
    }
    return temp;
}

void Avl::remove(std::shared_ptr<Node> node) {
    if(!node->left) {
        transplant(node, node->right);
        check_balance(node);
    } else if(!node->right) {
        transplant(node, node->left);
        check_balance(node);
    } else {
        std::shared_ptr<Node> successor = inorder_successor(node);
        if(successor->parent != node) {
            transplant(successor, successor->right);
            check_balance(successor->parent);
            successor->right = node->right;
            if(successor->right) {
                successor->right->parent = successor;
            }
        }
        transplant(node, successor);
        successor->left = node->left;
        if(successor->left) {
            successor->left->parent = successor;
        }
        successor->parent = node->parent;
        check_balance(successor);
    }
}

void Avl::remove(int data) {
    std::shared_ptr<Node> node = find(data);
    std::shared_ptr<Node> successor = 0;
    if(!node) {
        return;
    }
    if(!node->left) {
        transplant(node, node->right);
        check_balance(node);
    } else if(!node->right) {
        transplant(node, node->left);
        check_balance(node);
    } else {
        successor = inorder_successor(node);
        if(successor->parent != node) {
            transplant(successor, successor->right);
            check_balance(successor->parent);
            successor->right = node->right;
            if(successor->right) {
                successor->right->parent = successor;
            }
        }
        transplant(node, successor);
        successor->left = node->left;
        if(successor->left) {
            successor->left->parent = successor;
        }
        successor->parent = node->parent;
        check_balance(successor);
    }
}

std::shared_ptr<Node> Avl::find_helper(std::shared_ptr<Node> parent_node, std::shared_ptr<Node> node) {
    if(!parent_node || parent_node->data == node->data) {
        return parent_node;
    }
    if(node->data > parent_node->data) {
        return find_helper(parent_node->right, node);
    } else if(node->data < parent_node->data) {
        return find_helper(parent_node->left, node);
    }
    return 0;
}

std::shared_ptr<Node> Avl::find_helper(std::shared_ptr<Node> parent_node, int data) {
    if(!parent_node || data == parent_node->data) {
        return parent_node;
    }
    if(data > parent_node->data) {
        return find_helper(parent_node->right, data);
    } else if(data < parent_node->data) {
        return find_helper(parent_node->left, data);
    }
    return 0;
}

std::shared_ptr<Node> Avl::find(std::shared_ptr<Node> node) {
    std::shared_ptr<Node> temp = root;
    return find_helper(temp, node);
}

std::shared_ptr<Node> Avl::find(int data) {
    std::shared_ptr<Node> temp = root;
    return find_helper(temp, data);
}

void Avl::destroy() {
    root.reset();
}

void Avl::destroy_helper(std::shared_ptr<Node>& node) {
}

void Avl::transplant(std::shared_ptr<Node> node, std::shared_ptr<Node> second_node) 
{
    if(!node->parent) {
        root = second_node;
    }
    if(node->parent && node->parent->right == node) {
        node->parent->right = second_node;
    } else if(node->parent && node->parent->left == node) {
        node->parent->left = second_node;
    }
    if(node->parent && second_node) {
        second_node->parent = node->parent;
    }
}

std::shared_ptr<Node> Avl::inorder_successor(std::shared_ptr<Node> node) {
    std::shared_ptr<Node> temp = node;
    if(temp->right) {
        return get_min(temp);
    }
    std::shared_ptr<Node> parent = temp->parent;
    while(parent && temp == parent->right) {
        temp = parent;
        parent = parent->parent;
    }
    return parent;
}

std::shared_ptr<Node> Avl::left_rotate(std::shared_ptr<Node> node) {
    std::shared_ptr<Node> temp = node->right;
    node->right = temp->left;
    temp->left = node;
    if(node->right) {
        node->right->parent = node;
    }
    temp->parent = node->parent;
    if(node->parent) {
        if(node == node->parent->left) {
            node->parent->left = temp;
        } else if(node == node->parent->right) {
            node->parent->right = temp;
        }
    }
    node->parent = temp;
    return temp;
}

std::shared_ptr<Node> Avl::right_rotate(std::shared_ptr<Node> node) {
    std::shared_ptr<Node> temp = node->left;
    node->left = temp->right;
    temp->right = node;
    if(node->left) {
        node->left->parent = node;
    }
    temp->parent = node->parent;
    if(node->parent) {
        if(node == node->parent->left) {
            node->parent->left = temp;
        } else if(node == node->parent->right) {
            node->parent->right = temp;
        }
    }
    node->parent = temp;
    return temp;
}

std::shared_ptr<Node> Avl::left_right_rotate(std::shared_ptr<Node> node) {
    node->left = left_rotate(node->left);
    return right_rotate(node);

}

std::shared_ptr<Node> Avl::right_left_rotate(std::shared_ptr<Node> node) {
    node->right = right_rotate(node->right);
    return left_rotate(node);
}

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

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

void Avl::add(std::shared_ptr<Node> node) {
    if(!root) {
        root = node;
        return;
    }
    add_helper(root, node);
}

void Avl::add(int data) {
    if(!root) {
        root = std::make_shared<Node>(data);
        return;
    } 
    std::shared_ptr<Node> node = std::make_shared<Node>(data);
    add_helper(root, node);
}

void Avl::check_balance(std::shared_ptr<Node> node) {
    if(height(node->left) - height(node->right) > 1 || height(node->left) - height(node->right) < -1) {
        node = rebalance(node);
    } 
    if(!node->parent) {
        return;
    }
    check_balance(node->parent);
}

//void Avl::rebalance(std::shared_ptr<Node> node) {
std::shared_ptr<Node> Avl::rebalance(std::shared_ptr<Node> node) {
    if(height(node->left) - height(node->right) > 1) {
        if(height(node->left->left) >= height(node->left->right)) {
            node = right_rotate(node);
        } else {
            node = left_right_rotate(node);
        }

    }
    if(height(node->left) - height(node->right) < -1) {
        if(height(node->right->right) >= height(node->right->left)) {
            node = left_rotate(node);
        } else {
            node = right_left_rotate(node);
        }
    }
    if(!node->parent) {
        root = node;
    }
    return node;
}

void Avl::traverse_inorder(std::vector<int>& out) {
    std::shared_ptr<Node> node = root;
    traverse_inorder_helper(node, out);
}

void Avl::traverse_preorder(std::vector<int>& out) {
    std::shared_ptr<Node> node = root;
    traverse_preorder_helper(node, out);
}

void Avl::traverse_postorder(std::vector<int>& out) {
    std::shared_ptr<Node> node = root;
    traverse_postorder_helper(node, out);
}

void Avl::traverse_inorder_helper(std::shared_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::shared_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::shared_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);
}
\$\endgroup\$
0

1 Answer 1

Reset to default
3
\$\begingroup\$

Memory Leak

std::shared_ptrs free their target when the last reference to that target disappears. Since you have Nodes that point at each other (node->right->parent == node) that never happens. std::weak_ptr is made to solve this problem.

Ownership vs Pointing

You are not forced to use std::shared_ptr just because you want to point at it from multiple spots. std::shared_ptr means "I co-own that data and as long as I live that data will live". Looking at Node that really isn't what you meant. One way to model this is that Nodes own their children, but the children only point to the parent, they don't own their parent. That would leave you with

std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
Node* parent;

Alternatively you can look into std::weak_ptr which is made to avoid cyclic references.

Don't Expose Your Privates

Node is private to Avl. Outside users should not be concerned with how to wire up Nodes. Right now I can do avl.find(x)->data = x + 1; //update value which breaks your tree. Since changing the value breaks the tree you cannot give the user a non-const reference to the data. You could make the Node members private, add Avl as a friend and add a Avl::set_value(const std::shared_ptr<Node> &) function that handles the rebalancing correctly. Maybe add a public getter for data, but definitely no constructor.

Unnecessary Copies

int height(std::shared_ptr<Node> node); for example makes a copy of its argument which means an increment and decrement of the atomic reference counter which means thread synchronization. Taking a const & would avoid that.

Naming

destroy is more commonly named clear.
I would argue that functions returning a bool should be phrased as a question. empty should be is_empty to avoid tree.empty(); //does not actually empty the tree. But the STL also does this wrong and keeping it STL-compatible instead of logical is also a reasonable design decision. Maybe use both.

Dead Code

destroy_helper seems to be useless.

Interface

Const Correctness

If I get a const Avl &tree I can barely do anything with it. I can check the size and if it's empty. I cannot travers_* it or find anything in it. Those functions should be const too.

Out Parameters

void traverse_inorder(std::vector<int>& out); is ugly to use and usually inefficient. std::vector<int> traverse_inorder() const; is much nicer to work with. If you keep the old version as a minor performance improvement call .reserve or .resize on the vector since you know exactly how big it will end up.

Noise

inline size_t size() const {
    return current_size;
}

is already implicitly inline, so just remove the redundant keyword.

Unnecessary Privacy

You already have get_min, but it's private. Since you already have it may as well expose it to the user (probably without the parameter or making it optional) instead of having them reimplement it.

Logic

I only looked at this briefly, so this is nowhere near complete.
void Avl::add(std::shared_ptr<Node> node) adds a Node without any unlinking. It keeps its parent and left and right, possibly going into another tree.
Avl tree_copy = tree; compiles, but doesn't make a copy.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for review, I will try to implement a model where the children pointers are unique and the parent is a raw pointer. \$\endgroup\$ Commented May 31, 2019 at 14:01

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.