在计算机科学中,二叉搜索树(Binary Search Tree)(有时称为有序或排序的二叉树)是一种能存储特定数据类型的容器。二叉搜索树允许快速查找、添加或者删除某一个节点,并且它是动态的集合。

      二叉搜索树按照关键字顺序地保存节点,因此查找和其他操作可以使用二叉搜索原理:当在树(或者寻找插入新节点的地方)中查找节点时,它从根节点遍历到叶节点,与每个节点的关键字进行比较,然后基于比较结果,决定继续在左子树或者右子树中进行搜索。平均而言,每次比较将跳过树的大约一半的元素,这使得每次查找,插入或删除一个节点所花费的时间与树的节点个数的对数成(树的高度)正比,比线性表的性能要好很多。

定义

        二叉搜索树是以一棵二叉树来组织,每个节点就是一个对象,包括key、卫星数据,除此之外还包括一些为了维持树结构所需要的信息:left、right、parent,分别指向左孩子、右孩子、父节点。其中如果孩子节点或者父节点不存在时,用NULL表示。根节点是树中唯一一个父节点为NULL的节点。

二叉搜索树具有以下性质

1、如果节点的左子树不空,则左子树上所有结点的值均小于等于它的根结点的值;

2、如果节点的右子树不空,则右子树上所有结点的值均大于等于它的根结点的值;

3、任意节点的左、右子树也分别为二叉查找树;

        在讨论二叉搜索树的操作之前,先看看二叉搜索树的遍历。二叉搜索树可以使用先序遍历(preorder tree walk)、中序遍历(inorder tree walk)和后序遍历(postorder tree walk)。这样命名的依据是根据输出关键字相对于左右子树的位置。

查询

      二叉搜索树还应该可以完成MIN,MAX,Successor和Predecessor操作,即求最小值,最大值,后继和前驱,并且这些操作都可以在o(lgn)的时间内完成。

查找指定关键字

      TREE-SEARCH操作在二叉树中查找一个具有指定的关键字的节点,输入树的根节点指针和关键字k,如果存在,返回节点指针,否则,返回NULL。

最小/最大关键字

        通过从树根开始,沿着left孩子向下搜索,直到遇到nil,那么根据二叉搜索树的性质,如果节点x没有左子树,而x的右子树的关键字肯定都大于x.key,因此此时当前节点一定是整个树中的最小值。

        求取最大、最小关键字的时间复杂度仅为o(lgn),即与树的高度成正比,因为查找过程自上而下形成一条线,线的最大长度为数的高度,如求取最小值的过程:

前驱/后继

        给定二叉搜索树的一个节点,有事需要按照中序遍历的次序查找它的后继,如果所有的关键字互不相同,则一个节点x的后继一定是大于x.key的最小关键字。

case 1:如果右子树不为空,则后继一定是右子树的最小值,即大于x的最小值(右子树的值都大于x节点)

case 2:右子树为空时

1、对于第一种情况比较简单,如果x右子树不为空,那它的后继就是右子树的最左节点,对应伪代码case 1,例如下图寻找68的后继,即寻找68的右子树的最小节点72,同时它也是右子树的最左节点。

2、第二种情况是x的右子树为空,注意x的后继始终是大于x的最小值(或者不存在),所以当x的右子树不存在时大于x的最小值在哪儿呢?我们只需要简单的从x开始沿树而上,找到第一个这样一个节点:它的父节点为空(即根节点)或者它的左孩子是x节点的祖先节点(不一定是直接祖先)。

一个二叉搜索树中除了最大节点外,都有后继。对于前驱节点,和后继节点原理一样,这里不再赘述。

插入

        插入操作会引起二叉搜索树集合的动态变化,因此需要一定的修改来维持二叉搜索树。由于二叉搜索树的性质,即左孩子小于等于父节点,右孩子大于等于父节点,因此插入操作相对简单。

      从树根开始,指针x记录了一条向下的简单路径,通过while循环比较z.key和x.key的大小,使指针x和指针y向下移动,循环结束时则找到一个空的x并作为一个槽,将节点z放到这里(插入),同时保持节点y为节点x的父节点,这样可以很方便的决定插入之后将z作为它的左孩子还是右孩子。

删除

从二叉搜索树中删除一个节点z稍微有点棘手,但总的来说可以分为三种情况:

1、如果z没有孩子节点,那么简单的将它删除,并修改它的父节点,用nil作为孩子节点代替z即可。

2、如果z只有一个孩子,那么将这个孩子提升到z的位置,并修改它的父点,用z的孩子代替z即可。

3、如果z有两个孩子,那么用z的后继y(此时z的后继y一定在z的右子树中,因为z的右孩子不为空)来占据z的位置,此时z的原来的右子树部分称为y的新的右子树,并且z的左子树称为y的新的左子树。这种情况稍微麻烦,因为还与y是否为z的右孩子相关。

第一种情况:节点z没有孩子

这种情况比较简单,我们直接删除节点z即可,并不会影响到二叉搜索树的性质:

第二种情况:节点z只有一个孩子

这种情况也比较简单,直接用节点z的孩子代替节点z即可。其实第一种情况和第二种情况可以归为一个:节点z的孩子个数小于2个,直接用节点z的孩子代替节点z即可,只是节点z没有孩子时是用的nil代替节点z,这里为了更加清楚地说明分了三种情况。

第三种情况:节点z有两个孩子

这种情况稍微复杂一点,因为此时我们需要找到节点z的后继y,而后继节点y又分为y是节点z的直接右孩子或者不是。

1、z的后继y是 z的右孩子

此时可以直接用后继y代替z,而且y的左孩子此时一定为空(因为后继的左孩子一定为空),再用z的左孩子代替y的原来为空的左孩子即可。

2、z的后继y不是 z的右孩子

在这种情况下我们先用y的右孩子x代替y,然后再用y代替z:


因此总的来说,删除操作可以分为两大类:

1、z的孩子总数小于2时,直接用z的孩子代替z即完成了对z的删除。

2、z有两个孩子时:

2.1. z的后继y是z的右孩子:直接用y代替z即可(别忘了将z的左孩子的父节点设置为y)。

2.2. z的后继y不是z的右孩子:先用y的右孩子x代替y,再用y代替z。

总结

因为二叉搜索树的性质,即可以在每个比较之后将数据规模变为原来的一半,因此平均情况下每一个操作都可以在o(lgn)的时间内完成,即花费时间与树的高度成正比。但在最坏的情况下,二叉搜索树就退化为一个链表,此时的时间复杂度退化到了o(n)。但很多改进版的二叉查找树可以使树高为o(lgn),如SBT,AVL树,红黑树等。

参考文献

1、算法导论

2、维基百科

3、visualgo

4、微信公众号《程序员共读》详细讲解二叉搜索树