第４章 树
对于大量数据链表访问太慢，而树支持以O(logN)平均时间支持各种操作。
树的概念：父亲、祖先、儿子、后裔、兄弟、根、路径、深度。
树节点写为泛型的嵌套类，多叉树用左孩子右兄弟表示法，二叉树左右孩子表示法。
private static classTreeNode{
AnyType element;
TreeNode leftChild;
TreeNode rightSibling;
}
private static classTreeNode{
AnyType element;
TreeNode leftChild;
TreeNode rightChild;
}
对于遍历，链表可以用索引号、增强for、迭代器。二叉树则使用递归。
先序遍历(preorder travesal)就是1判空、2输出、3归子。注意到改进后判空也是递归的。遍历的要点就是首先处理null情形。遍历的递归没有传递任何变量，减少出错。
public void printTree(){
if(isEmpty())
System.out.println("Emptytree");
else
printTree(root);
}
private voidprintTree(BinaryNode t){
if(t!=null){
System.out.println(t.element);
printTree(t.left);
printTree(t.right);
}
}
后序遍历计算树高的例子：
public intheight(BinaryNode t){
if(t!=null)
return -1;
else
return1+Math.max(height(t.left),height(t.right));
}
Linux中目录本身也是文件，需要占用空间。
列出文件系统目录（先序遍历、递归）的伪码（了解）：
private void listAll(intdepth){//ll命令被写为节点的类方法
printName(depth);
if(isDirectory()){
for each file c in thisdirectory(for each child)
c.listAll(depth+1);
}
}
public void listAll(){
listAll(0);
}
层序遍历中所有深度为d的节点要在深度d+1之前处理。使用非递归的队列实现，而不是递归默认的栈。
二叉树平均深度O(sqrtN)，二叉查找树平均深度O(logN)。
用二叉树作表达式转换方法：构造表达式树，其节点为操作符、树叶为操作数。中序遍历得中缀表达式，后序遍历得后缀表达式。如何由中缀表达式构造表达式树？？
至此已经学习了中缀表达式转为后缀表达式的”栈实现”和”二叉树实现”。
4.3二叉查找树
二叉查找树的写法：
[if !supportLists]l [endif]BST定义为最多２孩子，不允许重复元素
[if !supportLists]l [endif]数据只有根节点root，节点写为嵌套类。
[if !supportLists]l [endif]BinarySearchTree的API为： 判空置空、元素式添删容遍、最值查找。没有建树而用插入建树。
内部实现函数为：含树根形参和”根/节”返回的”元素式添删容遍、找最值”（用于递归）
(链表判长空置空、添删容迭、索引式增删改进。BST没有判长、没有迭代器、没有索引相关的方法。)(树更容易判空，不需要theSize)
public classBinarySearchTree> {
private BinaryNode root;
private static BinaryNode{
private AnyType element;
private BinaryNodeleft;
private BinaryNoderight;
public BinaryNode(AnyType e){
element=e;leftChild=null;rightChild=null;
}
public BinaryNode(AnyTypee,BinaryNode lt,BinaryNode rt){
element=e;leftChild=lt;rightChild=rt;
}
}
public BinarySearchTree(){root=null;}
public void makeEmpty(){root=null;}
public boolean isEmpty(){return root==null;}
public void insert(AnyType x){root=insert(x,root);}
public void remove(AnyType x){root=remove(x,root);}
public boolean contains(AnyType x){returncontains(root);}
public void printTree(){printTree(root);}
public AnyType findMin(){
if(isEmpty())
throw newUnderflowException();
return findMin(root).element;
}
public AnyType findMax(){
if(isEmpty())
throw newUnderflowException();
return findMax(root).element;
}
private BinarySearchNodeinsert(AnyType x,BinaryNode t){}
private BinarySearchNoderemove(AnyType x,BinaryNode t){}
private boolean contains(AnyTypex,BinaryNode t){}
private void printTree(BinaryNodet){}
private BinarySearchNodefindMin(BinaryNode t){}
private BinarySearchNodefindMax(BinaryNode t){}
}
返回值递归：二叉查找树的添删容的内部函数均使用了返回值递归。此处的返回值递归意味着更新树。
BST的内部函数实现：
[if !supportLists]l [endif]insert先递归查找，再处理递归底为空位插入和重复元素。
insert递归底并没有直接赋值给空位，而只是在空位处创建节点并返回，在上一个递归完成赋值。
[if !supportLists]l [endif]remove先递归查找再分情况处理：叶子直接删；单儿子补儿子；双儿子补右子树最小点，并递归删除替补。
二叉查找树的找最值即是外部方法，又协助完成remove操作。
补右子树最小点用改元素的方法而非改链。
删除替补为"返回值递归"。
[if !supportLists]l [endif]contains递归解决，找到与否均为递归底。
[if !supportLists]l [endif]printTree递归解决，先判空后遍历。
[if !supportLists]l [endif]findMin/findMax先判空再循还，而不要用尾递归解决。
（注意空树的退化情形，在递归中作为递归底其处理尤为重要）
二叉查找树的insert/remove/contains/printTree/findMin/findMax平均运行时间O(logN)，而非最坏除非树得到平衡。这也是二叉查找树需要：平衡附加条件，使任何节点深度不得过深的原因。
删除次数不多时，通常使用"惰性删除"（仅将待删除元素标记为已删除）。即便惰性删除的节点数与实际节点数相同，而树仅是上升很小的常数，不影响其insert/remove/contains性能，并且删除的效率和重新插入该节点的效率将大大提升。
private booleancontains(AnyType x,BinaryNode t){
if(t==null)
return false;
int compareResult=x.compareTo(t);//节约一次比较次数
if(compareResult<0)
return contains(x,t.left);
else if(compareResult>0)
return contains(x,t.right);
else
return true;
}
private AnyTypefindMin(BinaryNode t){
if(t==null)
return null;
else{
while(t.left!=null)
t=t.left;
return t.element;
}
}
private AnyTypefindMax(BinaryNode t){
if(t==null)
return null;
else{
while(t.right!=null)
t=t.right;
return t.element;
}
}
如果AnyType不是Comparable的，则需要使用比对象作比较。体现在成员、构造、比较器（有比较对象用比较对象，无比较器将参数强制转换为Comparable）、contains实现。
import java.util.Comparator;
public classBinarySearchTree{
private BinaryNode root;
private Comparator cmp;
public BinarySearchTree(){
this(null);
}
public BinarySearchTree(Comparator c){
root=null;cmp=c;
}
private int myCompare(AnyType lhs,AnyType rhs){
if(cmp!=null)
returncmp.compare(lhs,rhs);
else
return((Comparable)lhs).compareTo(rhs);
}
private boolean contains(AnyType x,BinaryNodet){
if(t==null)
returnfalse;//not found
int compareResult=cmp.compare(x,t);
if(compareResult<0)
returncontains(x, t.left);
else if(compareResult>0)
returncontains(x, t.right);
else
returntrue;//found
}
}
4.4 AVL平衡树
AVL树是左右子树的高度最多差１的二叉查找树（空树高度定义为-1）。插入／删除节点需要通过旋转恢复平衡，惰性删除不用维护平衡性。
[if !vml]
[endif]
AVL平衡树进化BST：节点记录树高、单双旋维护平衡、
[if !supportLists]l [endif]节点树高定义为其子树最大树高加１，因而节点树高可以递归求解。（区别：离根节点为深度，离叶节点为高度）
[if !supportLists]l [endif]单旋转为内逆子归重平，重平成逆子，自下而上地大子高加１地刷树高。实现为重平为形参逆点为返回的持左子／持右子两种情况。
双旋转为自下而上对两级作单旋转。
[if !supportLists]l [endif]insert的平衡维护：以insert的树根形参为参考。左右子树超过１开启维护，”一字型插入”用单旋转，”之字型插入”用双旋转。
4.5伸展树
伸展树的展开实现：父为根做单旋转，父祖俱在做双旋转。
展开操作不仅将被访问节点移到根处，而且将访问路径上大部分节点的深度大致减少一半。当访问路径过长导致过长查找时间时，树的伸展对未来操作有益。当访问消耗很少时，树伸展益处较少甚至有害。
伸展树查询contains将被访问节点旋转到树根上。
伸展树删除：访问被删除节点将其推到根处，访问左子树最大节点将其推到左子树根处，此时左子树没有右儿子可以挂载右子树成为其右儿子。
伸展树拥有：操作的O(logN)的摊还时间界、快速重访、无需保存更新树高的优点。伸展树的编程较AVL树简单。
4.7Ｂ树
M阶Ｂ树的有以下特性：B树就是非页节点作索引，叶节点存数据。
[if !supportLists]l [endif]叶节点存数据，叶节点深度相同存（L/2的下取整）至L个数据项
[if !supportLists]l [endif]非叶节点存关键字，M-1个关键字存2-M个叶节点中的最小关键字。
[if !supportLists]l [endif]树根儿子数2至M之间，或仅有一片树叶
[if !supportLists]l [endif]树根以外的非页节点的儿子数（M/2的下取整）至M之间
节点容量为块大小，块大小8K，为磁盘最小I/O单位。7200转磁盘的1转8.3毫秒，访问时间约为寻道时间+磁盘转动。B树将叶节点（叶节点和非叶节点）提高为块大小，提高访问效率。
M和L的取值：L=块大小/行数据大小。如块在小8192字节，行数据256字节，则L=32。每个非叶节点厚M-1个关键字和M个分支（地址）。如块大小8192字节，关键字大小32字节，分支大小4字节，则M=228。
B树先查找后插入：插入后L+1项则分裂树叶并在节点中添加查找关键字，父节点关键字个数超过M则递归解决。根节分裂为2个则建立新根，这就是根节点允许有2个儿子的原因。
另一种方法：交给数据项不超过L的邻节点领养，并修改父节点。
B树先查找后删除：删除后数据项低于最小值，从数据项没有达到最小值的邻节点领养。如果邻节点已达最小值则合并邻节点，并递归地修改父节点。
4.8标准库中的集合
Set接口不允许重复元素，Map接口关键字唯一而允许值重复。TreeSet、TreeMap是有序状态，是SortedSet、SortedMap的实现类。TreeSet、TreeMap支持以O(logN)时间支持add/remove/contains，实现方法为平衡二叉查找树中的红黑树。
词典的1字之差相似单词算法
词典的1字之差相似单词算法：
[if !supportLists]l [endif]读入List words。
[if !supportLists]l [endif]单词按长度分组Map>wordsByLength。
[if !supportLists]l [endif]遍历各组、遍历各位置，按缺字母词根分组。
[if !supportLists]l [endif]词根分组以单词对加入结果Map>adjWords。
[if !supportLists]l [endif]补写图链表update（图中取表、空表建表、表中加值）和图链表遍历方法。
低效的另一种方法：
[if !supportLists]l [endif]先写单词对相似检测函数：单词长度比较、逐个字母比较。
[if !supportLists]l [endif]单词分组，单循还地取出组内单词对进行相似验证。
代码参考教材。
