pas*_*ena 10 c++ atl avl-tree red-black-tree data-structures
我已经在几个地方阅读了它,可以更快地搜索树,但无法理解.据我了解:红黑树的最大高度= 2*log(N + 1)AVL树的高度= 1.44*标识(N + 1)
是因为AVL更短吗？
And*_*rei 16
是.
查找项目所需的步骤数取决于项目与根之间的距离.
由于AVL树被打包得更紧(即它具有更低的最大高度),这意味着更多的项目更接近根,而不是红黑的情况.
额外的紧密包装也意味着AVL树在插入元素时需要更多的工作.任何应用程序的最佳选择取决于它是插入密集型还是搜索密集型...
小智 5
如果输入键几乎是上升/下降,则AVL树优于红黑树,因为那时我们必须进行单次旋转(左 - 左或右 - 右)以添加该元素.此外,由于树将紧密平衡,搜索也会更快.
但是对于随机选择的输入键,RBTree更好,因为与AVL相比,它们需要更少的旋转插入.
总的来说,它取决于输入序列,它将决定我们的树是如何倾斜的,以及执行的操作.对于插入密集型使用红黑树和搜索密集型使用AVL.