在红黑树中，自下而上的删除比自下而上的删除更快，空间更高？ [英] In red-black trees is top-down deletion faster and more space efficient than bottom-up deletion?
问题描述
按此页面 http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree .aspx
自上而下的删除是一个红黑树节点删除的实现，通过将红色节点向下推动通过树，从而主动平衡树，使得叶节点被清除被保证是红色的。由于叶节点保证是红色的，所以您不必担心重新平衡树，因为删除红叶节点不会违反任何规则，并且您不必执行任何其他操作，平衡和恢复红黑色。
Per this page http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx "Top-down deletion" is an implementation of a red-black tree node removal that pro-actively balances a tree by pushing a red node down through the tree so that the leaf node which is being removed is guaranteed to be red. Since the leaf node is guaranteed to be red, you don't have to worry about re-balancing the tree, because deleting a red leaf node doesn't violate any rules and you don't have to perform any additional operations to re-balance and restore red-black'ness.
自下而上的删除涉及在树下进行正常的二进制搜索，找到要删除的节点，交换在叶节点（如果找到的节点不是叶节点），然后通过在修复违反黑黑规则的情况下爬回树来恢复红黑树属性。
"Bottom-up deletion" involves doing a normal binary search down the tree to find the node to be deleted, swapping in the leaf node ( if the found node isn't a leaf node), and then restoring the red-black tree properties by climbing back up the tree while fixing red-black rule violations.
自上而下的删除是否减少了重新平衡操作的次数？自上而下的删除是否有可能主动地在下降的过程中重新着色和重新平衡？
Does top-down deletion minimize the number of re-balancing operations? Could it be possible that top-down deletion pro-actively does too many re-colorings and re-balancings on the way down?
这种情况如何：（x）表示红色节点
What about this scenario: (x) denotes a red node
8
_____/ \____
/ \
4 12
/ \ / \
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 15
\
(16)
如果我想删除16，自下而上的删除将不会进行任何重新平衡，但是自上而下的删除会重新将节点重新整理，发现之前复选操作是不必要的：
If I want to delete 16, a bottom-up deletion wouldn't do any rebalancing, but a top-down deletion re-colors the nodes all the way down, before discovering that the recoloring operations were unnecessary:
迭代1：
(8)
_____/ \____
/ \
4 12
/ \ / \
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 15
\
(16)
迭代2：
8
_____/ \____
/ \
(4) (12)
/ \ / \
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 15
\
(16)
迭代3：
8
_____/ \____
/ \
(4) 12
/ \ / \
2 6 (10) (14)
/ \ / \ / \ / \
1 3 5 7 9 11 13 15
\
(16)
然后在迭代4中，发现您不需要按下，因为16已经是红色。所以自上而下的删除更多的时间和空间有效？
Then in iteration 4 you discover that you don't need to push down because 16 is already red. So is top-down deletion more time and space efficient?
推荐答案
从我收集的内容：自上而下的删除在运行过程中不止一次路径中的相同节点。所以，考虑到从根到一个给定节点的简单路径，如果你要对这个路径中的一个节点做一些事情，为什么不这样做呢？它避免不必多次遍历路径的一部分。因此，这节省了时间。
From what I gather: "top-down deletion" avoids traversing the same node in a path more than once during the operation. So, given the simple path from the root to a given node, if you're going to do some thing to a node that's in that path anyway, why not just do it on the way down? It avoids having to traverse over parts of the path more than once. Therefore, this saves time.
类似的原理用于2-3-4树中的多个操作（包括插入）（a，b的特殊子案例
A similar principle is employed for multiple operations (including insert) in 2-3-4 trees (a special sub-case of a,b-trees)
在一般情况下，它是。因为您可以通过少量重新平衡操作来更容易地插入某些内容。
Think that, in the average case, it does. Because you make it potentially easier to insert something afterward with few re-balancing operations.
也许，但这取决于数据集。但是，如上所述。这可能会减少重新着色和重新平衡的数量。
Maybe, but that depends on the data set. However, as mentioned above. This may reduce the number of re-colorings and re-balancings overall.
这篇关于在红黑树中，自下而上的删除比自下而上的删除更快，空间更高？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
