Question

Draw the red-black BST that results when you insert letters A through K int order into an initially empty tree, then describe what happens in general when trees are built by insertion of keys in ascending order. What about descending order?

Answer 1

A red-black tree is a binary search tree in which each node is colored either red or black and follows the following conditions:

• The root of the tree is always black.
• Every leaf (which is null always) must be black.
• The children of a red node are always black i.e., there can never be adjacent red nodes.
• Every path from the root to a 0-node or a 1-node has the same number of black nodes.

Insertion in the Red Black tree happens in the same way when nodes are in ascending or descending order.There are no different rules when nodes are sorted in a certain fashion.Every insertion follows the same rules of restructuring and recoloring.

The difference is in the balancing part.The nodes will arrange themselves in a line with no branches.Since each node is larger than the previously inserted node, every node is a right child, so all the nodes are on right side of the root.Hence, the tree will be maximally unbalanced.

The tree in fact will behave like a linked list. The complexity of searching will reduce to O(N) instead of O(logN) as it is for a balanced tree.

Similarly, if nodes are inserted in descending order, every node would be the left child of its parent; the tree would be unbalanced on the left side.

As per the question if we insert nodes from A to K in ascending order or descending order following results will be shown:

Nodes inserted in Ascending Order:-

Nodes inserted in Descending order:-

Hope this is helpful

Please please dont downvote

If it is helpful please please please upvote it wil help me alot