红黑树的直觉
The intuition of red-black tree
我想了解红黑树的工作原理。我了解算法，如何在插入和删除操作后修复属性，但我不清楚。为什么红黑树比二叉树更平衡？我想理解直觉，为什么旋转和固定树属性会使红黑树更平衡。
谢谢。
假设您通过按顺序插入以下项目来创建普通二叉树：1、2、3、4、5、6、7、8、9。每个新项目将始终是树中最大的项目，因此作为最右边的可能节点插入。你 "tree" 看起来像这样：
1
\
2
\
3
.
.
.
9
在红黑树（或任何类型的平衡二叉树）中执行的旋转确保任何节点的左子树或右子树都不会明显比另一个更深（通常，高度差为 0 或1，但任何常数因子都可以。）这样，运行 时间取决于树的高度 h 的操作总是 O(lg n)，因为旋转保持 属性 即 h = O(lg n)，而在上面显示的最坏情况下 h = O(n).
特别是对于红黑树，节点着色只是一种簿记技巧，有助于证明旋转始终保持 h = O(lg n)。不同类型的平衡二叉树（AVL 树、2-3 树等）使用不同的簿记技术来维护相同的 属性.
Why red-black tree is more balanced than binary search tree?
因为红黑树保证了任意顺序的插入、删除和查找的O(logN)性能。
Why rotations and fixing tree properties makes red-black tree more balanced?
除了任何二叉搜索树必须遵守的一般性质外，红黑树还遵守以下性质：
- 没有节点有两个红色 link 连接到它。
- 从根到空 link 的每条路径都有相同数量的黑色 link。
- 红色link向左倾斜。
现在我们要证明以下命题：
命题。在最坏的情况下，树的高度≤ 2 lg N。
证明。
由于从根到任何空 link 的每条路径都具有相同数量的黑色 link 并且两个红色 link 永远不会在一行中，因此最大高度将始终小于最坏情况下不大于 2logN。
虽然已经很晚了，但由于我最近在研究 RBT，并且一直在为为什么一些神奇的旋转和着色平衡树的直觉而苦苦挣扎，并且在思考与 OP 相同的问题
why rotations and fixing tree properties makes red-black tree more balanced
经过几天的“研究”，灵光一现，决定详细写一下。我不会在这里复制粘贴，因为某些格式不正确，因此任何有兴趣的人可以从 github 中查看。我试图用大量的图像和模拟来解释。希望有一天它能帮助碰巧在这个线程中搜索相同问题的人:)
我想了解红黑树的工作原理。我了解算法，如何在插入和删除操作后修复属性，但我不清楚。为什么红黑树比二叉树更平衡？我想理解直觉，为什么旋转和固定树属性会使红黑树更平衡。
谢谢。
假设您通过按顺序插入以下项目来创建普通二叉树：1、2、3、4、5、6、7、8、9。每个新项目将始终是树中最大的项目，因此作为最右边的可能节点插入。你 "tree" 看起来像这样：
1
\
2
\
3
.
.
.
9
在红黑树（或任何类型的平衡二叉树）中执行的旋转确保任何节点的左子树或右子树都不会明显比另一个更深（通常，高度差为 0 或1，但任何常数因子都可以。）这样，运行 时间取决于树的高度 h 的操作总是 O(lg n)，因为旋转保持 属性 即 h = O(lg n)，而在上面显示的最坏情况下 h = O(n).
特别是对于红黑树，节点着色只是一种簿记技巧，有助于证明旋转始终保持 h = O(lg n)。不同类型的平衡二叉树（AVL 树、2-3 树等）使用不同的簿记技术来维护相同的 属性.
Why red-black tree is more balanced than binary search tree?
因为红黑树保证了任意顺序的插入、删除和查找的O(logN)性能。
Why rotations and fixing tree properties makes red-black tree more balanced?
除了任何二叉搜索树必须遵守的一般性质外，红黑树还遵守以下性质：
- 没有节点有两个红色 link 连接到它。
- 从根到空 link 的每条路径都有相同数量的黑色 link。
- 红色link向左倾斜。
现在我们要证明以下命题：
命题。在最坏的情况下，树的高度≤ 2 lg N。
证明。
由于从根到任何空 link 的每条路径都具有相同数量的黑色 link 并且两个红色 link 永远不会在一行中，因此最大高度将始终小于最坏情况下不大于 2logN。
虽然已经很晚了，但由于我最近在研究 RBT，并且一直在为为什么一些神奇的旋转和着色平衡树的直觉而苦苦挣扎，并且在思考与 OP 相同的问题
why rotations and fixing tree properties makes red-black tree more balanced
经过几天的“研究”，灵光一现，决定详细写一下。我不会在这里复制粘贴，因为某些格式不正确，因此任何有兴趣的人可以从 github 中查看。我试图用大量的图像和模拟来解释。希望有一天它能帮助碰巧在这个线程中搜索相同问题的人:)