CODEWITHSUNDEEP
binary-treebinary-search-treeavl-treered-black-treebalanced-binary-search-tree
Alexander Mills
Alexander Mills

Reputation: 100486

How to rebalance BST if removing root node

Let's say I delete the root node (6), how do I rebalance the tree?

enter image description here

Is rebalancing the tree related to a left or right rotation? Would it be different depending on AVL vs Red/Black?

Upvotes: 2

Views: 1186

Answers (3)

SJHowe
SJHowe

Reputation: 776

Deleting the node and rebalancing the binary search tree are two separate operations. If you wish to delete a node that has 2 children, you need to find the successor or predecessor node of the node you wish to delete.

The successor node is go to the right child of the node to delete, now go leftwards as far as you can among real nodes.

The predecessor node is go to the left child of the node to delete, now go rightwards as far as you can among real nodes.

In your example, the successor of 6 is 7, the predecessor of 6 is 5. Pick either of these, swap the value of node with 6 (but also if the node has balance or colour info, this remains unswapped).

Now delete 6 in its new position. Once done any rebalancing or recolouring or both of nodes depends on whether AVL or Red-Black rules are broken. Fixups of trees means you work your way towards the root, and once the rules are satisfied, you stop.

Is rebalancing the tree related to a left or right rotation? Yes. But in the case of Red-Black trees, sometimes nodes are recoloured.

Would it be different depending on AVL vs Red/Black? Yes, because Red/Black trees have the option of recolouring nodes, AVL trees don't.

In the case of AVL trees, as you work up the chain of parent nodes, you are looking for temporary height differences of 2 or -2. If you find one, a rotation is needed. In the case of Red-Black trees, if the node deleted was red => tree is still Red-Black. If the node deleted was black but a single red child => the child replaces the node deleted and is coloured black. If the node deleted was black and has no children => then a search towards the root node is necessary, looking for a red sibling node that can be rotated to fill the hole caused by the deletion.

Upvotes: 0

Alexander Mills
Alexander Mills

Reputation: 100486

I think the following is for AVL not Red/Black (although not sure if it matters). This video is pretty good: https://youtu.be/g4y2h70D6Nk?t=384

if you remove the root node (6), you would replace it with either (5) or (7).

The way (5) or (7) is discovered: you want the rightmost value from the left child of (6), or the leftmost value from the right child of (6). Let's go with (5)..so the operations are:

4.right = null;
5.left = 4;
4.parent = 5;
5.right = 8;
8.parent = 5;

Upvotes: 0

SuperJumbo
SuperJumbo

Reputation: 541

Knowing the height of each sub-tree of the (now removed) root, you'd make the taller of the two sub-trees the new root. (Making the shorter of the two the root would violate your balanced-ness)

I'm not sure if there is a rotation involved because as I recall a rotation is implemented on a single sub-tree, but in this case you've actually got two trees; instead I think it's just some reference updates.

In this case if 4 is the new root, you have two right sub-trees - 5 and the prior right sub-tree of 7-8. It makes sense that the root of the new right sub-tree will be the left most node of the prior right sub-tree, with the 5 slotting in under that.

Upvotes: 2

Related Questions