文章目录
前言
经过之前数据结构的学习,我们知道如果一个二叉树满足:
- 若其左子树非空,则左子树上所有节点各自的值都小于根节点的值
- 若其右子树非空,则右子树上所有节点各自的值都大于根节点的值
- 其左右子树都是一棵二叉查找树。
则它是一个二叉搜索树(Binary Search Trees, BST)。
遍历顺序
对树的遍历,我们来复习一下:
先序遍历
在先序遍历中,对节点的处理工作是在它的诸儿子节点被处理之前(pre)进行的。
先序遍历步骤为:访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。即根左右。
例如下面的这个树:
它遍历的顺序就是ABDECF
后续遍历
和先续遍历不同的是它的访问不是我们所想的从跟开始,而是从左开始:
后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点。即左右根。
例如之前的这个树:它遍历的顺序就是DEBFCA
因此我们可以发现,这个先和后,指的是跟的先后。
中序遍历
在二叉树中还有一种中序遍历,按照我们之前的说法,它是跟的中序:中
序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。即左根右。
故之前的那颗树的遍历顺序是:DBEAFC
如果我们使用设这个BST是T,x是二叉搜索树中的一个结点。如果y是左子树中的一个结点,那么 y.key ≤ x.key;如果y是右子树中的一个结点,那么 y.key ≥ x.key。那么中序遍历的伪代码为:
INORDER-TREE-WALK(x)
if x ≠ NIL
INORDER-TREE-WALK(x.left)
print x.key
INORDER-TREE-WALK(x.right)
INORDER-TREE-WALK(T.root) //从根结点开始
如果x是一棵有n个结点的子树的根,那么调用INORDER-TREE-WALK(x)运行时间O(n),证明省略。
查找BST
二叉搜索树支持SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR等查询操作。在一棵高度为 h 的二叉搜索树上,SEARCH、MINIMUM、MAXIMUM、PREDECESSOR和SUCCESSOR的运行时间为 O(h)
。
查找(Searching)
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-SEARCH(T.root, k)
TREE-SEARCH的运行时间为 O(h),其中 h 为树的高度。
关键字最小元素和关键字最大元素 (Minimum and maximum)
TREE-MINIMUM(x)
while x.left ≠ NIL
x = x.left
return x
TREE-MAXIMUM(x)
while x.right ≠ NIL
x = x.right
return x
TREE-MINIMUM和TREE-MAXIMUM的运行时间均为 O(h),其中 h 为树的高度.
后继和前驱(Successor and predecessor)
TREE-SUCCESSOR(x)
if x.right ≠ NIL
return TREE-MINIMUM(x.right) // leftmost node in right subtree
else // find the lowest ancestor of x whose left child is an ancestor of x
y = x.p
while y ≠ NIL and x == y.right
x = y
y = y.p
return y
TREE-PREDECESSOR(x)
if x.left ≠ NIL
return TREE-MAXIMUM(x.left) // rightmost node in left subtree
else // find the highest ancestor of x whose right child is an ancestor of x
y = x.p
while y ≠ NIL and x == y.left
x = y
y = y.p
return y
TREE-MINIMUM和TREE-MAXIMUM的运行时间均为 O(h),其中为树的高度。
插入和删除(Insertion and deletion)
具体插入与删除的解析,请见:
插入和删除操作会引起二叉搜索树表示的动态集合的变化,但是二叉搜索树的性质保持不变。在一棵高度为 h的二又搜索树上,INSERT和DELETE的运行时间为 O(h)。
插入
向二叉搜索树T中插入结点z,其关键字为 z.key ,伪代码TREE-INSERT如下
TREE-INSERT(T, z)
x = T.root // node being compared with z
y = NIL // y will be parent of z
while x ≠ NIL // descend until reaching a leaf
y = x
if z.key < x.key
x = x.left
else x = x.right
z.p = y // found the location - insert z with parent y
if y == NIL
T.root = z // tree T was empty
else if z.key < y.key
y.left = z
else y.right = z
该过程保持跟踪指针(trailing pointer) y 记录 x 的父结点,TREE-INSERT的运行时间为O(h),其中h为的高度。
删除
从二叉搜索树 T 中删除结点 z 分三种情况
- 情况一: 如果z没有孩子结点,直接删除, z 的父结点指向z的指针置为NIL。
- 情况二: 如果z只有一个孩子结点,将这个孩子结点提升到z的位置,z 的父结点指向z的指针改为指向这个孩子结点。
- 情况三: 如果z有两个孩子结点,找出z的后继 y,让y占据z的位置,z 的右子树变为 y的右子树,z 的左子树变为 y 的右子树。由于y是z的后继,所以y不可能有孩子。
- 如果y 是z的右孩子,用y 替换z。
- 如果y在2的右子树中且y 不是z 的右孩子,先用y 的右孩子结点替换 y,然后用y 替换 z。
子程序TRANSPLANT实现了用某子树原先父结点的指向该子树的指针指向另一棵子树,实现了子树的替换。伪代码如下:
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
TREE-DELETE(T, z)
if z.left == NIL
TRANSPLANT(T, z, z.right) // replace z by its right child
else if z.right == NIL
TRANSPLANT(T, z, z.left) // replace z by its left child
else y = TREE_MINIMUM(z.right) // y is z's successor
if y ≠ z.right // is y farther down the tree?
TRANSPLANT(T, y, y.right) // replace y by its right child
y.right = z.right
y.right.p = y // z's right child becomes y's right child
TRANSPLANT(T, z, y) // replace z by its successor y
y.left = z.left
y.left.p = y // and give z's left child to y which had no left child
TREE-DELETE的运行时间为O(h),其中h为树的高度。
后记
本文介绍了二叉搜索树(Binary Search Trees, BST)的定义和遍历顺序,包括先序遍历、后序遍历和中序遍历。同时,还介绍了BST的查找操作,包括SEARCH、MINIMUM、MAXIMUM、PREDECESSOR和SUCCESSOR等查询操作。文章还讲解了BST的插入和删除操作,包括向BST中插入结点和从BST中删除结点的实现方法。在一棵高度为 h 的BST上,SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT和DELETE的运行时间均为 O(h)。
Comments NOTHING