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

Average case anaysis, what is the impoartance of average case analysis of ...

what is the impoartance of average case analysis of algorithm

Algorithms and flowcharts, write an algorithm and draw a flowchart to calcu...

write an algorithm and draw a flowchart to calculate the perimeter and area of a circle

The complexity of searching an element, The complexity of searching an elem...

The complexity of searching an element from a set of n elements using Binary search algorithm is   O(log n)

The quick sort algorithm exploit design technique, The quick sort algorithm...

The quick sort algorithm exploit design technique Divide and Conquer

Define a b-tree, Define a B-Tree Justas AVL trees are balanced binary s...

Define a B-Tree Justas AVL trees are balanced binary search trees, B-trees are balanced M-way search trees. A B-Tree of order M is either the empty tree or it is an M-way searc

Binary tree construction, Construct a B+ tree for the following keys, start...

Construct a B+ tree for the following keys, starting with an empty tree.  Each node in the tree can hold a maximum of 2 entries (i.e., order d = 1). Start with an empty root nod

Multikey file organization, what are the applications of multikey file orga...

what are the applications of multikey file organization?

The number of different directed trees with 3 nodes, The number of differen...

The number of different directed trees with 3 nodes are ?? The number of disimilar directed trees with three nodes are 3

FIRST function in the compiler construction, I need a recursive algorithm t...

I need a recursive algorithm to implement the FIRST function to any grammar

Sorting algorithms, Sorting is significant application activity. Several so...

Sorting is significant application activity. Several sorting algorithms are obtainable. But, each is efficient for a specific situation or a specific kind of data. The choice of a

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