????本篇文章介紹一些算法里用到的基本概念背蟆。
(1)遞歸
????一個微妙的遞歸算法，代碼如下：
public static int bad(int n) {
if (n == 0)
return 0;
else
return bad(n / 3 + 1) + n - 1;
}
????初一看基矮，好像沒什么問題淆储。但如果n=1冠场，那么會出現bad(1) = bad(1)家浇。而bad(1)的值究竟是多少，不知道碴裙。
????這里就需要了解遞歸的兩個基本法則：
????????1）基準情形(base case)钢悲，必須總有某些基準的情形点额，它們不用遞歸就能求解；
????????2）不斷推進莺琳，遞歸調用必須總能夠朝著一個基準情形推進还棱。
????上面的代碼違反了第2)條，遞歸調用最終并沒有推進到基準情形惭等。推進到bad(1)就陷入死循環(huán)了珍手。
(2)散列
- 散列(hashing)是一種用于以常數平均時間插入、刪除和查找的技術辞做。需要排序信息的操作則不支持琳要，如findMax、findMin等秤茅。散列是散列表的一種實現稚补；
- 散列函數：將關鍵字映射到0到size-1這個范圍中的函數，稱為散列函數框喳；一個簡單示例：key % size 课幕；另外一個示例，Java版本：
public static int hash(String key , int size){
int hash = 0;
for (int i =0 ; i < key.length() ; i++){
hash += key.charAt(i);
}
return hash % size;
}
????Kotlin版本：
fun hash(key: String, size: Int): Int {
var hash = 0
for (i in 0 until key.length) {
hash += key[i].code
}
return hash % size
}
- 散列沖突：兩個關鍵字散列到同一個值五垮；
- 分離鏈接法：將沖突的元素保留到一個鏈表中乍惊，如Java中的HashMap、HashSet實現方式拼余；
(3)中綴表達式轉后綴表達式
????中綴表達式就是我們常見的算術表達式污桦，如 a + b * c + (d * e + f) * g。后綴表達式是一種將操作數放在前匙监，操作符放在后面的表達式凡橱，它不使用圓括號。最簡單后綴表達式如“ab+”亭姥，它對應的中綴表達式是"a+b"稼钩。中綴表達式對于人來說非常容易理解，但對于計算機來說太復雜 达罗。而后綴表達式則相反坝撑。
???? a + b * c + (d * e + f) * g 轉換為后綴表達式的結果是：abc * + de * f + q * +。
????這個轉換需要用到Stack數據結構粮揉。對中綴表達式的每個字符巡李，如果是操作數，則放到輸出中扶认；如果是操作符侨拦，則根據棧頂情況處理。
????????1）如果棧頂的操作符優(yōu)先級高辐宾，那么將它立即出棧狱从；如果兩者優(yōu)先級一樣膨蛮，也立即出棧；如果棧頂操作符優(yōu)先級低季研，則入棧敞葛。
????????2）對于圓括號 "(" 和 ")"，左括號直接入棧与涡；只有遇到右括號惹谐，才移走左括號。
????后綴表達式的求值：也使用一個棧驼卖，不過處理的不是操作符豺鼻，而是操作數。對每個字符款慨，如果是操作數，就入棧桩了；如果是操作符埠戳，則從棧頂彈出2個操作數并進行計算，計算結果入棧颗圣。如此循環(huán)屁使，直到處理完表達式中的所有字符在岂。最后，棧中只剩下一個元素蛮寂，就是表達式的求值結果蔽午。
(4)樹的一些基本概念
- 樹是一種非線性結構；
- 樹是一些節(jié)點的集合酬蹋。這個集合可以是空集及老，如果不是空集，則由根節(jié)點和子樹組成范抓；
- 一棵樹是N個節(jié)點和N-1條邊的集合骄恶。除了根節(jié)點外，每個節(jié)點都有一個父親匕垫；
- 只有根節(jié)點沒有直接前驅僧鲁，其他節(jié)點有且僅有一個直接前驅；
- 每個節(jié)點可以有任意多個直接后繼；
- 兄弟節(jié)點：具有同一個父節(jié)點的節(jié)點悔捶；
- 節(jié)點的度：一個節(jié)點所包含子樹的數量；
- 樹的度：該樹所有節(jié)點中最大的度单芜；
- 節(jié)點的層數：根節(jié)點的層數是1蜕该，依次向下。樹是一種層次結構洲鸠，每個節(jié)點都處在一定的層次上堂淡。
- 樹的深度：樹中節(jié)點的最大層數稱為樹的深度
- 樹的表示法：層次括號法，如( A )表示只有一個根節(jié)點A扒腕；( A( B , C ) )表示3個節(jié)點組成的樹绢淀，A是根節(jié)點，B瘾腰、C是A的直接后繼節(jié)點；以此類推；
- 有序樹：樹中各節(jié)點的子樹是按一定次序從左向右安排的看铆；
- 無序樹：與有序樹相反；
- 森林：多棵互不相交的樹的集合竞慢；
- 先序遍歷：先處理節(jié)點，再處理孩子寺谤；
- 后序遍歷：先處理孩子变屁，再處理節(jié)點；
- 二叉樹：每個節(jié)點闷板，子節(jié)點數不超過2遮晚；
- 中序遍歷：先處理左孩子糜颠，再處理節(jié)點其兴，最后處理右孩子元旬。針對二叉樹而言。
????二叉樹的一般結構：
class BinaryNode {
Object element;
BinaryNode left;
BinaryNode right;
}
- 表達式樹：樹葉是操作數朋譬，其他是操作符徙赢。從后綴表達式可以構造一個表達式樹；
- 二叉查找樹：對于每個節(jié)點X枕屉，它的左子樹中所有項的值都小于X中的項搀擂，右子樹則相反哨颂；它的平均深度是O(log N);
- AVL樹：帶有平衡條件的二叉查找樹威恼，每個節(jié)點的左子樹和右子樹的高度最多相差1腹备；除去插入操作外(惰性刪除)植酥，所有的樹操作都是O(log N)哎媚。插入操作可能會破壞AVL樹的特性稻据，這種特性需要“旋轉”操作來維持捻悯。插入一個新節(jié)點后今缚，如果節(jié)點A的AVL性質被破壞了，那么新節(jié)點的位置存在下列幾種情況：
- A的左兒子的左子樹何荚；
- A的左兒子的右子樹餐塘；
- A的右兒子的左子樹；
- A的右兒子的右子樹稠鼻；
????這可以歸為兩種情況候齿，一種是插入發(fā)生在“外邊”的情況周霉，即左-左俱箱、右-右，另外一種是插入發(fā)生在“內部”的情況禁漓，即左-右伶跷、右-左叭莫。第一種情況需要“單旋轉”來進行調整；第二種情況需要“雙旋轉”進行調整抵皱。
????Java實現如下：
public class AVLTree {
//節(jié)點
class Node {
int data;
Node leftChild;
Node rightChild;
int height;
public Node(int data) {
this(data, null, null);
}
public Node(int data, Node leftChild, Node rightChild) {
this.data = data;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
}
int height(Node node) {
return node == null ? -1 : node.height;
}
/**
* 更新節(jié)點node的高度
*
* @param node
*/
void updateHeight(Node node) {
int leftHeight = height(node.leftChild);
int rightHeight = height(node.rightChild);
node.height = Math.max(leftHeight, rightHeight) + 1;
}
/**
* 節(jié)點左、右子樹的高度差
* 如果返回值為正伤为，說明右子樹較高
*
* @param node
* @return
*/
int balanceFactor(Node node) {
return height(node.rightChild) - height(node.leftChild);
}
//右旋
Node rotateRight(Node node) {
Node left = node.leftChild;
node.leftChild = left.rightChild;
left.rightChild = node;
updateHeight(left);
updateHeight(node);
return left;
}
//左旋
Node rotateLeft(Node node) {
Node right = node.rightChild;
node.rightChild = right.leftChild;
right.leftChild = node;
updateHeight(right);
updateHeight(node);
return right;
}
//使節(jié)點node保持AVL樹特性
Node reBalance(Node node) {
//如果為正，說明右子樹高位衩；如果為副僚祷，說明左子樹高辙谜。絕對值如果大于1，說明AVL特性被破壞
int balanceFactor = balanceFactor(node);
if (balanceFactor < -1) {//左子樹高蜕琴，特性被破壞
if (balanceFactor(node.leftChild) < 0) { //左-左情況，右旋
node = rotateRight(node);
} else { //左-右情況号醉，先左旋，再右旋
node.leftChild = rotateLeft(node.rightChild);
node = rotateRight(node);
}
}
if (balanceFactor > 1) {//右子樹高
if (balanceFactor(node.rightChild) > 0) {//右-右情況润绵，左旋
node = rotateLeft(node);
} else {//右-左情況，先右旋卿捎，再左旋
node.rightChild = rotateRight(node);
node = rotateLeft(node);
}
}
return node;
}
//插入一個新節(jié)點
Node insertNode(int data, Node node) {
if (node == null) {
return new Node(data);
}
if (data < node.data) {
node.leftChild = insertNode(data, node.leftChild);
} else if (data > node.data) {
node.rightChild = insertNode(data, node.rightChild);
} else { //重復了
return node;
}
updateHeight(node);
return reBalance(node);
}
//刪除節(jié)點
Node deleteNode(int data, Node node) {
if (node == null) return null;
if (data < node.data) {
node.leftChild = deleteNode(data, node.leftChild);
} else if (data > node.data) {
node.rightChild = deleteNode(data, node.rightChild);
} else if (node.leftChild == null && node.rightChild == null) {
return null;
} else if (node.leftChild == null) {//節(jié)點只有右孩子
node = node.rightChild;
} else if (node.rightChild == null) { //節(jié)點只有左孩子
node = node.leftChild;
} else { //節(jié)點左右孩子都有
//找到右子樹的最小節(jié)點
Node minNode = node.rightChild;
while (minNode.leftChild != null) {
minNode = minNode.leftChild;
}
//將最小點的值保存到node
node.data = minNode.data;
node.rightChild = deleteNode(minNode.data,node.rightChild); //刪除右子樹的最小點底桂，因為它已經移到node了
}
updateHeight(node);
return reBalance(node);
}
}
層序遍歷：所有深度為d的節(jié)點，要在深度為d+1的節(jié)點之前處理暮顺。
滿二叉樹：除了葉子節(jié)點外拖云，其他節(jié)點都有2個子節(jié)點乏苦；
完全二叉樹：除最后一層外汇荐，其他各層的節(jié)點數都是2，且最后一層葉節(jié)點按照從左至右的順序連續(xù)存在油昂，只缺最后一層右側若干節(jié)點革娄；
B樹：當數據結構非常大，內存裝不下時冕碟，就需要用到B樹拦惋。它用來平衡cpu計算速度和磁盤訪問速度不匹配的問題。
M叉查找樹：有M路分支的查找樹安寺，一顆完全M叉查找樹的高度大約是log
N 厕妖。
攤還時間：當M次操作的序列總的最壞情形運行時間為O(M f(N))時，我們就說它的攤還運行時間為O(f(N))。
伸展樹：從空樹開始凳枝，連續(xù)M次對樹的操作最多花費O(M logN)時間的一種二叉樹锭环。伸展樹的攤還時間是O(log N)蛾茉。它的基本想法如下：
????當一個節(jié)點被訪問后，它就要經過一系列AVL樹的旋轉被推到根上赔桌；如果一個節(jié)點很深纽竣，那么在其路徑上就存在許多相對較深的節(jié)點幽勒，通過重新構造可以減少對這些節(jié)點的進一步訪問時間。伸展樹在節(jié)點過深時朵纷，具有平衡這棵樹(某種程度上)的作用落午。在實際的許多應用中，當一個節(jié)點被訪問時瓷翻，它很可能不久再被訪問敢朱。使用伸展樹結構，可以減少查找時間洛巢。
????此外，伸展樹不要求保留高度或平衡信息茂装。根節(jié)點屋摇、左孩子和右孩子也沒有大小關系重斑，它不是查找樹坦冠。
(5)圖的一些基本概念
- 每個數據元素之間佛玄，可以任意關聯哼蛆，構成了一個圖結構旅东；
- 圖結構包括兩個部分：頂點Vertext和邊Edge，所有的頂點構成一個頂點集合陡舅，記為V(G)蜈出；所有的邊構成一個邊集合，記為E(G)涛酗；
- 在數學上铡原，圖結構記為：G = (V , E) 或者 G = ( V(G) , V(E) ) ; V(G)必須是非空，V(E)可以為空商叹；
- V(G)示例：V(G) = { V1 , V2 , V3 , V4} ;
- E(G)示例：E(G) = { (V1, V2) , (V1 , V3) , (V2, V4) ,(V1 , V4)} ;
- 在一個圖中燕刻，所有的邊都沒有方向性，則它是無向圖剖笙；無向圖中對頂點順序沒有要求卵洗，(V1 , V2) 和 (V2 , V1)是一樣的；
- 在一個圖中弥咪，邊是有方向性的过蹂，則它是有向圖；頂點順序表示指向酪夷；用尖括號表示：<V1 , V2> ;
- 頂點的度：連接頂點的邊的數量稱為度榴啸；對于無向圖，即為連接頂點的邊的數量晚岭，記為D(V)；對于有向圖勋功，則分為入度ID(V)和出度OD(V)坦报；有向圖中頂點的度是入度+出度库说，D(V) = ID(V) + OD(V)；
- 鄰接頂點：一條邊的兩個頂點片择；有向圖中根據邊的方向潜的，分為起始頂點和結束頂點，也分別稱為入邊鄰接點和出邊鄰接點字管；
- 無向完全圖：如果一個無向圖中啰挪，每兩個頂點之間都存在一條邊，那么它是無向完全圖嘲叔；
- 有向完全圖：如果一個有向圖中亡呵，每兩個頂點之間都存在方向相反的兩條邊，那么它是有向完全圖硫戈；包含N個頂點的有向完全圖锰什，邊數是N(N-1);
- 子圖：類似于子集合，子圖的頂點和邊都應該是父圖的頂點和邊的子集丁逝；
- 路徑：路徑是圖結構中兩個頂點之間的連線汁胆；路徑上邊的數量稱為路徑長度；兩個頂點之間的路徑可能有多條霜幼，路徑長度可能不一樣嫩码；
- 簡單路徑：如果一條路徑上頂點不重復出現，則稱為簡單路徑罪既；
- 環(huán)：如果一條路徑的第一個頂點和最后一個頂點相同谢谦，則稱之為環(huán)，也稱為回路萝衩；
- 簡單回路：如果第一個頂點和最后一個頂點相同回挽，其余各點都不重復的回路稱為簡單回路；
- 連通：如果圖結構中猩谊，兩個頂點之間有路徑千劈，則稱為這兩個頂點是連通的；這兩個頂點可以不鄰接牌捷；
- 連通圖：如果無向圖中墙牌，任意兩個頂點都是連通的，那么這個圖便稱為連通圖暗甥；
- 連通分量：無向圖的極大連通子圖喜滨；對于一個連通圖，其連通分量有且只有一個撤防，就是它自身虽风；非連通圖，有多個連通分量；
- 強連通圖：如果有向圖中辜膝，任意兩個頂點都是連通的无牵，則稱該圖為強連通圖；注意有向圖中邊具有方向性厂抖；
- 強連通分量：有向圖的極大連通子圖稱為該圖的強連通分量茎毁；強連通圖只有一個強連通分量，就是它自身忱辅；
- 權：將邊表示為某種數值七蜘，這個數值就是權；無向圖中加入權墙懂，稱為無向帶圖權橡卤；有向圖中加入權，稱為有向帶圖權垒在；在交通圖中蒜魄，權可以代表路徑長度；
- 網：邊上帶權值的圖的另一種名稱场躯；
- 鄰接矩陣：保存頂點之間關系的數組谈为；示例如下：
char vertex = new char[N] ;// 保存頂點信息
int[][] edgeWeight = new int[N][N];// 保存邊的權或者連接關系
- 根據兩個頂點的編號，從鄰接矩陣中獲取值踢关，如果為0表示這兩個頂點之間沒有邊伞鲫；如果為1，則表示有邊签舞；如果大于1秕脓，表示權；
- 對于無向圖儒搭，鄰接矩陣左下角和右上角是對稱的吠架；
- 圖結構，Java語言描述：
public class Graph {
static final int NUM = 20; //圖的頂點數
char[] vertex = new char[NUM]; //頂點集合
int gType; //圖類型搂鲫，0表示無向圖傍药；1表示有向圖
int vertexNum;//頂點數量
int[][] edgeWeight = new int[NUM][NUM] ; //鄰接矩陣
int[] isTrav = new int[NUM];
}
????Kotlin版本：
class Graph {
var vertex = CharArray(NUM) //頂點集合
var gType //圖類型，0表示無向圖魂仍；1表示有向圖
= 0
var vertexNum //頂點數量
= 0
var edgeWeight = Array(NUM) { IntArray(NUM) } //鄰接矩陣
var isTrav = IntArray(NUM)
companion object {
const val NUM = 20 //圖的頂點數
}
}
- 圖的遍歷拐辽，深度優(yōu)先算法，Java版本：
void deepTraOne(Graph g,int n){ //從第n個頂點開始
int i;
g.isTrav[n] = 1; //標記該頂點已經訪問過
System.out.println(g.vertex[n]); //輸出節(jié)點數據
for (i = 0;i<g.vertexNum;i++){
if (g.edgeWeight[n][i] != 0 && g.isTrav[i] == 0){
deepTraOne(g,i);
}
}
}
//深度優(yōu)先遍歷
void deepTraGraph(Graph g){
int i;
for (i =0;i<g.vertexNum;i++){
if (g.isTrav[i] == 0){
deepTraOne(g,i);
}
}
}
????Kotlin版本：
fun deepTraOne(g: Graph, n: Int) { //從第n個頂點開始
var i: Int
g.isTrav[n] = 1 //標記該頂點已經訪問過
println(g.vertex[n]) //輸出節(jié)點數據
i = 0
while (i < g.vertexNum) {
if (g.edgeWeight[n][i] != 0 && g.isTrav[i] == 0) {
deepTraOne(g, i)
}
i++
}
}
//深度優(yōu)先遍歷
fun deepTraGraph(g: Graph) {
var i: Int
i = 0
while (i < g.vertexNum) {
if (g.isTrav[i] == 0) {
deepTraOne(g, i)
}
i++
}
}
- 生成樹：滿足這3個條件的的樹稱為原圖的一顆生成樹擦酌，1)子圖的頂點與原圖相同俱诸；2）子圖的邊是原圖的子集，且這部分邊剛好將圖中所有頂點連通赊舶；3）子圖中的邊不構成回路睁搭；
- 對于有n個頂點的連通圖赶诊，其生成樹有且只有n-1條邊。如果邊數少于此數介袜，就不可能將所有頂點連通甫何；如果多于此數出吹，則必須產生回路遇伞；
- 最小生成樹：一個圖的生成樹可能有多個，其中權值最小的生成樹就稱為圖的最小生成樹捶牢；
(6)堆
- 優(yōu)先隊列：某些作業(yè)應該具有優(yōu)先權鸠珠，支持這種特點的隊列稱為優(yōu)先隊列；
- 優(yōu)先隊列是一種特殊的數據結構秋麸，至少支持兩種操作：insert 和 deleteMin渐排，即插入和刪除最小者；一種簡單實現是：以一個單鏈表為基礎灸蟆，在表頭插入數據驯耻，并遍歷該鏈表，以刪除最小元炒考；
- 堆：也叫二叉堆可缚，可以實現優(yōu)先隊列。堆是一顆完全二叉樹斋枢，一個高為h的完全堆帘靡，有2
到2
-1個節(jié)點，高是logN ;
- 堆可以用數組來表示瓤帚，對于數組中任一位置i(為維持特性描姚，從下標1開始)上的元素，其左兒子在位置2i上戈次，右兒子在位置(2i + 1)上轩勘，它的父親則在i/2上；例如一個包含3元素的堆怯邪，A(B,C) 绊寻，A是根節(jié)點，B擎颖、C分別為左右子樹榛斯，那么對應的數組array[ ]大小為3+2，a[1] = A搂捧，a[2] = B, a[3] = C ;其中a[0] 和a[4]為空驮俗，不使用。
- 對于元素為N個的堆來說允跑，N/2剛好是最后一個非葉節(jié)點王凑；
- 大根堆：在堆中搪柑，對于每個節(jié)點，它的key比左索烹、右孩子的key大或者等工碾，這樣的堆稱為大根堆；
- 小根堆：在堆中百姓，對于每個節(jié)點渊额，它的key比左、右孩子的key小或者等垒拢，這樣的堆稱為小根堆旬迹；
- 堆的插入：在size-1位置后，再創(chuàng)建一個空的可用位置求类，簡稱空穴奔垦，這樣保持了堆的特性。如果放入X后尸疆，不破壞堆的特性椿猎，那么插入完成；如果破壞了寿弱，則將空穴朝著根的方向向上冒一步犯眠，直至完成。Java版本：
public class BinaryHeap {
private static final int CAPACITY = 10;
private int currentSize;
private int[] heapArray;
public void insert(int x){
if (currentSize == heapArray.length -1){
// 擴展大小脖捻，暫略
}
int hole = ++currentSize;
for(;hole >1 && x < heapArray[hole];hole /= 2){
heapArray[hole] = heapArray[hole/2];
}
heapArray[hole] = x;
}
}
????Kotlin版本：
class BinaryHeap {
private var currentSize = 0
private var heapArray: IntArray
fun insert(x: Int) {
if (currentSize == heapArray.size - 1) {
// 擴展大小阔逼，暫略
}
var hole = ++currentSize
while (hole > 1 && x < heapArray[hole]) {
heapArray[hole] = heapArray[hole / 2]
hole /= 2
}
heapArray[hole] = x
}
companion object {
private const val CAPACITY = 10
}
}
- 堆的構造，Java版本：
public class BinaryHeap {
private static final int CAPACITY = 10;
private int currentSize;
private int[] heapArray;
public BinaryHeap(int[] items) {
currentSize = items.length;
heapArray = new int[(currentSize + 2) * 11 / 10];
int i = 1;
for (int item:items){
heapArray[i++] = item;
}
buildHeap();
}
private void buildHeap(){
for (int i = currentSize/2;i>0;i--){ //對每個非葉節(jié)點依次處理
percolateDown(i);
}
}
private void percolateDown(int hole){
int child;
int tmp = heapArray[hole];
for (;hole *2 <= currentSize;hole = child){
child = hole *2;
if (child != currentSize && heapArray[child +1] < heapArray[child]){
child ++;
}
if (heapArray[child]<tmp){
heapArray[hole]= heapArray[child];
}else {
break;
}
}
heapArray[hole] = tmp;
}
????Kotlin版本：
class BinaryHeap(items: IntArray) {
private val currentSize: Int
private val heapArray: IntArray
init {
currentSize = items.size
heapArray = IntArray((currentSize + 2) * 11 / 10)
var i = 1
for (item in items) {
heapArray[i++] = item
}
buildHeap()
}
private fun buildHeap() {
for (i in currentSize / 2 downTo 1) {
percolateDown(i)
}
}
private fun percolateDown(hole: Int) {
var hole = hole
var child: Int
val tmp = heapArray[hole]
while (hole * 2 <= currentSize) {
child = hole * 2
if (child != currentSize && heapArray[child + 1] < heapArray[child]) {
child++
}
if (heapArray[child] < tmp) {
heapArray[hole] = heapArray[child]
} else {
break
}
hole = child
}
heapArray[hole] = tmp
}
companion object {
private const val CAPACITY = 10
}
}
(7)算法設計思想
????本小節(jié)將介紹幾種算法設計思想地沮，有：貪婪算法嗜浮、分治算法、動態(tài)規(guī)劃摩疑、回溯算法危融。
貪婪算法：貪婪算法可謂是大名鼎鼎，使用得非常廣泛雷袋。它分階段地工作吉殃，每個階段，可以認為所做決定是好的楷怒，而不考慮將來的后果蛋勺。這常常在局部達到最優(yōu)，“眼下能夠拿到的就拿”鸠删。當算法終止時抱完，如果局部最優(yōu)等于全局最優(yōu)，那么算法就是正確的刃泡；否則巧娱，算法得到的就是一個次最優(yōu)解碉怔。代表算法有：Dijkstra算法、Prim算法和Kruskal算法禁添，見 14_業(yè)界經典算法第(3)撮胧、(4)、(5)小節(jié)老翘。
分治算法：將大問題分解成若干子問題芹啥，子問題之間相互獨立，從子問題的解構建原問題的解酪捡。典型的應用如快速排序叁征、歸并排序(見 10_經典排序查找算法第(5)纳账、(7)小節(jié))逛薇，求最大子序列和算法(見 14_業(yè)界經典算法第(1)條中的第三種算法)也用到了它。
動態(tài)規(guī)劃：基本思想和分治算法類似疏虫，也是將大問題分解成若干個子問題(階段)永罚，不同點是這些子問題不是相互獨立的，后一個子問題需要用到前一個子問題的結果卧秘。將遞歸算法改為迭代算法時經常要用到這種思想呢袱。如斐波那契數列的迭代版本(見 《13_經典數學問題算法》第(8)小節(jié))，就是使用兩個參數保留上一次的計算結果翅敌，從而將算法由指數版本改為線性版本羞福；迭代版本實現數學遞推公式(見 《13_經典數學問題算法》第(10)小節(jié))也用到了它。
回溯算法：很多情況下蚯涮，回溯算法相當于窮舉搜索的巧妙實現治专，它是一種試探性的算法，在嘗試過程中尋找問題的解遭顶，如果不滿足张峰，就回溯到別的路徑。見 《12_經典趣題算法》第(10)小節(jié)漁夫捕魚問題棒旗。
(8)紅黑樹
????紅黑樹(red-black樹)是一種特殊的二叉查找樹喘批。對紅黑樹的操作在最壞情況下花費O(log N)時間。紅黑樹的每個節(jié)點铣揉，要么是紅色饶深，要么是黑色。它有如下性質：
- 每一個節(jié)點或者是黑色逛拱，或者是紅色敌厘；
- 根節(jié)點是黑色的；
- 每個葉子節(jié)點是黑色的(指為null的節(jié)點)橘券；
- 如果一個節(jié)點是紅色的额湘，那么它的子節(jié)點必須是黑色的卿吐；
- 從一個節(jié)點到該節(jié)點的子孫節(jié)點所有路徑包含相同數目的黑色節(jié)點。
????紅黑樹的基本結構和插入操作如下：
public class RBTree<T extends Comparable<T>> {
public class RBTNode<T extends Comparable<T>> {
boolean color; // 顏色
T key; // 關鍵字(鍵值)
RBTNode<T> left; // 左孩子
RBTNode<T> right; // 右孩子
RBTNode<T> parent; // 父結點
public RBTNode(T key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
}
private RBTNode<T> mRoot; // 根結點
private static final boolean RED = false;
private static final boolean BLACK = true;
//左旋
private void leftRotate(RBTNode<T> x) {
// 設置x的右孩子為y
RBTNode<T> y = x.right;
// 將 “y的左孩子” 設為 “x的右孩子”锋华；
// 如果y的左孩子非空嗡官，將 “x” 設為 “y的左孩子的父親”
x.right = y.left;
if (y.left != null)
y.left.parent = x;
// 將 “x的父親” 設為 “y的父親”
y.parent = x.parent;
if (x.parent == null) {
this.mRoot = y; // 如果 “x的父親” 是空節(jié)點，則將y設為根節(jié)點
} else {
if (x.parent.left == x)
x.parent.left = y; // 如果 x是它父節(jié)點的左孩子毯焕，則將y設為“x的父節(jié)點的左孩子”
else
x.parent.right = y; // 如果 x是它父節(jié)點的左孩子衍腥，則將y設為“x的父節(jié)點的左孩子”
}
// 將 “x” 設為 “y的左孩子”
y.left = x;
// 將 “x的父節(jié)點” 設為 “y”
x.parent = y;
}
//右旋
private void rightRotate(RBTNode<T> y) {
// 設置x是當前節(jié)點的左孩子。
RBTNode<T> x = y.left;
// 將 “x的右孩子” 設為 “y的左孩子”纳猫；
// 如果"x的右孩子"不為空的話婆咸，將 “y” 設為 “x的右孩子的父親”
y.left = x.right;
if (x.right != null)
x.right.parent = y;
// 將 “y的父親” 設為 “x的父親”
x.parent = y.parent;
if (y.parent == null) {
this.mRoot = x; // 如果 “y的父親” 是空節(jié)點，則將x設為根節(jié)點
} else {
if (y == y.parent.right)
y.parent.right = x; // 如果 y是它父節(jié)點的右孩子芜辕，則將x設為“y的父節(jié)點的右孩子”
else
y.parent.left = x; // (y是它父節(jié)點的左孩子) 將x設為“x的父節(jié)點的左孩子”
}
// 將 “y” 設為 “x的右孩子”
x.right = y;
// 將 “y的父節(jié)點” 設為 “x”
y.parent = x;
}
public void insert(T key) {
RBTNode<T> node=new RBTNode<T>(key,BLACK,null,null,null);
// 如果新建結點失敗尚骄，則返回。
if (node != null)
insert(node);
}
//將結點插入到紅黑樹中
private void insert(RBTNode<T> node) {
int cmp;
RBTNode<T> y = null;
RBTNode<T> x = this.mRoot;
// 1. 將紅黑樹當作一顆二叉查找樹侵续，將節(jié)點添加到二叉查找樹中倔丈。
while (x != null) {
y = x;
cmp = node.key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else
x = x.right;
}
node.parent = y;
if (y != null) {
cmp = node.key.compareTo(y.key);
if (cmp < 0)
y.left = node;
else
y.right = node;
} else {
this.mRoot = node;
}
// 2. 設置節(jié)點的顏色為紅色
node.color = RED;
// 3. 將它重新修正為一顆二叉查找樹
insertFixUp(node);
}
/*
* 紅黑樹插入修正函數
*
* 在向紅黑樹中插入節(jié)點之后(失去平衡)，再調用該函數状蜗；
* 目的是將它重新塑造成一顆紅黑樹需五。
*/
private void insertFixUp(RBTNode<T> node) {
RBTNode<T> parent, gparent;
// 若“父節(jié)點存在，并且父節(jié)點的顏色是紅色”
while (((parent = parentOf(node))!=null) && isRed(parent)) {
gparent = parentOf(parent);
//若“父節(jié)點”是“祖父節(jié)點的左孩子”
if (parent == gparent.left) {
// Case 1條件：叔叔節(jié)點是紅色
RBTNode<T> uncle = gparent.right;
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色轧坎，且當前節(jié)點是右孩子
if (parent.right == node) {
RBTNode<T> tmp;
leftRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色宏邮，且當前節(jié)點是左孩子。
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
} else { //若“z的父節(jié)點”是“z的祖父節(jié)點的右孩子”
// Case 1條件：叔叔節(jié)點是紅色
RBTNode<T> uncle = gparent.left;
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色缸血，且當前節(jié)點是左孩子
if (parent.left == node) {
RBTNode<T> tmp;
rightRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色蜜氨，且當前節(jié)點是右孩子。
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
// 將根節(jié)點設為黑色
setBlack(this.mRoot);
}
private void setRed(RBTNode<T> node) {
node.color = RED;
}
private void setBlack(RBTNode<T> node) {
node.color = BLACK;
}
private boolean isRed(RBTNode<T> node) {
return node.color == RED;
}
private RBTNode<T> parentOf(RBTNode<T> node) {
return node.parent;
}
}
????這其中的左旋属百、右旋和AVL樹是非常類似的记劝，不同點在于需要額外處理節(jié)點的parent成員。
????紅黑樹有幾種擴展：BB樹族扰、AA樹厌丑、treep樹，分別介紹如下：
BB樹全稱是二叉B樹(binary B-tree)渔呵，它是一個帶附加條件的紅黑樹：一個節(jié)點最多可以有一個紅兒子怒竿。
AA樹：用level代替color的一種紅黑樹，如果節(jié)點是樹葉扩氢，level = 1耕驰；如果該節(jié)點是紅色的，level等于它的父節(jié)點的level录豺；如果該節(jié)點是黑色的朦肘，level等于父節(jié)點的level減1饭弓。
????結構如下：
class AANode<T> {
T element;
AANode<T> left;
AANode<T> right;
int level;
AANode(T element,AANode<T> left,AANode<T> right){
this.element = element;
this.left = left;
this.right = right;
level = 1;
}
}
treep樹：用優(yōu)先級代替color的一種紅黑樹，優(yōu)先級滿足小根堆的性質媒抠。
????結構如下：
class TreepNode<T>{
T element;
TreepNode<T> left;
TreepNode<T> right;
int priority;
TreepNode(T element,TreepNode<T> left,TreepNode<T> right){
this.element = element;
this.left = left;
this.right = right;
priority = random.nextInt();
}
static Random random = new Random();
}
???? Over !
