数据结构--平衡二叉树和红黑树_红黑树与平衡二叉树数据库

作者：从前慢现在也慢 | 2024-06-27 12:12:37

踩

红黑树与平衡二叉树数据库

来了来了，今天就要讲讲听起来就很厉害的红黑树。

说道红黑树，不得不先弄明白平衡二叉树的概念，我在上一篇博客中简单提到了平衡二叉树的概念。

平衡二叉树

平衡二叉树又叫AVL树。在平衡二叉树中，任意结点对应的两棵子树的高度差最大为1，因此它也被称为高度平衡树。每个结点除了关键字之外，它还会记录一个平衡因子，这个平衡因子=左子树的高度-右子树的高度。因此平衡因子取值只能为0，+1或-1。
拿一张维基百科上的图来说，这是个平衡二叉树（每个结点的平衡因子的取值都在{0，+1，-1}）
在这里插入图片描述
树上的查找操作的时间复杂度依赖于树的高度，对于平衡二叉树来说，高度为 $log_2N$

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