Does deleting a node with no children from a red black tree and then re-insertin

Question

Does deleting a node with no children from a red black tree and then re-inserting it with the same key always result in the original tree? b) Is the subtree of the root of a red-black tree always itself a valid red-black tree? c) Does inserting a node into a RB tree and then deleting it result in the original tree? d) For the following BST, which of the following stack configurations is never observed with recursive call to search? A. 20, 10, 40, 30, 35, 60 B. 10, 20, 30, 35, 40, 60 C. 10, 35, 30, 60, 40, 20 D. 10, 20, 40, 30, 35, 60 e) 127 elements are inserted one at a time into an initially empty binary search tree using the traditional, naive algorithm. What is the maximum possible height of the resulting tree, if it isn't ? A. 64 B. 126 C. 127 D. 254 E. 14 f) Suppose the above tree were a RBT. What is the maximum possible height of the resulting tree now?^1 A. 64 B. 126 C. 127 D. 254 E. 14

Explanation / Answer

2. a: No,because in insert operation, we check color of uncle to decide the appropriate case. In delete operation, we check color of sibling to decide the appropriate case.

b: No,because the root node must be black and the child of black is either red or black .if the subtree we create has root node red then it will not be a valid red black tree.

c: No,because deleting the same node immediately after inserting will not always result in the original tree. As a counterexample, you can try inserting 4,7,10,23,5. Now insert 65 and delete it. The tree before inserting 65 will be different from the tree after deleting 65. The reason is basically that if any property is violated in a RB tree then it rearranges itself to restore the property which changes its structure.

d: 10,20,30,35,40,60 i.e option B .
because in A the searching begin with 10 and then traverse every node after that one by one in line
in C after searching the root nodes we are traversing its parents and so on
in D again searching begin with 10 and then every nodes are traverse in line
but there is no sequence in B

e: 126, because the height is -1 for empty binary search tree.

f: 127, because the nodes may be in increasing order and join at right sides only resulting in a tree with height of 127

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.