第12章 二叉搜索树
2019-11-08 本文已影响0人
明若晴空
12.1、二叉搜索树
二叉搜索树，使用一个链表数据结构来表示结点。每个结点是一个对象，包含属性key、left、right、p，分别代表其值、左孩子、右孩子和父节点。
子结点或父节点不存在时，属性值为NIL。
根节点是树中唯一父指针为NIL的结点。
二叉搜索树的性质：
二叉搜索树的每个结点，都满足其左子树上的结点都小于等于该节点的值，其右子树上的结点都大于等于该节点的值。
定理 12.1：
一棵有n个结点的树，使用中序遍历法需要 O(n)时间。
12.2、查询二叉搜索树
查找
在二叉搜索树上的查询的运行时间为O(h)，其中h为树的高度。
其搜索伪代码如下：
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);
最大关键字搜索和最小关键字搜索
搜索最小关键字的伪代码：
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(h)，其中h为树的高度。
后继和前驱
按照中序遍历法，获取一个节点的后继的伪代码：
TREE-SUCCESSOR(x)
if x.right不等于nil
return TREE_MINIMUM(x.right);
y = x.p;
while y 不等于NIL, and x == y.right
x = y;
y = y.p;
return y;
说明：
- 节点x的右子树非空，那么其后继就是右子树中最小的结点；
- 结点x的右子树为空，并有一个后继，那么这个后继就是结点x的有左孩子的最底层（最靠近根节点）的祖先，该后继也是结点x的祖先。
按照中序遍历法，获取一个节点的前驱的伪代码：
TREE-PREDECESSOR(x)
if x.left 不等于 nil
return TREE-MAXIMUM(x.left);
y = x.p;
while y 不等于nil and x == y.left
x= y;
y = y.p;
return y;
12.3、插入和删除
插入
TREE-INSERT(T,z)
y = nil;
x = T.root;
while (x 不等于 nil)
y = x;
if z.key < x.key
x = x.left;
else
x = x.right;
z.p = y;
if y == nil
T.root = z;
else
if y.key <= z.key
y.right = z;
else
y.left = z;
说明：
- 遍历过程中，y是记录z的父节点位置；
- while循环中向右或向左移动，向下遍历寻找z的应该插入的位置，即x为nil的位置，此时记录x的父节点y；
- 最后，设置新节点z的父节点，并设置z为父节点的左子节点或右子节点。
删除
二叉树删除子节点z的几种情况：
- z没有左孩子，就直接用右孩子来替换z。右孩子可以是nil，也可以不是nil。
- z有左孩子，并且只有这一个孩子，就直接用左孩子来替换z。
- z既有左孩子，又有右孩子。这时，要在z的右子树中寻找z的后继y。这个后继y肯定没有左孩子。那么这种情况又分为两种：y是z的右孩子和y不是z的右孩子
3.1. 后继y，是z的右孩子，就直接用y替换z，继续保留y的右孩子（y是没有左孩子的）。
3.2. 后继y，在z的右子树中，但是不是z的右孩子。这种情况下，先用y的右孩子替换y的位置（y没有左孩子），再用y替换z的位置。
这个过程中，涉及到移动子树，因此要先定义一个移动子树的过程TRANSPLANT。主要是要替换树的父节点
在树T中，用子树v替换子树u，移动子树的伪代码：
TRANSPLANT(T, u, v)
if u.p == nil
T.root = v;
else if u == u.p.left
u.p.left = v;
else
u.p.right = v;
if v != nil
v.p = u.p;
利用TRANSPLANT移动子树的过程，从二叉搜索树中删除节点z的伪代码：
TREE-DELETE(T,z)
//对应z没有左孩子节点
if z.left == nil
TRANSPLANT(T, z, z.right);
//对应z有左孩子节点，但是没有右孩子节点
else if z.right == nil
TRANSPLANT(T, z, z.left);
else
//对应z既有左孩子节点，又有右孩子节点，先去右子树中找z的后继
y = TREE-MINIMUM(z.right);
//对应后继y不是z的右孩子，用y构建z的父节点的子树
if y.p != z
TRANSPLANT(T, y, y.right)
y.right = z.right;
y.right.p = y;
//对应后继是z的右孩子的情况，直接用z的右孩子替换z的位置
TRANSPLANT(T, z, y)
y.left = z.left;
y.left.p = y;
插入和删除的运行时间均为O(h)，h为树的高度 **
12.4、随机构建二叉搜索树
随机构建二叉搜索树定义如下：
按随机次序插入n个关键字到一棵初始空树中，从而生成的树。
一棵n个不同关键字的随机构建二叉树的期望高度为O(lg n);**
