红黑树RBTree原理(超易懂)

作者：菜鸟追梦旅行 | 2024-03-16 01:21:43

踩

rbtree

二叉查找树由于在频繁的动态更新过程中，可能会出现树的高度远大于 log2n的情况，所以就会导致各个操作效率下降，最坏的情况下就会退化为链表，变为O(n)．很明显，想要解决这个问题，有效的一种办法就是使得树的高度不要差很多，也就是平衡它．

最先发明的平衡二叉查找树是AVL树，（它严格符合平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过 1，是一种高度平衡的二叉查找树。）但是在工程中，我们经常听到的通常是红黑树，而不是AVL树．那么为什么工程中都喜欢用红黑树，而不是其他平衡二叉查找树呢？

平衡二叉树是严格按照规定执行，每次的插入，删除，都就会引发树的调整

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/246025