第４章 樹(shù)
對(duì)于大量數(shù)據(jù)鏈表訪(fǎng)問(wèn)太慢，而樹(shù)支持以O(shè)(logN)平均時(shí)間支持各種操作。
樹(shù)的概念：父親、祖先、兒子、后裔、兄弟、根、路徑、深度。
樹(shù)節(jié)點(diǎn)寫(xiě)為泛型的嵌套類(lèi)，多叉樹(shù)用左孩子右兄弟表示法，二叉樹(shù)左右孩子表示法。
private static classTreeNode{
????????????????? AnyType element;
????????????????? TreeNode leftChild;
????????????????? TreeNode rightSibling;
}
private static classTreeNode{
????????????????? AnyType element;
????????????????? TreeNode leftChild;
????????????????? TreeNode rightChild;
}
對(duì)于遍歷，鏈表可以用索引號(hào)、增強(qiáng)for、迭代器。二叉樹(shù)則使用遞歸。
先序遍歷(preorder travesal)就是1判空、2輸出、3歸子。注意到改進(jìn)后判空也是遞歸的。遍歷的要點(diǎn)就是首先處理null情形。遍歷的遞歸沒(méi)有傳遞任何變量，減少出錯(cuò)。
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);
????????????????? }????????????????
}
后序遍歷計(jì)算樹(shù)高的例子：
public intheight(BinaryNode t){
????????????????? if(t!=null)
??????????????????????????????????? return -1;
????????????????? else
??????????????????????????????????? return1+Math.max(height(t.left),height(t.right));
}
Linux中目錄本身也是文件，需要占用空間。
列出文件系統(tǒng)目錄（先序遍歷、遞歸）的偽碼（了解）：
private void listAll(intdepth){//ll命令被寫(xiě)為節(jié)點(diǎn)的類(lèi)方法
????????????????? printName(depth);
????????????????? if(isDirectory()){
??????????????????????????????????? for each file c in thisdirectory(for each child)
????????????????????????????????????????????????????? c.listAll(depth+1);
????????????????? }
}
public void listAll(){
????????????????? listAll(0);
}
層序遍歷中所有深度為d的節(jié)點(diǎn)要在深度d+1之前處理。使用非遞歸的隊(duì)列實(shí)現(xiàn)，而不是遞歸默認(rèn)的棧。
二叉樹(shù)平均深度O(sqrtN)，二叉查找樹(shù)平均深度O(logN)。
用二叉樹(shù)作表達(dá)式轉(zhuǎn)換方法：構(gòu)造表達(dá)式樹(shù)，其節(jié)點(diǎn)為操作符、樹(shù)葉為操作數(shù)。中序遍歷得中綴表達(dá)式，后序遍歷得后綴表達(dá)式。如何由中綴表達(dá)式構(gòu)造表達(dá)式樹(shù)？？
至此已經(jīng)學(xué)習(xí)了中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式的”棧實(shí)現(xiàn)”和”二叉樹(shù)實(shí)現(xiàn)”。
4.3二叉查找樹(shù)
二叉查找樹(shù)的寫(xiě)法：
[if !supportLists]l?[endif]BST定義為最多２孩子，不允許重復(fù)元素
[if !supportLists]l?[endif]數(shù)據(jù)只有根節(jié)點(diǎn)root，節(jié)點(diǎn)寫(xiě)為嵌套類(lèi)。
[if !supportLists]l?[endif]BinarySearchTree的API為： 判空置空、元素式添刪容遍、最值查找。沒(méi)有建樹(shù)而用插入建樹(shù)。
內(nèi)部實(shí)現(xiàn)函數(shù)為：含樹(shù)根形參和”根/節(jié)”返回的”元素式添刪容遍、找最值”（用于遞歸）
(鏈表判長(zhǎng)空置空、添刪容迭、索引式增刪改進(jìn)。BST沒(méi)有判長(zhǎng)、沒(méi)有迭代器、沒(méi)有索引相關(guān)的方法。)(樹(shù)更容易判空，不需要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){}
}
返回值遞歸：二叉查找樹(shù)的添刪容的內(nèi)部函數(shù)均使用了返回值遞歸。此處的返回值遞歸意味著更新樹(shù)。
BST的內(nèi)部函數(shù)實(shí)現(xiàn)：
[if !supportLists]l?[endif]insert先遞歸查找，再處理遞歸底為空位插入和重復(fù)元素。
insert遞歸底并沒(méi)有直接賦值給空位，而只是在空位處創(chuàng)建節(jié)點(diǎn)并返回，在上一個(gè)遞歸完成賦值。
[if !supportLists]l?[endif]remove先遞歸查找再分情況處理：葉子直接刪；單兒子補(bǔ)兒子；雙兒子補(bǔ)右子樹(shù)最小點(diǎn)，并遞歸刪除替補(bǔ)。
二叉查找樹(shù)的找最值即是外部方法，又協(xié)助完成remove操作。
補(bǔ)右子樹(shù)最小點(diǎn)用改元素的方法而非改鏈。
刪除替補(bǔ)為"返回值遞歸"。
[if !supportLists]l?[endif]contains遞歸解決，找到與否均為遞歸底。
[if !supportLists]l?[endif]printTree遞歸解決，先判空后遍歷。
[if !supportLists]l?[endif]findMin/findMax先判空再循還，而不要用尾遞歸解決。
（注意空樹(shù)的退化情形，在遞歸中作為遞歸底其處理尤為重要）
二叉查找樹(shù)的insert/remove/contains/printTree/findMin/findMax平均運(yùn)行時(shí)間O(logN)，而非最壞除非樹(shù)得到平衡。這也是二叉查找樹(shù)需要：平衡附加條件，使任何節(jié)點(diǎn)深度不得過(guò)深的原因。
刪除次數(shù)不多時(shí)，通常使用"惰性刪除"（僅將待刪除元素標(biāo)記為已刪除）。即便惰性刪除的節(jié)點(diǎn)數(shù)與實(shí)際節(jié)點(diǎn)數(shù)相同，而樹(shù)僅是上升很小的常數(shù)，不影響其insert/remove/contains性能，并且刪除的效率和重新插入該節(jié)點(diǎn)的效率將大大提升。
private booleancontains(AnyType x,BinaryNode t){
????????????????? if(t==null)
??????????????????????????????????? return false;
????????????????? int compareResult=x.compareTo(t);//節(jié)約一次比較次數(shù)
????????????????? 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的，則需要使用比對(duì)象作比較。體現(xiàn)在成員、構(gòu)造、比較器（有比較對(duì)象用比較對(duì)象，無(wú)比較器將參數(shù)強(qiáng)制轉(zhuǎn)換為Comparable）、contains實(shí)現(xiàn)。
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平衡樹(shù)
AVL樹(shù)是左右子樹(shù)的高度最多差１的二叉查找樹(shù)（空樹(shù)高度定義為-1）。插入／刪除節(jié)點(diǎn)需要通過(guò)旋轉(zhuǎn)恢復(fù)平衡，惰性刪除不用維護(hù)平衡性。
[if !vml]
[endif]
AVL平衡樹(shù)進(jìn)化BST：節(jié)點(diǎn)記錄樹(shù)高、單雙旋維護(hù)平衡、
[if !supportLists]l?[endif]節(jié)點(diǎn)樹(shù)高定義為其子樹(shù)最大樹(shù)高加１，因而節(jié)點(diǎn)樹(shù)高可以遞歸求解。（區(qū)別：離根節(jié)點(diǎn)為深度，離葉節(jié)點(diǎn)為高度）
[if !supportLists]l?[endif]單旋轉(zhuǎn)為內(nèi)逆子歸重平，重平成逆子，自下而上地大子高加１地刷樹(shù)高。實(shí)現(xiàn)為重平為形參逆點(diǎn)為返回的持左子／持右子兩種情況。
雙旋轉(zhuǎn)為自下而上對(duì)兩級(jí)作單旋轉(zhuǎn)。
[if !supportLists]l?[endif]insert的平衡維護(hù)：以insert的樹(shù)根形參為參考。左右子樹(shù)超過(guò)１開(kāi)啟維護(hù)，”一字型插入”用單旋轉(zhuǎn)，”之字型插入”用雙旋轉(zhuǎn)。
4.5伸展樹(shù)
伸展樹(shù)的展開(kāi)實(shí)現(xiàn)：父為根做單旋轉(zhuǎn)，父祖俱在做雙旋轉(zhuǎn)。
展開(kāi)操作不僅將被訪(fǎng)問(wèn)節(jié)點(diǎn)移到根處，而且將訪(fǎng)問(wèn)路徑上大部分節(jié)點(diǎn)的深度大致減少一半。當(dāng)訪(fǎng)問(wèn)路徑過(guò)長(zhǎng)導(dǎo)致過(guò)長(zhǎng)查找時(shí)間時(shí)，樹(shù)的伸展對(duì)未來(lái)操作有益。當(dāng)訪(fǎng)問(wèn)消耗很少時(shí)，樹(shù)伸展益處較少甚至有害。
伸展樹(shù)查詢(xún)contains將被訪(fǎng)問(wèn)節(jié)點(diǎn)旋轉(zhuǎn)到樹(shù)根上。
伸展樹(shù)刪除：訪(fǎng)問(wèn)被刪除節(jié)點(diǎn)將其推到根處，訪(fǎng)問(wèn)左子樹(shù)最大節(jié)點(diǎn)將其推到左子樹(shù)根處，此時(shí)左子樹(shù)沒(méi)有右兒子可以?huà)燧d右子樹(shù)成為其右兒子。
伸展樹(shù)擁有：操作的O(logN)的攤還時(shí)間界、快速重訪(fǎng)、無(wú)需保存更新樹(shù)高的優(yōu)點(diǎn)。伸展樹(shù)的編程較AVL樹(shù)簡(jiǎn)單。
4.7Ｂ樹(shù)
M階Ｂ樹(shù)的有以下特性：B樹(shù)就是非頁(yè)節(jié)點(diǎn)作索引，葉節(jié)點(diǎn)存數(shù)據(jù)。
[if !supportLists]l?[endif]葉節(jié)點(diǎn)存數(shù)據(jù)，葉節(jié)點(diǎn)深度相同存（L/2的下取整）至L個(gè)數(shù)據(jù)項(xiàng)
[if !supportLists]l?[endif]非葉節(jié)點(diǎn)存關(guān)鍵字，M-1個(gè)關(guān)鍵字存2-M個(gè)葉節(jié)點(diǎn)中的最小關(guān)鍵字。
[if !supportLists]l?[endif]樹(shù)根兒子數(shù)2至M之間，或僅有一片樹(shù)葉
[if !supportLists]l?[endif]樹(shù)根以外的非頁(yè)節(jié)點(diǎn)的兒子數(shù)（M/2的下取整）至M之間
節(jié)點(diǎn)容量為塊大小，塊大小8K，為磁盤(pán)最小I/O單位。7200轉(zhuǎn)磁盤(pán)的1轉(zhuǎn)8.3毫秒，訪(fǎng)問(wèn)時(shí)間約為尋道時(shí)間+磁盤(pán)轉(zhuǎn)動(dòng)。B樹(shù)將葉節(jié)點(diǎn)（葉節(jié)點(diǎn)和非葉節(jié)點(diǎn)）提高為塊大小，提高訪(fǎng)問(wèn)效率。
M和L的取值：L=塊大小/行數(shù)據(jù)大小。如塊在小8192字節(jié)，行數(shù)據(jù)256字節(jié)，則L=32。每個(gè)非葉節(jié)點(diǎn)厚M-1個(gè)關(guān)鍵字和M個(gè)分支（地址）。如塊大小8192字節(jié)，關(guān)鍵字大小32字節(jié)，分支大小4字節(jié)，則M=228。
B樹(shù)先查找后插入：插入后L+1項(xiàng)則分裂樹(shù)葉并在節(jié)點(diǎn)中添加查找關(guān)鍵字，父節(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)超過(guò)M則遞歸解決。根節(jié)分裂為2個(gè)則建立新根，這就是根節(jié)點(diǎn)允許有2個(gè)兒子的原因。
另一種方法：交給數(shù)據(jù)項(xiàng)不超過(guò)L的鄰節(jié)點(diǎn)領(lǐng)養(yǎng)，并修改父節(jié)點(diǎn)。
B樹(shù)先查找后刪除：刪除后數(shù)據(jù)項(xiàng)低于最小值，從數(shù)據(jù)項(xiàng)沒(méi)有達(dá)到最小值的鄰節(jié)點(diǎn)領(lǐng)養(yǎng)。如果鄰節(jié)點(diǎn)已達(dá)最小值則合并鄰節(jié)點(diǎn)，并遞歸地修改父節(jié)點(diǎn)。
4.8標(biāo)準(zhǔn)庫(kù)中的集合
Set接口不允許重復(fù)元素，Map接口關(guān)鍵字唯一而允許值重復(fù)。TreeSet、TreeMap是有序狀態(tài)，是SortedSet、SortedMap的實(shí)現(xiàn)類(lèi)。TreeSet、TreeMap支持以O(shè)(logN)時(shí)間支持add/remove/contains，實(shí)現(xiàn)方法為平衡二叉查找樹(shù)中的紅黑樹(shù)。
詞典的1字之差相似單詞算法
詞典的1字之差相似單詞算法：
[if !supportLists]l?[endif]讀入List words。
[if !supportLists]l?[endif]單詞按長(zhǎng)度分組Map>wordsByLength。
[if !supportLists]l?[endif]遍歷各組、遍歷各位置，按缺字母詞根分組。
[if !supportLists]l?[endif]詞根分組以單詞對(duì)加入結(jié)果Map>adjWords。
[if !supportLists]l?[endif]補(bǔ)寫(xiě)圖鏈表update（圖中取表、空表建表、表中加值）和圖鏈表遍歷方法。
低效的另一種方法：
[if !supportLists]l?[endif]先寫(xiě)單詞對(duì)相似檢測(cè)函數(shù)：?jiǎn)卧~長(zhǎng)度比較、逐個(gè)字母比較。
[if !supportLists]l?[endif]單詞分組，單循還地取出組內(nèi)單詞對(duì)進(jìn)行相似驗(yàn)證。
代碼參考教材。
