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

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





仅支持查看

AI智能生成

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

作者其他创作

大纲/内容

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

几个概念

二叉树

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

二叉搜索树

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

完全二叉树

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

二叉搜索树的操作

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

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

算法

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

查询

while x~=NIL and x.key~=k\u00A0 \u00A0 if kx.key\u00A0 \u00A0 \u00A0 \u00A0x = x.left\u00A0 \u00A0 else\u00A0 \u00A0 \u00A0 x = x.rightreturn x

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

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

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)

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

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

y = NILx = T.rootwhile x~=NIL y = x if z.keyx.key x = x.left else x = x.rightz.p = xif y==NIL T.root = z // tree is emptyelseif z.key y.key y.left = zelse y.right = z

时耗：O(h)

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

基本思路

时耗 O(h)

功能

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

if u.p==NIL T.root = velseif u==u.p.left u.p.left = velse u.p.right = vif v~=NILv.p = u.p

随机构建二叉搜索树

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

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