最近研究了一下红黑树的一些性质和思想, 在这里记录一下.

Map, 或者在 Python 等一些语言中叫做 dictionary 的常用的以键值对形式储存的数据结构一般有两种实现方式, 在 C++ 的 STL 中使用了红黑树的方式, 而在Python中使用了哈希表的方式.

一般认为采用哈希表的方式查找删除的时间复杂度为 O(1), 而红黑树为 O(logn).

Python 中的哈希表使用开放寻址法解决冲突.

对于普通的二叉查找树来说, 查找和插入的时间复杂度在最坏的情况下可能会变成 O(n), 即完全偏向一边的不平衡情况使其成为一个单链表. 如果只是在树的叶子上增加节点而不进行其他的调整, 很容易会使只向下增长的树不平衡. 为了保证 O(logn) 的时间复杂度, 我们需要一种动态的机制, 来调整树的父节点, 乃至于根节点.

红黑树是一种动态调整的实现方式. 红黑树其实是在 2, 3-树 的基础上实现的. 他们也完全可以等价的转换. 不过 2, 3-树 在程序的实现上比较复杂, 而且查找操作也和二叉搜索树有一些不同, 所以在程序实现中一般使用红黑树.

2, 3-树 和红黑树他们共同的思想是, 将树的叶子节点上的操作造成的影响, 逐步的传递给父节点, 按照一定的方式对当前子树进行调整. 父节点再传递给它的父节点, 调整更大一些的子树. 最终传递到根节点, 调整整颗树.

可以这样理解, 在红黑树中, 用红色来标记正在累计调整的节点. 当节点M的两个子节点均被标记, 则M取消子节点的标记, 并标记自己, 使调整向根节点传递.