Fairly deleting nodes in a binary search tree

Question

The idea of ​​removing node in BST:

• If the node does not have a child, delete it and update the parent pointer to this node as null

• If the node has one child, replace the node with its children by updating the node's parent pointer with its child

• If the node has two children, find the predecessor of the node and replace it with your predecessor, also update the parent pointer of the predecessor by pointing to its only child (which can only be a left child)

the latter case can also be accomplished using a successor instead of a predecessor!

He said that if we use the predecessor in some cases and the successor in some other cases (giving them equal priority), we can have better empirical performance,

Now the question is, how is this done? based on what strategy? and how does it affect performance? (I think in terms of performance they mean time complexity)

I think we should choose a predecessor or successor in order to have a more balanced tree! but I don’t know how to choose which one to use!

One solution is to randomly select one of them (just chance), but is it not better to have a strategy based on a tree structure? but the question is: WHEN choose WHICH?

Answer 1

As you said, this is a matter of balance, therefore, in general, a method that upsets the balance is preferable. You can hold some indicators to measure the balance level (for example, the difference between the maximum and minimum sheet height, average height, etc.), but I'm not sure if this is worth the overhead. In addition, there are self-balancing data structures (red-black, AVL-trees, etc.) that mitigate this problem by rebalancing after each deletion. If you want to use a basic BST, I suggest that the best strategy without a priori knowledge of the tree structure and deletion sequence would be to switch between the two methods for each deletion.

Answer 2

The fact is that this is a fundamental problem - finding the right removal algorithm for BST. For 50 years, people tried to solve it (as at the merger), and they did not find anything better than the usual algorithm (with the removal of the predecessor / successor). So what is wrong with the classic algorithm? Actually, this eliminates the imbalance of the tree. After some random add/remove operations, you will get an unbalanced tree with a height of sqrt(n) . And this regardless of what you choose - to remove the successor or predecessor (or randomly chosen beetwen in these ways) - the result is the same.

So what to choose? I assume that random (succ or pred) deletion will delay the imbalance of your tree. But, if you want to have an absolutely balanced tree, you need to use red-black or something like that.