在计算机科学中,二叉搜索树(Binary Search Tree)(有时称为有序或排序的二叉树)是一种能存储特定数据类型的容器。二叉搜索树允许快速查找、添加或者删除某一个节点,并且它是动态的集合。 二叉搜索树按照关键字顺序地保存节点,因此查找和其他操作可以使用二叉搜索原理:当在树(或者寻找插入新节点的地方)中查找节点时,它从根节点遍历到叶节点,与每个节点的关键字进行比较,然后基于比较结果,决定继续在左子树或者右子树中进行搜索。平均而言,每次比较将跳过树的大约一半的元素,这使得每次查找,插入或删除一个节点所花费的时间与树的节点个数的对数成(树的高度)正比,比线性表的性能要好很多。

定义

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

二叉搜索树具有以下性质:

  1. 如果节点的左子树不空,则左子树上所有结点的值均小于等于它的根结点的值;
  2. 如果节点的右子树不空,则右子树上所有结点的值均大于等于它的根结点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;

二叉树

比如在上图中根节点的关键字为6,左子树有关键字2、4和5,均不大于6;右子树有关键字7和8,均不小于6。这个性质对树中的每个节点都成立,也就是说,二叉搜索树的定义是递归的。

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

INORDER-TREE-WALK(x)
	if x != nil  // 如果节点不为空
		INORDER-TREE-WALK(x.left)  // 首先递归地遍历左孩子,直到左孩子为空
		print x.key     // 输出当前节点(显然第一次运行到这里时,它是最小值,因为它是整棵树的最左节点)  
		INORDER-TREE-WALK(x.right)  // 递归地遍历右孩子

对于上图中的二叉搜索树,动态过程如下,这样输出结果为:2,4,5,6,7,8,即按照从小到大的顺序排列。因为输出时一直遍历左孩子,知道遇到第一个左孩子为空的节点,将它输出,然后出栈返回继续输出。

file

查询

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

查找指定关键字

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

TREE-SEARCH(x, k)
	if x == nil or k == x.key  //如不存在或者找到,直接返回
		return x
	if k < x.key                    //如果小于当前节点,根据性质,在左子树中搜索
		return TREE-SEARCH(x.left, k)
	else                          //如果大于等于当前节点,根据性质,在右子树中搜索
		return TREE-SEARCH(x.right, k)

比如查找关键字为5的节点,首先从根节点6开始,与5进行比较,因为5小于6,因此在节点6的左子树继续搜索。到达节点4时因为5大于4,所以在4节点的右子树搜索,这样就顺利找到了节点5,此时函数将返回指向节点5的指针。如果找不到目标节点,TREE-SEARCH函数将返回nil。整个搜索过程如下:

搜索过程

最小/最大关键字

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

TREE-MINIMUM(x)
	while x.left != nil  // 沿着左子树一直深入搜索下去,直到遇到左子树为空的节点,此时当前节点为最小值
		x = x.left
	return x

同理,最大关键字的伪代码如下:

TREE-MAXIMUM(x)
	while x.right != nil  // 沿着右子树一直深入搜索下去,直到遇到右子树为空的节点,此时当前节点为最大值
		x = x.right
	return x

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

求取最小值

前驱/后继

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

TREE-SUCCESSOR(x)
	if x.right != nil   //case 1:如果右子树不为空,则后继一定是右子树的最小值,即大于x的最小值(右子树的值都大于x节点)
		return TREE-MINIMUM(x.right)
	y = x.p    // case 2:右子树为空时
	while y != nil and x == y.right
		x = y   // 变量x代表节点原始x的祖先,如果找到x,它是父节点的左孩子,则循环终止
		y = y.p   // y 代表节点x的父节点,如果x是y的左孩子,循环终止,并且返回y
	return y

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

寻找68的后继

2.第二种情况是x的右子树为空,注意x的后继始终是大于x的最小值(或者不存在),所以当x的右子树不存在时大于x的最小值在哪儿呢?我们只需要简单的从x开始沿树而上,找到第一个这样一个节点:它的父节点为空(即根节点)或者它的左孩子是x节点的祖先节点(不一定是直接祖先)。例如下图中为了寻找17的后继,沿着树上升,首先以此遇到了节点1311,它们均不符合条件,因为它们不是父节点的左孩子。当遇到节点10时,此时x指向节点10y指向节点19,并且节点10是节点19的左孩子,符合条件,所以返回节点y,它是节点x的后继。

寻找17的后继

再举一个例子,下图为了找15的后继,仍然沿着树上升,直到遇到节点10(此时伪代码中的变量x指向节点10):它是15的祖先,而且是左孩子。所以此时返回节点10的父节点19,即节点15的后继。

寻找15的后继

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

插入

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

将一个节点插入到二叉搜索树中,需要调用TREE-INSERT,该过程以节点z作为输入,其中z.left = nil, z.right = nil, z.key = 将要插入数据的关键字

TREE-INSERT(T, z)
	y = nil
	x = T.root
	while x != nil //循环结束后,x一定为空,此时x即为节点z要插入的地方
		y = x    //在这里给y赋值,保证循环结束后y始终是x的父节点
		if z.key < x.key
			x = x.left
		else
			x = x.right
		z.p = y  //  y始终是x的父节点,为了插入z,需要让z的父节点指向x的父节点,即指向y
		if y == nil  //  如果y为空,说明插入时是一棵空的树,需要将树根指向z
			T.root = z
		elseif z.key < y.key   //  判断节点z是y的左孩子还是右孩子
			y.left = z
		else
			y.right = z

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

file

上图为了在树中插入节点46,首先x指向根节点,节点46与根节点68x节点)比较,小于68,因此指针x指向根节点(x节点)的左孩子62,然后一直下移。注意当x指向45的时候,节点46大于45,因此将x指向节点45的右孩子,此时xnil了,循环结束,也就找到了节点46的位置:节点45的右孩子。然后进行一些操作将节点46插入到树中即可。

删除

从二叉搜索树中删除一个节点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即可,并不会影响到二叉搜索树的性质:

file

用动图来表示就是:

file

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

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

file

例如如下图,当节点42只有左孩子时,直接将42的父节点6的右孩子指向节点29,将节点29的父节点设置为节点6即可:

file

或者只有右孩子时也是如此,直接将94的左孩子指向7878的父节点指向94即可: file

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

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

  1. z的后继yz的右孩子 此时可以直接用后继y代替z,而且y的左孩子此时一定为空(因为后继的左孩子一定为空),再用z的左孩子代替y的原来为空的左孩子即可。 file 用动图表示删除节点67就是: file

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

file

file

用动图表示删除节点50就是用74代替73,即将73的父节点82的右孩子指向74,74的父节点设置为82,然后再用73代替50,即将50左孩子31设置为73的左孩子,50的右孩子82设置为73的右孩子: file

为了实现删除过程的伪代码,我们需要定义一个子过程TRANSPLANT,它是用为了用以v为根的子树替换以u为根的子树,让u的双亲节点变为v的双亲节点,即让v称为u的双亲节点的孩子:

TRANSPLANT(T, u, v)
	if u.p == nil   // 当u位树的根节点时,直接将树的根节点指向v
		T.root = v
	elseif u == u.p.left   // 如果u是左孩子,则u的父节点的左孩子指向v
		u.p.left = v
	else    // 如果u是右孩子,则u的父节点的右孩子指向v
		u.p.right = v
	if v != nil   
		v.p = u.p    // 将v的父节点设为u的父节点

然后实现具体的删除过程:

TREE-DELETE(T, z)
	if z.left == nil  // 如果左孩子为空,则直接用右孩子代替z即可,而不管右孩子是否为空(右孩子为空时对应情况一否则对应情况二)
		TRANSPLANT(T, z, z.right)
	elseif z.right == nil  // 右孩子为空,直接用做孩子代替z
		TRANSPLANT(T, z, z.left)
	else y = TREE-MINIMUM(z.right)  // 左右孩子均不为空,找到z的后继y,即z的右子树的最小值,对应第三种情况
		if y.p != z   // 如果z的后继y不是z的右孩子,对应第三种情况的2
			TRANSPLANT(T, y, y.right)  // 用y的右孩子代替y
			y.right = z.right    // 将y的右孩子指向z的右孩子
			y.right.p = y     // 将y的右孩子(原来的z的右孩子)的父节点设为y
		TRANSPLANT(T, z, y)  // 用y代替z
		y.left = z.left
		y.left.p = p

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

  1. z的孩子总数小于2时,直接用z的孩子代替z即完成了对z的删除。
  2. z有两个孩子时: 2.1. z的后继yz的右孩子:直接用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