Sal*_*ami 5 algorithm red-black-tree
我一直在实现我自己的红黑树版本,主要基于维基百科的算法(http://en.wikipedia.org/wiki/Red-black_tree).它在很大程度上相当简洁,但有一部分我想澄清.
从具有2个非叶子(非NULL)子节点的树中删除节点时,它表示将任一方的子节点移动到可删除节点中,并删除该子节点.
基于此,我对哪一方要删除感到困惑.我是否随机选择一侧,我是否在两侧之间交替,或者我是否会在未来的每次删除时都坚持到同一侧？
如果您对输入数据没有任何先验知识,则无法知道哪一方更有利于成为新的中间节点或新的子节点.
因此,您可以应用最适合您的规则(最容易编写/计算 - 可能"始终采用左侧").采用随机方案通常只会引入更多不需要的计算.