在我看来,看源码是一件既痛苦又兴奋的事。当我们在推敲其中的难点时,是及其痛苦的,但当发现实现代码是那么丝滑简洁时,“wc, nb!”。


1. 导语

如果我们去看关联式容器map、set、multimap、multiset源代码,我们发现绝大部分操作如插入、修改、删除、搜索,均是由其内含的红黑树来完成的,我们有必要去揭开她的神秘面纱,一览她的绝世风姿。

(如果你手头还没有《STL源码剖析》时,强烈建议你现在就去买一本or文末的百度云链接or网路上的其他资源)

关键词:RB-tree、BST、AVL tree 、STL Sources


 从哪里讲起呢?

二叉搜索树,每个节点最多有两个子节点,而每个节点键值一定大于左子树键值节点键值,而小于右子树节点键值。这样一来,就可以提供对数时间的插入和搜索。

STL源码剖析 - RB-tree-LMLPHP

当然,较为复杂的是它的删除操作。

STL源码剖析 - RB-tree-LMLPHP

STL源码剖析 - RB-tree-LMLPHP

  上述例子是在二叉树平衡的情况下进行的。平衡即左右子树高度相近,完全平衡则要求左右子树高度(深度/层数)完全相等。要是完全平衡的条件下,我们的搜索和插入操作就会是对数时间,这无疑是相当快的(当然比起Hashtable的大致O(1)来说是较慢的),这在关联式容器中是我们所追求的。因为它们的底层均不是线性结构,能达到常数时间的查找/搜索。

  但是要知道,维护一个二叉树的完全平衡是非常耗时的,比如我插入之后,很大概率就会使得二叉树不完全平衡,就需要复杂度旋转移位操作,这对于插入来说非常不划算,也就是说,我们没必要为了平衡而平衡,只要达到大致平衡,就可以得到统计上的对数查找插入时间。

那么进入我们的正题,平衡二叉搜索树。


2. 平衡二叉搜索树

这里的平衡,是指没有任何节点的深度过大,而非绝对的平衡。

代表结构:RB-tree、AVL-tree、AA-tree

本片主要介绍红黑树,AVL-tree将在其他篇章中讲解。


3. RB-tree

红黑树,一种自平衡的二叉查找树。它的最坏情况运行时间也是良好的,并且在实践中是高效的,它可以在O(log n)时间内做查找,插入和删除。(来自百度百科)

无疑,它的实现是非常复杂的,搜索几乎是是它最为简单的操作,复杂度O(log n),最坏也是如此。而插入和删除就比较困难了,查找到插入节点/删除节点复杂度O(log n),在插入时、插入后、删除后都需要满足它的红黑规则限定

05-22 16:26