Red Black Tree

-

RED BLACK TREE


Properties

  1. Root is always black
  2. No red nodes are adjacent to each other
  3. Number of black nodes from any node to a NULL node is the same

Insertion Algorithm

N = new node
P = N's parent
U = N's uncle
GP = N's grandparent

1 Do BST insertion
2 Mark N as red
3 If N is root, colour it black
4 If P is black, stop.
5 Else
6     IF if U is RED, 
7         do recolouring (colour P and U as BLACK, and. GP as RED)
8         recursive recolouring by N = GP in the recolouring algorithm and so on
9     IF U is BLACK
10       do Rotation

Rotation Cases
1. Left Left (N is P's left child,  P is GP's left child)
2. Right Right (N is P's right child, P is GP's right child)
3. Left Right (N is P's right child, P is GP's left child)
4. Right Left (N is P's left child, P is GP's right child)

Solving the Cases
1. LL: do right rotation on GP as pivot, swap GP and P colours
2. RR: do left rotation on GP as pivot, swap GP and P colours
3. LR: do right rotation on P as pivot,  do left rotation with on GP as pivot, swap GP and N colours
4. RL: do left rotation on P as pivot, do right rotation on GP as pivot, swap GP and N colours

Deletion Algorithm

N = node to be deleted
P = parent
S = sibling of N

1 Do BST deletion
2 IF N is red, just delete
3 IF N is black and N's child is RED, swap colours and delete N
4 ELSE move to double black case
5     IF N is root, just delete
6.    IF P is red and S and S's children are all black, swap P and S colours and immediately delete N
7.    IF S is RED, do rotation with P as pivot, swap P and S colours, do second IF
8     IF P, S and S's children are all black, make S red and the the 3rd IF
9.    IF S's children is at least one red, do a single/double rotation, the node taking the position of P will also have its colour, delete N




Comments

Post a Comment

Popular posts from this blog

Hash Tables and Trees

-
Image
Hash Tables and Hashing Hashing Hashing is a technique used to store and allocate data (in a hash table array for example) by obtaining a key from the inputted data and processing it to its respective index. This hashing process through a Hash Function which has many different forms and each will spit out different results even from one key. For example, we may have a series of string such as "apple", "dog" and "cat" and we want to place this is an array of strings. Sure, we can just insert them using a For-loop and the resulting array will be : { "apple", "dog","cat"}.  Now assume we have hundreds of different strings and we one to search for the string "cat" in the array. We now have to do a linear search through the array which has the time complexity of O(n). This wouldn't be an effective method of storing and searching data if we have a large amount of data stored. A way to make the time...
Read more

AVL TREES & B-TREES

-
Image
AVL TREE DEFINITION AVL trees is a self-balancing binary search tree where the difference between heights of left and right subtrees cannot be more than one for all nodes. To ensure that this property is fulfilled, each node will have a variable called the balance factor  which is calculated by (height of left subtree - height of right subtree). The node is said to be balanced  if and only if the balance factor is = {-1,0,1}. With this condition, the property of the AVL tree will be fulfilled. BENEFITS The obvious benefit of an AVL tree when compared with a BST is the worst case time complexity of a search in an AVL tree is O(log n) compared to the O(n) worst case time complexity of a BST. This is simply because an AVL tree will always have the height of O(log n) due to its property. BALANCING What happens if we insert a new node or delete a current node (NOTE: insertion and deletion follows the same algorithm as BST's, but is only added with the balancing a...
Read more

Binary Search Tree

-
Image
Binary Search Tree Theory Why do we use BST (Binary Search Tree) for storing data? Well, BST allows for faster searching and sorting, insertion and deletion of data. This can happen because of the fundemental rules of Binary Search Trees, which are:  For every node in a BST, the left subtree of the node must contain elements which are smaller than the element stored in the node. For every node in a BST. the right subtree of the node must contain elements which are greater than the element stored in the node Therefore, traversing through a binary search will just be a matter of asking the question of greater or smaller.  Basic BST Operations Search This search algorithm will return a struct Node* datatype, this is just something that we need to keep in mind when applying this algorithm in our main function Insert Delete This deletion operation requires some sort of visualisation to fully understand, especially on line 28. Howev...
Read more