12-二叉搜索树-算法导论

2016-06-12 23:49:59   0  举报





仅支持查看

AI智能生成

《算法导论》中的12-二叉搜索树章节介绍了一种特殊的二叉树——二叉搜索树。这种数据结构具有一些独特的性质，例如：每个节点都有一个值，且所有左子树上的值都小于该节点的值，所有右子树上的值都大于该节点的值。此外，对于任何给定的节点，其左、右子树也都是二叉搜索树。这一章详细阐述了如何在这种数据结构上进行各种操作，如插入、删除和查找等，并给出了相应的算法实现。通过学习这一章节，读者可以深入理解二叉搜索树的原理和应用，为进一步学习其他高级数据结构和算法打下坚实的基础。

作者其他创作

大纲/内容

几个概念

二叉树

二叉树是一个连通的无环图，并且每一个顶点的度不大于3；且区分左右子树（但是没说左一定比右小哈）

二叉搜索树

一种二叉树，父节点与子节点间有特定的大小关系：x.left.key<=x.key<=x.key （这是二叉搜索树必须满足的性质，所以进行插入等操作也必须保证这种结构不变）

完全二叉树

一种二叉树，满足：假定树的高度为h，那么第1~h-1层都是满二叉树，只有h层可能会有叶子节点，且叶子节点都是从左到右依次排列

二叉搜索树的操作

中序遍历Inorder-Tree-Walk(x)

时耗：对于有n个节点子树的跟，时耗为F(n)

算法

if x~=NIL Inorder-Tree-Walk(x.left) print x.key; Inorder-Tree-Walk(x.right)

查询

递归实现Tree-Search(x,k)

算法

if x==NIL or x.key==k return x if k

时耗：O(h),h为树的高度或者写作 O(logn), n为子节点个数

迭代实现Iterative-Tree-Search(x,k)

while x~=NIL and x.key~=k if k

这比递归实现的效率要高很多额

最大关键字元素和最小关键字元素

Tree-Min(x)

while x.left~=NIL x = x.left; return x (根据 while x~=NIL 是无法返回所需的值的，因为指针不是双向)

Tree-Max(x)

同上

时耗： O(h)

前驱和后继 (如果所有关键字都不同，那么后继是大于x.key的最小关键字的节点)

Tree-Successor(x)

算法思路： 1）如果x的有子树不为空，那么该节点所求后继节点； 2）如果右子树空，那么考察从x往回找，y代表x的双亲节点，通过不断回溯来更新x和y,知道找到第一个有左子树且x在左子树上的双亲节点即为所求后继

if x.right~=NIL return Tree-Min(x.right) y = x.p (即x的后继) while y~=NIL and x==y.right x = y; y = y.p; return y

插入Tree-Insert(T,z) (T为二叉搜索树， z为待插入节点)

思路：首先从根节点开始找到能插入z的叶子节点位置y(key的大小满足二叉搜索树即可) 然后，根据z.key 与 y.key大小比较将z作为y的左或右子树

y = NIL x = T.root while x~=NIL y = x if z.key

时耗：O(h)

删除Tree-Delete(T,z)

功能：删除二叉搜索树T中的节点z

基本思路

分三种情况讨论： 1、若z无孩子节点，直接用NIL代替掉z即可 2、若z有一个孩子节点，那么用z的孩子节点代替z,并修改z的父节点为z的孩子的父亲 3、若z有两个孩子，那么找z的后继y且y没有左孩子，并让y占据z的位置。z原来的右子树部分称为y的新右子树，z原来的左子树称为y的新的左子树

算法

if z.left==NIL Transplant(T, z, z.right) elseif z.right==NIL Transplant(T,z, z.left) else y = Tree-Min(z.right) if y.p~=z Transplant(y,y.right);//注意y原来的左孩子被认为是空的所以不予考虑 y.right = z.right y.right.p = z.p Transplant(T,z,y) y.left = z.left y.left.p = y

时耗 O(h)

移动子树Transplant(T,u,v)

功能

用子树v去替换掉子树u并使得u的双亲的孩子为v (注意：此函数没有更新u，v的左右孩子节点，所以移动时还需要其他函数补上这一操作) (另外值得注意的是，经过此操作，虽然v的父亲节点发生了变化，但是其孩子节点暂时是没变也没丢的额)

算法

if u.p==NIL T.root = v elseif u==u.p.left u.p.left = v else u.p.right = v if v~=NIL v.p = u.p

随机构建二叉搜索树

概念：即按随机的次序将关键字插入到一棵空数里

Th: 具有n个不同关键字的随机构建二叉搜索树的期望高度是O(lgn)