Below is a partially complete, recursive, pseudocode description of the insertio

Question

Below is a partially complete, recursive, pseudocode description of the insertion algorithm for (left-leaning) red-black trees. The algorithm searches for the key, if it finds it replaces the old value with the new value. Otherwise, it stops at a null node (external) and inserts a new node there. On the way out of the recursion it balances the tree. Other than the insert() method itself you may call five other methods: Node(Key key, Value val, boolean colour) - Create a Node and set the key, val and colour (RED or BLACK) is Red (Node h) - returns true if node h is RED, otherwise false flipColours (Node h) - Toggles the colours of h and its children rotateLeft (Node h) - Makes a right-leaning red node (h.right) left-leaning rotate Right (Node h) - Makes a left-leaning red node (h.left) right-leaning Fill in the blanks to complete the code. Algorithm insert (h, k, v): Input: Current node h, key k used for search and the value v to be stored Output: Current node h, possibly different based on restructuring if h = null then//reached an external node return new _____//create a new node if k h. key then _____//recursive call to insert else _____//key k already exists in the tree if _____ and _____ then//Need to rotate left h leftarrow rotateLeft(h) if _____ and _____ then//Need to rotate right h leftarrow rotateRight (h) if _____ and _____ then//Need to flip the colours h leftarrow flipColors (h) return h

Explanation / Answer

1. Node( k, v) //where k is key and v is value if the node is null then we insert the value

2.h.left = insert (h.k, k,v) // if the key is greater than node h.k then it is inserted to left part of node

3.h.right= insert (h.k,k,v) // if key is less than node h.k

4.return h //no change if already exists

5. if (isRed(h.right) // fixs the right-leaning reds on the way up rotates left

6. if (isRed(h.left) ) and (isRed(h.left.left) ) //fixs 2 reds in a row on the way up rotates right

7.if (isRed(h.left) and (isRed(h.right)) //splits 4 nodes on the way up

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

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