Data Structure 2

Contents: AVL Tree B-Tree Red Black Tree Heaps & Tries Graphs Reference: Alfon's Notion: Tree Based Data Structure Jenny's lectures CS/IT NET&JRF: 5.17 RED BLACK Tree Insertion Jenny's lectures CS/IT NET&JRF: 5.18 RED BLACK Tree Deletion

AVL Tree

Introduction
AVL Tree is a self-balancing Binary Search Tree. Its main characteristic is that the difference of height between the left and right sub-tree of all nodes cannot be more than one. This is called the Balance Factor of the node:

$\text{Balance Factor} = \text{Left Sub-Tree Height} - \text{Right Sub-Tree Height}$

Example of AVL Tree

In other words, the balance factor of all nodes in an AVL Tree should always be -1, 0, 1.

Since AVL Tree is still classified as a Binary Search Tree, the implementation of Binary Search Tree is still used in implementing AVL Tree though there are some stuff that have to be added for AVL Tree's characteristic of balance factors. For example, the node struct now contains their own height:


Insertion & Deletion
Insertion & deletion of nodes in an AVL Tree begins with the same insertion & deletion of nodes in a Binary Search Tree. However, upon performing either insertion & deletion, we must check whether the balance factor of all nodes is either -1, 0, 1. Should there be any violation to the balance factor, then we can use rotations to solve them.

There are 4 kinds of rotations used to resolve these violations: Single Left Rotation, Single Right Rotation, Left-Right Rotation and Right-Left Rotation.

Single Right Rotation

Single Left Rotation

Left-Right Rotation

Right-Left Rotation

Single Right Rotation and Single Left Rotation are mirrors of each other, hence I only made .gif for Single Right Rotation and mirrored it for the latter's visualization. Same with Left-Right Rotation and Right-Left Rotation.

Though the .gif for Left-Right Rotation only shows one left rotation, like the name suggests, one right rotation is done afterwards. Upon performing the initial left rotation, we can see that the tree becomes exactly like the tree used in the visualization for Single Right Rotation. Same with Right-Left Rotation.



Usage
Due to AVL Tree's characteristic of balance factors, one of AVL Tree's advantage is O(log n) searching time. However, AVL Tree's disadvantage lies in its insertion & deletion because insertion & deletion can involve lots of rotations.

Since AVL Tree's advantage lies in its searching, it is used when fast searching is needed.

B Tree

Introduction
B-Tree is a self-balancing tree. The following are the propeties of a B-Tree for order = m:

• Each node has m children at most.
• Each non-root node has (m/2) children at least.
• The root has 2 children if it is not a leaf.
• Each non-leaf node with k children contain (k-1) keys.
• All data are kept in sorted order.
• All leaves are always on the same, bottom level.

Insertion (2-3 Tree)
There are two different cases during insertion, which are:

• Case 1 New key is inserted but doesn't make the node full: Just add, nothing left to do.
• Case 2 New key is inserted and it makes a node full.
  
  Insertion: Case 2a
  • Case 2a Parent node isn't full.
  
  Insertion: Case 2b
  • Case 2b Parent node is full.

Deletion (2-3 Tree)
There are three different cases during deletion, which are:

Deletion: Case 1
• Case 1 Key_{leaf with deleted key} is less than minimum and Key_sibling is more than minimum.

Deletion: Case 2
• Case 2 Key_{leaf with deleted key} is less than minimum and Key_sibling is NOT more than minimum.

Deletion: Case 3
• Case 3 Deleting internal node.

Sometimes, fixing the parents is required. Some examples:

Fixing Parent Example: Case 1
• Case 1 Key_parent is less than minimum and Key_{parent's sibling} is more than minimum.

Fixing Parent Example: Case 2
• Case 2 Key_parent is less than minimum and Key_{parent's sibling} is less than minimum.

Usage
The height of a B-Tree is always minimized, due to its characteristics that allow multiple keys/values in a single node. Due to this characteristic, B-Tree is often used when dealing with large amount of datas (e.g. indexing in database).

Red Black Tree

Introduction
Red Black Tree is a kind of self-balancing Binary Search Tree. Unlike the usual Binary Search Tree, Red Black Tree has the following properties:

• Every node is colored either RED or BLACK.
• By default, root is colored BLACK. Newly added nodes afterwards will be initially colored as RED.
• External nodes are colored BLACK.
• There are no adjacent RED nodes.

Insertion

• Case 1 Color_{parent node} is BLACK: Just add, nothing left to do.
• Case 2 Color_{parent node} is RED.
  
  Insertion: Case 2a
  • Case 2a Color_{parent's sibling} is BLACK/NULL.
    • Perform appropriate rotation.
    • Recolor.
  
  Insertion: Case 2b
  • Case 2b Color_{parent's sibling} is RED.
  • Recolor, and recheck.

Deletion
Begin by performing BST deletion, and apply the appropriate cases:

• Case 1 Color_{deleted node} is RED: Just delete, nothing left to do.
• Case 2 Color_{DB's sibling} and Color_{DB's sibling's children} are BLACK.
  • Remove DB
  • If Color_{DB's parent} is RED, it becomes BLACK. Otherwise, it becomes DOUBLE BLACK.
  • Color_{DB's sibling} becomes RED.
  • If necessary, re-apply appropriate cases.
• Case 3 Color_{DB's sibling} is RED.
  • Remove DB
  • Swap Color_{DB's parent} with Color_{DB's sibling}.
  • Rotate parent in the direction of DB.
  • Re-apply appropriate cases.
• Case 4 Color_{DB's sibling} is BLACK, Color_{child of DB's sibling nearest to DB} is RED and Color_{child of DB's sibling farthest to DB} is BLACK.
  • Swap Color_{DB's sibling} with Color_{child of DB's sibling nearest to DB}.
  • Rotate sibling in the opposite direction of DB.
  • Apply Case 5.
• Case 5 Color_{DB's sibling} is BLACK and Color_{farthest child of DB's sibling} is RED.
• Swap Color_{DB's sibling} with Color_{DB's parent}.
• Rotate parent in the direction of DB.
• Remove DB.
• Color_{child of DB's sibling farthest to DB} becomes BLACK.

Usage
Red Black Trees are used in Java TreeMap, and the process scheduler in Linux.

Heaps & Tries

Introduction: Heaps
There are 3 kinds of heaps, which are Min-Heap, Max-Heap and Min-Max Heap.

Min-Heap is a heap with the characteristic where the value of all nodes are always smaller than the value of their children, hence it can be concluded that the smallest value is located on the root of the tree, and the largest value is located in one of the leaves.

Max-Heap is a heap with the characteristic where the value of all nodes are always greater than the value of their children, hence it can be concluded that the largest value is located on the root of the tree, and the smallest value is located in one of the leaves.

Min-Max Heap is a heap that alternates between the characteristic of a Min-Heap and Max-Heap from level to level.

Usage: Heaps
Heaps are often used in Heap Sort, and in implementing graph algorithms such as Prim's minimal spanning tree algorithm and Djikstra's shortest path problem. Tries
Tries, or prefix tree, is a kind of a tree data structure used to store an associative array (like strings).

Graphs

Definition
Graph is an abstract data structure with the purpose of implementing the mathematical concept of graph. It is also a collection vertices (or nodes) connected by edges.

There is Undirected Graph, it is a graph where its edges don't have direction. Likewise, there is Directed Graph, it is a graph where its edges have direction.

The connection between nodes of a graph can be represented by the Adjacency List Matrix. It can be implemented using array, or linked list.

Prim's Algorithm
Prim's algorithm is an algorithm to find the MST (Minimum Spanning Tree).


Kruskal's Algorithm
Kruskal's algorithm is an algorithm to find the MST (Minimum Spanning Tree).


Dijkstra's Algorithm
Dijkstra's algorithm is an algorithm to find the shortest path possible between two nodes.