Index
1. Stack
2. Queue
2.1. Queue
2.2. Priority Queue
3. Linked List
3.1. Linked List
3.2. Doubly Linked List
3.3. Circular Linked List
4. Binary Tree
4.1. Binary Tree
4.2. Heap
4.3. BST (Binary Search Tree)
4.4. AVL Tree1. Stack
Stack is an array-like structure that follows the LIFO (last-in first-out) rule, i.e., the element that joins the stack last will be the first one leaving. Stack has two basic operations, push and pop. Push adds one elements to the top of the stack while pop removes the top element. C++ has built-in stack class in standard library <stack>. More information can be found in the post C++ Standard Library – <stack> section.
2.1. Queue
Queue is an array-like structure that follows the LILO (last-in last-out) rule, i.e., the element that joins the queue last will be the last one leaving. Queue has two basic operations, enqueue and dequeue (or push and pop, respectively). Enqueue adds one elements to the tail of the queue while dequeue removes the head of the queue. C++ has built-in queue class in standard library <queue>. More information can be found in the post C++ Standard Library – <queue> section.
2.2. Priority Queue
Priority queue is similar to queue, but each element in a priority queue is associated with a value that defines its priority, and the element with higher priority is in the front. Pop removes the element with the highest priority from priority queue. This data structure is also contained in C++ standard library <queue>. Note that max heap is an implementation of priority queue.
4.1 Binary Tree
4.2 Heap
4.4. AVL Tree
AVL tree, named after Adelson-Velsky and Landis, requires the heights of left and right children of every node in the tree to differ by at most ±1.
Following this description, we can formulate a recurrence relation:
N0 = 1, N1 = 2;
Nh = 1 + Nh-1 + Nh-2,
where Nh is the minimum number of nodes required in a AVL tree of height h.
This relation yields the following inequality since Nh > Fh (Fibonacci sequence) when h > 1:
h < 1.44 lg n
Below is a diagram showing AVL trees of height 0, 1, 2, 3, and 4 that contain the minimum number of nodes:
AVL insert requires the rotation operation. Suppose node x is right-heavy. If the child of x is right-heavy or balanced, then a left rotation on x fixes the problem on x. If the child of x is left-heavy, then a right rotation on the right child of x followed by a left rotation on x fixes the problem on x. Repeat the procedure going up from x as these nodes may be affected by previous operations.
