CODEWITHSUNDEEP
binary-tree
Gwen Brewer
Gwen Brewer

Reputation: 87

How to tell if a binary tree is red-black balanced?

In a past exam we were once asked to decide whether a tree was red-black balanced by looking at its shape. I haven't found any information on how to do this, except that one sight claims that a binary tree is red-black balanced if the longest path is no more than twice the shortest, but I'm pretty sure that's the requirement for null path balanced trees, too. Is that correct? Is there any way to tell if a tree is red-black balanced by the shape?

Upvotes: 5

Views: 3529

Answers (3)

Mostafa Derispour
Mostafa Derispour

Reputation: 21

to check if a binary tree is red-black tree balanced, you should validate that for every subtree the maximum height is less than or equal to the twice of the minimum height

more information:

check given binary tree follows height property red black tree

Upvotes: 1

gsamaras
gsamaras

Reputation: 73366

Don't mix things up. Probably the professor wants the students to realize what a Red-black tree looks like.

From wikipedia, you have:

In addition to the requirements imposed on a binary search tree the following must be satisfied by a red–black tree:

  1. A node is either red or black.
  2. The root is black.
  3. All leaves (NIL) are black.(All leaves are same color as the root.)
  4. Every red node must have two black child nodes (and therefore it must have a black parent).
  5. Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.

These constraints enforce a critical property of red–black trees: that the path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf. The result is that the tree is roughly height-balanced. Since operations such as inserting, deleting, and finding values require worst-case time proportional to the height of the tree, this theoretical upper bound on the height allows red–black trees to be efficient in the worst case, unlike ordinary binary search trees.

Source

Then there is this question: Colour a binary tree to be a red-black tree

and this one: How to check the black-height of a node for all paths to its descendent leaves?, where you can find an algorithm for your question.

Take this tree for example: enter image description here

If the test has a colored tree, then you can assert the properties given from Wikipedia. If the tree has no colors, which I think will be the case, then take the tree I linked to above, write it down to a piece of paper and run the algorithm provided in the linked question.

Upvotes: 1

Giorgi Nakeuri
Giorgi Nakeuri

Reputation: 35780

I'm not guru, but this is from Cormen's book Introduction to Algorithms:

A red-black tree is a binary tree that satisfies the following red-black properties:

  1. Every node is either red or black.
  2. The root is black.
  3. Every leaf (NIL) is black.
  4. If a node is red, then both its children are black.
  5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Upvotes: 1

Related Questions