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

Tree, application of threaded binary treee

application of threaded binary treee

Infix expression to postfix form using the stack function, Q. Convert the f...

Q. Convert the following given Infix expression to Postfix form using the stack function: x + y * z + ( p * q + r ) * s , Follow general precedence rule and suppose tha

Define the term ''complexity of an algorithm, Define the term 'complexity o...

Define the term 'complexity of an algorithm; Complexity of an algorithm is the calculate of analysis of algorithm. Analyzing an algorithm means predicting the resources that th

Determine the warnock algorithm, Warnock's Algorithm A divide and conqu...

Warnock's Algorithm A divide and conquer algorithm Warnock (PolyList PL, ViewPort VP) If (PL simple in VP) then Draw PL in VP, else Split VP vertically and horiz

Explain b- tree, B- Tree  A B-tree of order m is an m-way true in which...

B- Tree  A B-tree of order m is an m-way true in which  1)  All leaves are on the similar level 2)  All internal nodes except the root have at most m-1(non-empty) childre

Data structure, Ask question #Minimum 1Mark each of the following statement...

Ask question #Minimum 1Mark each of the following statements as valid or invalid. If a statement is invalid, explain why. a. current ¼ list; b. temp->link->link ¼ NULL; c. trail->l

Adjacency matrix representation of a graph, An adjacency matrix representat...

An adjacency matrix representation of a graph cannot having information of : Parallel edges

Linked list, write an algorithm for multiplication of two sparse matrices u...

write an algorithm for multiplication of two sparse matrices using Linked Lists

Program on radix sort., Write a program that uses the radix sort to sort 10...

Write a program that uses the radix sort to sort 1000 random digits. Print the data before and after the sort. Each sort bucket should be a linked list. At the end of the sort, the

Array vs. ordinary variable, Q. Describe what do you understand by the term...

Q. Describe what do you understand by the term array? How does an array vary from an ordinary variable? How are the arrays represented in the specific memory?

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