Return to Revisions

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.