二叉查找树是这样一种数据结构：它是按二叉树的结构来组织的，节点除了key域外，还包含有left、right和p指针，分别指向自己的左孩子、右孩子和父亲节点。如果儿子或者父亲不存在，则该指针置NULL。二叉查找树又称为二叉排序树。
二叉查找树中关键字的存储方式总是满足：
设x为二叉查找树中的一个节点，如果y是x的左子树中的任意一个节点，则key[y] <= key[x]；如果y是x的右子树中的任意一个节点，则key[y] >= key[x]。因此如果对一棵二叉查找树进行中序遍历的话那么输出的结果将是升序排列的。
一、中序遍历二叉树其算法是简单的，递归算法如下：
1 INORDER-TREE-WALK(x)
2 if x != NULL
3 then
4 INORDER-TREE-WALK(left[x])
5 print key[x]
6 INORDER-TREE-WALK(right[x])
定理：如果x是一棵包含n个节点的子树的根，则调用INORDER-TREE-WALK(x)过程的时间为
θ(n)。
利用递推公式证明还是相对简单的，略。
二、查询二叉查找树
1、查找指定关键字k
给定指向树根的指针和关键字k，返回包含关键字k的指针或者NULL，递归算法如下：
1 TREE-SEARCH(x, k)
2 if x == NULL or k == key[x]
3 then
4 return x
5 if k < key[x]
6 then
7 return TREE-SEARCH(left[x], k)
8 else
9 return TREE-SEARCH(right[x], k)
非递归版本的算法如下：
1 INTERATIVE-TREE-SEARCH(x, k)
2 while x != NULL and k != key[x]
3 do
4 if k < key[x]
5 then
6 x = left[x]
7 else
8 x = right[x]
9 return x
算法复杂度相同，均为O(h)，其中h为树的高度。
2、最大关键字元素和最小关键字元素函数TREE-MINIMUM(x)和TREE-MAXIMUM(x)分别返回二叉查找树的最小关键字元素和最大关键字元素，思想也是简单的，沿着二叉查找树的left指针一直走下去直到left指针为空，则当前节点为最小关键字元素；沿着二叉查找树的right指针一直走下去直到right指针为空，则当前节点为最大关键字元素。复杂度也相同，均问O(h)。
算法如下：
1 TREE-MINIMUM(x)
2 while left[x] != NULL
3 do
4 x = left[x]
5 return x
6
7 TREE-MAXIMUM(x)
8 while right[x] != NULL
9 do
10 x = right[x]
11 return x
3、前趋与后继当找寻一个二叉查找树的中序遍历后继节点的时候，有下面两种情况：
- 如果当前节点的right指针不为NULL，则说明节点有右子树，由于是中序遍历，因此当前节点的后继节点必然是其右子树中关键字值最小的节点，这通过TREE-MINIMUM(right[x])即可得到；
- 如果当前节点的right指针为NULL，则说明节点没有右子树，此时情况稍微有些复杂，可以画图理解一下，其实就是如下情况，沿着当前节点的父指针往上走，只要此节点是是其父节点的右孩子，就继续往上走，直到此节点是其父节点的左孩子或者此节点为空为止，返回此节点的父节点或者NULL。
用图形表示如下：
我们可以看到，如果节点的right[x]为空，则y节点必是x节点的后继节点，除非不包含符合这一条件的y节点，则x的后继节点为NULL。
由此算法如下：
1 TREE-SUCCESSOR(x)
2 if right[x] != NULL
3 then
4 return TREE-MINIMUM(right[x])
5 y = p[x]
6 while y!= NULL and x == right[y]
7 do
8 x = y
9 y = p[y]
10 return y
同理，求节点x的前趋类似：
- 如果当前节点的left指针不为NULL，则说明节点有左子树，当前节点的前趋节点必然是其左子树中关键字值最大的节点，这通过TREE-MAXIMUM(left[x])即可得到；
- 如果当前节点的left指针为NULL，则说明节点没有左子树，此时为如下情况，沿着当前节点的父指针往上 走，只要此节点是是其父节点的左孩子，就继续往上走，直到此节点是其父节点的右孩子或者此节点为空为止，返回此节点的父节点或者NULL。
由此算法如下：
1 TREE-PREDECCESSOR(x)
2 if left[x] != NULL
3 then
4 return TREE-MAXIMUM(left[x])
5 y = p[x]
6 while y != NULL and x == left[y]
7 do
8 x = y
9 y = p[y]
10 return y
两个算法时间复杂度相同，均为O(h)。
三、二叉查找树的插入和删除1、插入对于二叉查找树的插入操作，相对简单，只需要从二叉查找树的根开始向下查找应该插入的位置即可。这个应该插入的位置必然为一叶子节点的left指针或者right指针指向的空域。算法如下：
1 TREE-INSERT(T, z)
2 y = NULL //y指向当前节点的父节点
3 x = root[T] //指向当前节点
4 while x != NULL
5 do
6 y = x
7 if key[z] < key[x]
8 then
9 x = left[x]
10 else
11 x = right[x]
12 p[z] = y
13 if y == NULL //如果为空树
14 then
15 root[T] == z //树根则为z
16 else if key[z] < key[y]
17 then
18 left[y] = z
19 else
20 right[y] = z
算法复杂度为O(h)。
2、删除对于删除一个节点，则情况复杂很多，因为删除操作破坏了二叉查找树的结构，必须调整树的结构，仔细观察发现，不外乎以下三种情况：
- 如果要删除的节点的左右孩子均为空，则直接删除该节点即可，因为这样并没有破坏二叉查找树的结构；
- 如果要删除的节点只有一个孩子（为左孩子或者右孩子均可），则直接将要删除节点的父节点的left指针或者right指针指向要删除节点的孩子节点即可，同时将孩子节点的父指针指向要删除节点的父节点；
- 如果要删除的节点既有左子树又有右子树，则将要删除节点用其后继节点替换，并删除后继节点即可。
为此算法如下：
1 TREE-DELETE(T, z)
2 if left[z] == NULL or right[z] == NULL
3 then //y指向真正需要删除的节点
4 y = z //y要么为要删除的节点
5 else
6 y = TREE-SUCCESSOR(z) //y要么为要删除节点的后继节点
7 if left[y] != NULL
8 then
9 x = left[y]
10 else
11 x = right[y]
12 if x != NULL
13 then
14 p[x] = p[y]
15 if p[y] == NULL
16 then
17 root[T] = x
18 else if y == left[p[y]]
19 then
20 left[p[y]] = x
21 else
22 right[p[y]] = x
23 if y != z
24 then
25 key[z] = key[y]
26 return y
时间复杂度同样为O(h)。
四、随机构造的二叉查找树性能分析
posted on 2011-10-31 16:28
myjfm 阅读(336)
评论(0) 编辑 收藏 引用 所属分类:
算法基础