Category Archives: Data structures

Trie

Trie or prefix tree is a tree-like data structure that implements dictionary abstract data type. In other words, trie allows to store key/value pairs in hierarchical structure. For example, let say we have words {a, as, air, aim, ail, car, i, milk, be, bag}. These words can be represented as follows.

trie_intro4

As you can see the root of the trie is an empty string that has five direct children. Every child represents first letter of a given word so that the words with the same prefix share the common nodes. As a result, a key can consist of one or more nodes, but values stored in one node.

Continue reading Trie

Red-black tree

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:

  1. A node has color either black or red.
  2. The root node is black.
  3. All leaves are black and don’t contain data. Sometimes to reduce memory consumption a single node performs the role of all leaves.
  4. 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.
  5. Every path from a node to a descendant leaf contains the same number of black nodes. This number is called black height.

rbt

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

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.

avl_2

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

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

 

BST doesn’t support duplicates, thus it can be used to construct sets or associative arrays. Continue reading Binary search tree

Binary heap

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.

heap

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