第一段
查找树支撑许多动态调集操作
search，minimum，maximum，predecessor，successor，插入，删去等
so用一颗查找树既可以当字典又可以作优先行列
第二段
二搜树上的根本操作用时与树高正比。
n nn个结点的彻底二叉树
这些操作的最坏运转时刻为Θ(lgn) Theta(lgn)Θ(lgn)
然鹅若此树是一条n nn个结点组成的线性链
那么相同操作就要Θ(n) Theta(n)Θ(n)最坏时
12.4中，将看到一颗随机结构的二叉查找树的希望高度是Θ(lgn) Theta(lgn)Θ(lgn)
so这样一棵树上的动态调集的根本操作的均匀运转时刻是Θ(lgn) Theta(lgn)Θ(lgn)
第三段
并不能总是确保随机地结构二叉查找树
但可以规划二叉查找树的变体
来确保根本操作具有好的最坏功能
13章介绍一个变形
红黑树
他的树高O(lgn) O(lgn)O(lgn)
18章介绍B树
特别适合于二级（磁盘）存储器上的数据库保护
第四段
在给出二叉查找树的根赋性指之后
随后几节介绍
遍历一颗二叉查找树来按序输出各个值
在二叉查找树上查找一个值
查找最小最大元素
查找一元素的前驱和后缀
对一颗二叉查找树刺进和删去
树的数学性质见附录B
12.1 什么是二叉查找树A8站源码交易平台
第1段
二搜树是以一棵二叉树来安排的
此树可用链表来表明
每节点便是一目标
除key和卫星数据外
还包括lef，tright和p
别离指左孩，右孩，双亲
如某个孩子结点和父节点不存在，为NIL
根节点是树中唯一父指针为NIL的结点
第2段
不同的二叉查找树可代表同一组值的调集（如下图）
（a）是包括6个结点、高度为2的二叉查找树
（b）包括相同关键字，高度为4的低效二叉查找树
大部分查找树操作的最坏运转时刻与树的高度成正比
二叉查找树中的关键字这样存储A8站源码交易平台
x xx是一个结点
若y yy是x xx左子树一结点，则y.key≤x.key y.keyle x.keyy.key≤x.key
若y yy是x xx右子树一结点，则y.key≥x.key y.keyge x.keyy.key≥x.key
如图12-1(a)，根为6，左子树有2，5，5均≤6 le 6≤6
右子树关键字7,8，均≥6 ge 6≥6
此性指对每个结点都建立
例如关于树根的左孩子。
第3段
二搜树的性指是咱们经过一个简略的递归算法来按序输出二叉查找树中的一切关键字，
称为中序遍历
命名原因是输出的子树根的关键字
坐落其左子树的关键字值和右子树的关键字值之间
那么先序后序呢？
调用INORDER-TREE_WALK(T.root)，就可以输出一颗二搜树T TT
的一切元素。
INORDER-TREE-WALK(x)
if x！=NIL
INORDER-TREE-WALK(x.left)
print x.key
INORDER-TREE-WALK(x.right)
上图中的两棵二搜树，中序遍历关键字为2,5,5,6,7,8.
第4段
遍历有n nn个结点的二搜树需求消耗Θ(n)时刻 Theta(n)时刻Θ(n)时刻
由于初度调用后，关于树中的每个结点
这个进程恰好要自己调用2次
一次是他的左孩子
另一次是他的右孩子
下面定理给了履行一次中序遍历消耗线性时刻的一证明
定理12.1
12.2 查询二叉查找树
第一段
常常需求查找一个存储在二叉查找树中的关键字
给个关键字，查找整个数据？？
除search之外
二叉查找树还能支撑例如
minimum，maximum，successor和predecessor
本节评论这些操作，并阐明
在高度为h hh的二搜树上，如安在O(h) O(h)O(h)内执完每操作
查找
第1段
用下面进程在一个二搜树上查找一个具有给定关键字的结点
输入一个指向树根的指针和关键字k kk
假如结点存在，回来指针
不然NIL
TREE-SEARCH(x,k)
if(x.key==k || x==NIL)
return x;
if(k<x.key)
return TREE-SEARCH(x.left,k)
else return TREE-SEARCH(x.right,k)
第2段
这段太简略了
图12-2
为了找13的结点。
从树根开端沿着15-6-7-13查找。
15的后继是17
13没右子树，它的后继是最低的先人且左孩子也是一个先人
15是他的后继。
第3段
可用while循环展开递归
用迭代方法重写这个进程
对大多数计算机，迭代版别效率高得多
ITERATIVE-TREE-SEARCH(x,k)
while(x!=NIL and k!=x.key)
if(k<x.key)
x=x.left
else x=x.right
return x
最大关键字元素和最小关键字元素
从树根开端沿着left孩子指针直到遇到NIL
总可在二搜树中找到一个元素
如图12-2.
下面的进程回来以x xx为根的子树中最小元素的指针
这儿假定x不为NIL
TREE-MINIMUM(x)
while x.left!=NIL
x=x.left
return x
后继和前驱
给定二搜树中一结点，需按中序遍历的次第查找他的后继。
假如一切的关键字互不相同，则后继是大于x.key x.{key}x.key的最小关键字的结点。
二搜树可经过没有任何关键字的比较来定一结点的后继。
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
伪代码分俩状况
右子树非空，easy
有子树空，为找到y yy，只需从x xx向上直到遇到这样一个结点：
这个结点是它父亲的左孩子。
12.3 插入和删除 A8站源码交易平台
插和删会引起由二搜树表明的动态调集的改变A8站源码交易平台
一定要修正数据结构来反映这个改变
但修正要坚持二搜树性质建立
下面将看到
刺进新结点简略些
删去有些杂乱
插入
12.4 随机构建二搜树
