红黑树

红黑树是一种很常用的自平衡二叉树。之前写过二叉搜索树,我们知道二叉搜索树查找速度是由树的高度决定的,但是因为二叉搜索树对树的平衡没什么限制,如果所有节点都在一个叉上,就变成了链表了。红黑树作为二叉搜索树的同时,用以下五个性质保证了树的平衡:

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色(叶子是NIL节点)。
  4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

因为这些性质,一棵红黑树尽量保持每个路径上节点数差距不大,从来保证了树的查找速度。

红黑树

红黑树是一颗二叉搜索树,其查找方法自然也就是二叉搜索树的查找方法。因为给二叉搜索树节点涂了颜色,树上面的修改操作(如插入、删除)会影响红黑树的某些性质,恢复其性质需要需要O(log n) 次操作。

继续阅读

二叉查找树

二叉查找树英语Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合multiset关联数组等。

二叉查找树是指一棵空树或者具有下列性质的二叉树

  1. 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  2. 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  3. 任意节点的左、右子树也分别为二叉查找树。
  4. 没有键值相等的节点(英语:no duplicate nodes)。

注:维基百科和百度百科上性质【1】和【2】不同,描述中的一个性质会存在键值相等的情况,考虑到性质【4】,是不应该存在这个相等情况的。

注:以上定义摘自维基百科(微幅修改)。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,等于树高,期望为O(log n),最坏为O(n)。

二叉查找树

两个高度相同的二叉查找树

上面的两个二叉查找树树高是一样的,但是查找是速度是相同的。

下面介绍二叉查找树的一些操作:

继续阅读