Ned*_*Ned 5 algorithm red-black-tree binary-search-tree data-structures
在红黑树中K插入和K删除后所需的最大旋转次数是多少？
我正在考虑它的3K,因为在最坏的情况下插入我们为每次插入执行2次旋转,每次删除执行1次旋转.我在这里走在正确的轨道上吗？
G. *_*ach 5
与AVL树相比,其中删除的旋转可以传播到根(尽管插入时最多有一个(双)旋转),RB树需要一个常数(插入时最多2个,删除时最多3个)旋转.在RB树中删除期间以对数方式占用的时间是可以传播到根的重新着色,这意味着插入和删除对于AVL和RB树都具有相同的渐近性.
(如果有兴趣,您可以在此脚本中找到对这些内容的分析.)
关于你的问题,最多3K是正确的(但显然旋转与链接的脚本有点不同).
归档时间：
11 年，7 月 前
查看次数：
1940 次
最近记录：