二叉搜索树
定义及性质:
- 若它的左子树不为空,则它的左子树的所有结点都小于根结点
- 若它的右子树不为空,则它的右子树的所有结点都大于根节点
- 任一子树也满足二叉搜索树
复杂度
插入和查找的平均复杂度的是O(lgN).但在最坏情况下,二叉搜索树退化成链表,复杂度变为O(N)
删除操作需要与查找复杂度差不多.删除=查找O(lgN)+删结点(O(1)),最坏也是O(N)
搜索
1. 查找指定关键字
TreeSearch(tree,x)
if tree.key==x
return x
if tree.key<x
return TreeSearch(tree.right,x)
if tree.key>x
return TreeSearch(tree.left,x)
2. 最小值
根据二叉搜索树的性质,树的最小值在最左下
TreeMin(tree)
while tree.left != null
x=x.left
return x.key
3. 最大值
根据二叉搜索树的性质,树的最大值在最右下
TreeMax(tree)
while tree.right != null
x=x.right
return x.key
4. 后继
后继表示在中序遍历中,位于tree的下一位的结点
过程:
1. 如果右子树不为空,则返回右子树的最小值
2. 如果右子树为空,则考虑其父结点
1. 如果tree是父结点的左孩子,则父结点是后继
2. 如果不是左孩子,则继续往上找
最后一个结点没有后继
TreeNext(tree)
if tree.right != null
return TreeMin(tree.right)
else
while tree.p != null
if tree.p.left==tree
return tree.p
tree=tree.p
插入
根据二叉搜索树的性质,选择左/右子树
下面的伪代码要注意维护父结点,在每次选择左/右子树后,都维护node的父结点为parent.最后再根据node与父结点的大小,决定node作为父结点的左孩子还是右孩子
TreeInsert(tree,node)
while tree != null
parent = tree.p
if tree.key>node.key
tree=tree.left
else
tree=tree.right
node.p=parent
if node.key>parent.key
parent.right=node
else
parent.left=node
删除
在树结构删除向来都是麻烦的处理
分为以下情况:
-
被删除结点的孩子个数小于2,则将结点的孩子替换为被删除结点
-
被删除结点有两个孩子
-
被删除结点的后继是该结点的右孩子
如果后继是右孩子,那么这个后继的左结点必是null.因此只要将该后继替换为被删除结点即可
-
被删除结点的后继不是右孩子
首先将后继的右孩子替换后继,然后将后继替换被删除结点
-
注意到若被删除结点有两个孩子,则必定是用后继结点替换该被删除结点.
在情况2.2下相当于是先将后继调整为被删除结点的右孩子,变成情况2.1
// 将结点u替换成结点v
TRANSPLANT(u,v)
if u==u.p.left
u.p.left=v
else
u.p.right=v
if v != null
v.p=u.p
TreeDelete(z)
// 若右孩子为null,则直接用左孩子替换,即使左孩子也为null
if z.right==null
TRANSPLANT(z,z.left)
// 若左孩子为null,则用右孩子替换
else if z.left==null
TRANSPLANT(z,z.right)
else
// 获取后继结点
next=TreeNext(z)
if z.right != next
// 后继结点的右孩子替换后继结点
TRANSPLANT(next,next.right)
// 被删除结点的右孩子成为后继结点的右孩子
next.right=z.right
next.right.p=next
// 后继结点替换被删除结点
TRANSPLANT(z,next)
// 被删除结点的左孩子成为后继结点的左孩子
next.left=z.left
next.left.p=next