How do insertions and deletions in a 2-3-4 tree retain the structure’s perfect balance?
Explain how the worst-case behaviour of Quicksort can be avoided to yield an improved time complexity
March 20, 2023Using big-O notation, state the average time and space complexity of quicksort
March 20, 2023How do insertions and deletions in a 2-3-4 tree retain the structure’s perfect balance?
Algorithms
(a) How do insertions and deletions in a 2-3-4 tree retain the structure’s perfect
balance? [2 marks]
(b) Explain the structural relationship between 2-3-4 trees and red-black trees.
[4 marks]
(c) Draw diagrams to illustrate left and right rotations at the root node of a binary
search tree. Label the positions of all subtrees before and after the rotation.
[4 marks]
(d) Write pseudocode for a recursive function move to root(x,k) which, given a
binary search tree with root node x and a key value k, uses a sequence of
rotations to move the node with key value k to the root of the tree and returns
a pointer to the new root node. [10 marks]
