RedBlack and AVL tree c++

Question

I want to understand implementation of red black and AVL trees using C++. I checked some websites about them but most of them are complex and difficult to understand. Could you suggest me some resources please?

Answer 1

First read the basic properties of the two trees. You don't have to limit yourself to one programming language. If you understand these properties,then you can implement it by yourself in any language.

Properties of Red Black Tree:

1. A node is either red or black.
2. The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.
3. All leaves (NIL) are black.
4. If a node is red, then both its children are black.
5. Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes. Some definitions: the number of black nodes from the root to a node is the node's black depth; the uniform number of black nodes in all paths from root to the leaves is called the black-height of the red–black tree.

Red Black Tree C++ code: http://www.sanfoundry.com/cpp-program-implement-red-black-tree/

AVL Tree Tutorial: https://www.youtube.com/watch?v=rwzuze_tTwQ

AVL Tree C++ code: https://tfetimes.com/c-avl-tree/