Red-black tree is a binary search tree which garanties searching, insertion and deletion in logarithmic time. As all extensions of BST it has additional properties which helps to keep tree balanced:
- A node has color either black or red.
- The root node is black.
- All leaves are black and don’t contain data. Sometimes to reduce memory consumption a single node performs the role of all leaves.
- Every red node must have two black child. This implies that on any path there can’t be two consecutive red nodes or in other words a red node can’t have a red child.
- Every path from a node to a descendant leaf contains the same number of black nodes. This number is called black height.
The best way to get the idea of these properties is an example. Let’s say we have inserted three elements in a plain vanilla binary search tree: Continue reading Red-black tree
AVL tree is a self-balancing binary search tree, which was invented by soviet mathematicians Georgy Adelson-Velskii and Evgenii Landis’. To the basic rules of BST added a new property which states that heights of the two sub-trees differ by at most one. This property helps to avoid the worst case in which search, insert and delete operations has linear complexity in the binary search tree.
As you can see on the diagram above the root node of the unbalanced three has left and right sub-tree. But, the right sub-tree is two levels deeper that the left sub tree. Continue reading AVL Tree
Binary search tree or BST is a family of tree-based data structures, with maximum of two children and which follow to the general restriction that any node in a tree is larger than all nodes in it’s left sub-tree and smaller than all nodes in it’s right sub-tree.
BST doesn’t support duplicates, thus it can be used to construct sets or associative arrays. Continue reading Binary search tree
Binary heap is a tree-like data structure that generally can be separated into two types: min-heap and max-heap. The difference is that in the max-heap all nodes are greater than or equal to each of it’s children. In the min-heap everything is vise versa, all nodes are less than or equal to each of its children. Thus, the highest (max-heap) or lowest (min-heap) element is always on the top and this is the main advantage which provides possibility to access the min or the max element in constant time. Another important property is that all levels, except the last last one, must be full.
The last level can be either full or not, but all new elements always added to the last level, from the left to the right.
Continue reading Binary heap