Properties of a red-black tree, Data Structure & Algorithms

Assignment Help:

Any binary search tree must contain following properties to be called as a red-black tree.

1. Each node of a tree should be either red or black.

2. The root node is always black.

3. If a node is red, then its children should be black.

4. For every node, all the paths from a node to its leaves contain the same number of black nodes.

We describe the number of black nodes over any path from but not including a node x down to a leaf, the black height of the node is denoted by bh (x).

Red-black trees contain two main operations, namely INSERT and DELETE. When the tree is modified, the result might violate red-black properties. To restore the tree properties, we must change the color of the nodes as well as the pointer structure. We can change the pointer structure by using a technique called rotation which preserves inorder key ordering. There are two types of rotations: left rotation and right rotation.

When we do a left rotation on a node y, we suppose that its right child x is non null. The left rotation makes x as the new root of the subtree with y as x's left child and x's left child as y's right child.

Alike procedure is repeated vice versa for the right rotation.


Related Discussions:- Properties of a red-black tree

Which sorting methods sorting a list which is almost sorted, Which sorting ...

Which sorting methods would be most suitable for sorting a list which is almost sorted  Bubble Sorting method.

Explain in detail about the ruby arrays, Explain in detail about the Ruby a...

Explain in detail about the Ruby arrays Ruby arrays have many interesting and powerful methods. Besides indexing operations which go well beyond those discussed above, arrays h

Splaying procedure, For splaying, three trees are maintained, the central, ...

For splaying, three trees are maintained, the central, left & right sub trees. At first, the central subtree is the complete tree and left and right subtrees are empty. The target

Program of implementation of stack using arrays, include int choice, st...

include int choice, stack[10], top, element; void menu(); void push(); void pop(); void showelements(); void main() { choice=element=1; top=0; menu()

Simulation of queues, Simulation is the process of making an abstract model...

Simulation is the process of making an abstract model of a real world situation in order to be aware of the effect of modifications and alterations and the effect of introducing nu

Insertion sort, Data array A has data series from 1,000,000 to 1 with step ...

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

Insertion of a node into a binary search tree, A binary search tree is cons...

A binary search tree is constructed through the repeated insertion of new nodes in a binary tree structure. Insertion has to maintain the order of the tree. The value to the lef

Tower of hanoi problem., Write an algorithm for getting solution to the Tow...

Write an algorithm for getting solution to the Tower's of Hanoi problem. Explain the working of your algorithm (with 4 disks) with appropriate diagrams. Ans: void Hanoi(int

Dynamic memory management, How memory is freed using Boundary tag method in...

How memory is freed using Boundary tag method in the context of Dynamic memory management? Boundary Tag Method to free Memory To delete an arbitrary block from the free li

Linked list, create aset of ten numbers.then you must divide it into two s...

create aset of ten numbers.then you must divide it into two sets numbers which are set of odd numbers and set of even numbers.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd