二叉查找树

二叉查找树英语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)。

二叉查找树

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

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

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

继续阅读