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

Entity relationship diagram, This question is based on the requirements of ...

This question is based on the requirements of a system to record band bookings at gigs. (A 'gig' is an event at which one or more bands are booked to play). You do not need to know

Graph connectivity, A connected graph is a graph wherein path exists among ...

A connected graph is a graph wherein path exists among every pair of vertices. A strongly connected graph is a directed graph wherein every pair of distinct vertices is connecte

Determine the disjoint of division method, Determine the Disjoint of divisi...

Determine the Disjoint of division method A polygon is disjoint from the viewport if the x- and y-extents of the polygon do not overlap the viewport anywhere. In this case; reg

B-tree, Unlike a binary-tree, each node of a B-tree may have a number of ke...

Unlike a binary-tree, each node of a B-tree may have a number of keys and children. The keys are stored or saved in non-decreasing order. Each key has an related child that is the

Define about the inheritance hierarchy, Define about the inheritance hierar...

Define about the inheritance hierarchy Languages Eiffel and D provide constructs in language for invariants and pre- and post conditions which are compiled into the code and ar

A bst is traversed in which order recursively, A  BST is traversed in the ...

A  BST is traversed in the following order recursively: Right, root, left e output sequence will be in In Descending order

Dijkstras algorithm, Djikstra's algorithm (named after it is discovered by ...

Djikstra's algorithm (named after it is discovered by Dutch computer scientist E.W. Dijkstra) resolves the problem of finding the shortest path through a point in a graph (the sour

Ruby implementation of the symbol abstract data type, Ruby implementation o...

Ruby implementation of the Symbol ADT Ruby implementation of the Symbol ADT, as mentioned, hinges on making Symbol class instances immutable that corresponds to the relative la

A binary tree of depth "d" is an almost complete binary tree, A binary tree...

A binary tree of depth "d" is an almost complete binary tree if  A) Every leaf in the tree is either at level "d" or at level "d-1"  B)  For any node "n" in the tree with a

Mapping constain, one to many one to one many to many many to one

one to many one to one many to many many to one

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