Red Black Tree Insertion & Deletion Uniqueness

Question

I've been learning and working on implementing a red-black tree data structure. I'm following this article on red-black tree deletion examples and looking at example 5 they have:

When I insert the same nodes into my tree, I get the following:

I understand that red black trees are not unique (I think), therefore both of the above trees are valid since they don't violate any of the properties.

In the example article, after deleting node 1, they get the following:

But after deleting node 1 in my code, I get the following:

Since in my case, node 1 is red, I don't call my delete_fix function which takes care of re-arranging the tree and such. The deletion algorithm I was following simply states to call a delete_fix function if the node to be deleted is black.

However, after comparing my tree with the one in the example article I can see that mine is not exactly optimized. It still follows the rules of the red-black tree though. Is this to be expected with red-black trees or am I missing something here?

Answer 1

However, after comparing my tree with the one in the example article I can see that mine is not exactly optimized.

It is optimised. Your tree will be fast at deleting nodes 5, 7, 20 & 28. The other only 5 & 7.

Bear in mind that for Red-Black Trees, they can be bushy in one direction. If the black tree height of real nodes is N, then the minimum path from root to leaf node is N (all black) and maximum path from root to leaf node is 2 * N (alternatively black-red-black-red etc). If you try to add a new node to the bushy path that is at maximum height, the tree will recolour and/or rebalance.

If you want a more balanced search tree you should use an AVL tree. Red-Black trees favour minimal insertion/deletion fixups over finding a node. Your tree is fine.