目錄
一、樹簡介
二、二叉樹
1、簡介
2、二叉樹的性質(zhì)
3、滿二叉樹和完全二叉樹?
三、二叉樹的遍歷
四、二叉樹遍歷代碼實(shí)現(xiàn)
五、二叉搜索樹（Binary Search Tree）
1、簡介
2、二插搜索樹的局限性
六、平衡二叉搜索樹（AVL樹）
七、紅黑樹（Red-Black Tree）
1、簡介
2、性質(zhì)
3、使用場景?
八、B樹（B-Tree）
?1、簡介
2、特點(diǎn)
九、B+樹
1、簡介
2、B+的特性
3、稠密索引
4、稀疏索引
一、樹簡介
????????樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，是由n（n >=0）個(gè)結(jié)點(diǎn)組成的有限集合。
????????如果n==0，樹為空樹。如果n>0，樹有一個(gè)特定的結(jié)點(diǎn)，叫做根結(jié)點(diǎn)（root）。根結(jié)點(diǎn)只有直接后繼，沒有直接前驅(qū)
????????除根結(jié)點(diǎn)以外的其他結(jié)點(diǎn)劃分為m（m>=0）個(gè)互不相交的有限集合，T0，T1，T2，...，Tm-1，每個(gè)集合都是一棵樹，稱為根結(jié)點(diǎn)的子樹（sub tree）。
?
下面是一些其它基本概念：
- 節(jié)點(diǎn)的度：節(jié)點(diǎn)擁有的子樹個(gè)數(shù)
- 葉子節(jié)點(diǎn)（leaf）：度為0的節(jié)點(diǎn)，也就是沒有子樹的節(jié)點(diǎn)
- 樹的高度：樹中節(jié)點(diǎn)的最大層數(shù)，也叫做樹的深度
二、二叉樹
1、簡介
對(duì)于樹這種數(shù)據(jù)結(jié)構(gòu)，使用最頻繁的是二叉樹。
每個(gè)節(jié)點(diǎn)最多只有2個(gè)子節(jié)點(diǎn)的樹，叫做二叉樹。二叉樹中，每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)作為根的兩個(gè)子樹，一般叫做節(jié)點(diǎn)的左子樹和右子樹。
?
2、二叉樹的性質(zhì)
- 若二叉樹的層次從0開始，則在二叉樹的第i層至多有2^i個(gè)結(jié)點(diǎn)(i>=0)
- 高度為k的二叉樹最多有2^(k+1) - 1個(gè)結(jié)點(diǎn)(k>=-1)(空樹的高度為-1)
- 對(duì)任何一棵二叉樹，如果其葉子結(jié)點(diǎn)(度為0)數(shù)為m, 度為2的結(jié)點(diǎn)數(shù)為n, 則m = n + 1
3、滿二叉樹和完全二叉樹?
- 滿二叉樹：除了葉子節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，每一層都被完全填充。
- 完全二叉樹：除了最后一層外，每一層都被完全填充，并且最后一層所有節(jié)點(diǎn)保持向左對(duì)齊。
三、二叉樹的遍歷
- 中序遍歷：即左-根-右遍歷，對(duì)于給定的二叉樹根，尋找其左子樹；對(duì)于其左子樹的根，再去尋找其左子樹；遞歸遍歷，直到尋找最左邊的節(jié)點(diǎn)i，其必然為葉子，然后遍歷i的父節(jié)點(diǎn)，再遍歷i的兄弟節(jié)點(diǎn)。隨著遞歸的逐漸出棧，最終完成遍歷
?
- 先序遍歷：即根-左-右遍歷
?
- 后序遍歷：即左-右-根遍歷
?
- 層序遍歷：按照從上到下、從左到右的順序，逐層遍歷所有節(jié)點(diǎn)。
?
四、二叉樹遍歷代碼實(shí)現(xiàn)
package com.kgf.algorithm.tree;
import java.util.ArrayDeque;
import java.util.Queue;
/***
* 二叉樹的遍歷
*/
public class TreeErgodic {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
TreeNode tn1 = new TreeNode(3);
TreeNode tn2 = new TreeNode(5);
TreeNode tn3 = new TreeNode(2);
TreeNode tn4 = new TreeNode(7);
TreeNode tn5 = new TreeNode(6);
root.left=tn1;
root.right=tn2;
tn1.left = tn3;
tn1.right = tn4;
tn2.left = tn5;
TreeErgodic te = new TreeErgodic();
te.levelTraversal2(root);
}
/***
* 層序遍歷
* 按照從上到下、從左到右的順序，逐層遍歷所有節(jié)點(diǎn)。
* 結(jié)果是：1 3 5 2 7 6
* @param treeNode
*/
public void levelTraversal2(TreeNode treeNode){
//創(chuàng)建一個(gè)隊(duì)列，先進(jìn)先出
Queue<TreeNode> queue = new ArrayDeque();
queue.add(treeNode);
while (!queue.isEmpty()){
TreeNode node = queue.poll();
System.out.print(node.val+"\t");
if (node.left!=null){
queue.add(node.left);
}
if (node.right!=null){
queue.add(node.right);
}
}
}
/***
* 層序遍歷
* 按照從上到下、從左到右的順序，逐層遍歷所有節(jié)點(diǎn)。
* 結(jié)果是：1 3 5 2 7 6
* @param treeNode
*/
public void levelTraversal(TreeNode treeNode){
//創(chuàng)建一個(gè)隊(duì)列，先進(jìn)先出
Queue queue = new ArrayDeque();
queue.add(treeNode.val);
loadTreeNode(treeNode,queue);
while (!queue.isEmpty()){
System.out.print(queue.poll()+"\t");
}
}
private void loadTreeNode(TreeNode treeNode, Queue queue) {
if (treeNode==null)return;
if (treeNode.left!=null){
queue.add(treeNode.left.val);
}
if (treeNode.right!=null){
queue.add(treeNode.right.val);
}
loadTreeNode(treeNode.left,queue);
loadTreeNode(treeNode.right,queue);
}
/***
* 后序遍歷
* 即左-右-根遍歷
* 結(jié)果是：2 7 3 6 5 1
* @param treeNode
*/
public void afterOrder(TreeNode treeNode){
if (treeNode==null)return;
afterOrder(treeNode.left);
afterOrder(treeNode.right);
System.out.print(treeNode.val+"\t");
}
/***
* 中序遍歷
* 即左-根-右遍歷
* 結(jié)果是：2 3 7 1 6 5
* @param treeNode
*/
public void centerOrder(TreeNode treeNode){
if (treeNode==null)return;
centerOrder(treeNode.left);
System.out.print(treeNode.val+"\t");
centerOrder(treeNode.right);
}
/***
* 先序遍歷
* 即根-左-右遍歷
* 結(jié)果是：1 3 2 7 5 6
* @param treeNode
*/
public void preOrder(TreeNode treeNode){
if (treeNode==null)return;
System.out.print(treeNode.val+"\t");
preOrder(treeNode.left);
preOrder(treeNode.right);
}
}
五、二叉搜索樹（Binary Search Tree）
1、簡介
二叉搜索樹也稱為有序二叉查找樹，滿足二叉查找樹的一般性質(zhì)，是指一棵空樹具有如下性質(zhì)：
- 任意節(jié)點(diǎn)左子樹如果不為空，則左子樹中節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值
- 任意節(jié)點(diǎn)右子樹如果不為空，則右子樹中節(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值
- 任意節(jié)點(diǎn)的左右子樹，也分別是二叉搜索樹
- 沒有鍵值相等的節(jié)點(diǎn)
基于二叉搜索樹的這種特點(diǎn)，在查找某個(gè)節(jié)點(diǎn)的時(shí)候，可以采取類似于二分查找的思想，快速找到某個(gè)節(jié)點(diǎn)。n 個(gè)節(jié)點(diǎn)的二叉查找樹，正常的情況下，查找的時(shí)間復(fù)雜度為 O(logN)。?
2、二插搜索樹的局限性
?一個(gè)二叉搜索樹是由n個(gè)節(jié)點(diǎn)隨機(jī)構(gòu)成，所以，對(duì)于某些情況，二叉查找樹會(huì)退化成一個(gè)有n個(gè)節(jié)點(diǎn)的線性鏈表。如下圖:
?
六、平衡二叉搜索樹（AVL樹）
?????????通過二叉搜索樹的分析我們發(fā)現(xiàn)，二叉搜索樹的節(jié)點(diǎn)查詢、構(gòu)造和刪除性能，與樹的高度相關(guān)，如果二叉搜索樹能夠更“平衡”一些，避免了樹結(jié)構(gòu)向線性結(jié)構(gòu)的傾斜，則能夠顯著降低時(shí)間復(fù)雜度。
????????平衡二叉搜索樹：簡稱平衡二叉樹。由前蘇聯(lián)的數(shù)學(xué)家Adelse-Velskil和Landis在1962年提出的高度平衡的二叉樹，根據(jù)科學(xué)家的英文名也稱為AVL樹。
它具有如下幾個(gè)性質(zhì)：
- 可以是空樹
- 假如不是空樹，任何一個(gè)結(jié)點(diǎn)的左子樹與右子樹都是平衡二叉樹，并且高度之差的絕對(duì)值不超過1
????????平衡的意思，就是向天平一樣保持左右水平，即兩邊的分量大約相同。如定義，假如一棵樹的左右子樹的高度之差超過1，如左子樹的樹高為2，右子樹的樹高為0，子樹樹高差的絕對(duì)值為2就打破了這個(gè)平衡。
????????比如，依次插入1，2，3三個(gè)結(jié)點(diǎn)后，根結(jié)點(diǎn)的右子樹樹高減去左子樹樹高為2，樹就失去了平衡。我們希望它能夠變成更加平衡的樣子。
????????AVL樹是帶有平衡條件的二叉搜索樹，它是嚴(yán)格的平衡二叉樹，平衡條件必須滿足(所有節(jié)點(diǎn)的左右子樹高度差不超過1)。不管我們是執(zhí)行插入還是刪除操作，只要不滿足上面的條件，就要通過旋轉(zhuǎn)來保持平衡，而旋轉(zhuǎn)是非常耗時(shí)的。旋轉(zhuǎn)的目的是為了降低樹的高度，使其平衡。?
?
?????????AVL樹適合用于插入刪除次數(shù)比較少，但查找多的情況。也在Windows進(jìn)程地址空間管理中得到了使用。
七、紅黑樹（Red-Black Tree）
1、簡介
?????????紅黑樹是一種特殊的二叉查找樹。紅黑樹的每個(gè)節(jié)點(diǎn)上都有存儲(chǔ)位表示節(jié)點(diǎn)的顏色，可以是紅(Red)或黑(Black)。
2、性質(zhì)
- 節(jié)點(diǎn)是紅色或黑色
- 根節(jié)點(diǎn)是黑色
- 每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）。
- 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）
- 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)
?????????在插入一個(gè)新節(jié)點(diǎn)時(shí)，默認(rèn)將它涂為紅色（這樣可以不違背最后一條規(guī)則），然后進(jìn)行旋轉(zhuǎn)著色等操作，讓新的樹符合所有規(guī)則。
????????紅黑樹也是一種自平衡二叉查找樹，可以認(rèn)為是對(duì)AVL樹的折中優(yōu)化。
3、使用場景?
紅黑樹多用于搜索,插入,刪除操作多的情況下。紅黑樹應(yīng)用比較廣泛：
- 廣泛用在各種語言的內(nèi)置數(shù)據(jù)結(jié)構(gòu)中。比如C++的STL中，map和set都是用紅黑樹實(shí)現(xiàn)的。Java中的TreeSet，TreeMap也都是用紅黑樹實(shí)現(xiàn)的。
- 著名的linux進(jìn)程調(diào)度Completely Fair Scheduler，用紅黑樹管理進(jìn)程控制塊。
- epoll在內(nèi)核中的實(shí)現(xiàn)，用紅黑樹管理事件塊
- nginx中，用紅黑樹管理timer等
八、B樹（B-Tree）
?1、簡介
????????B樹(B-Tree)是一種自平衡的樹，它是一種多路搜索樹（并不是二叉的），能夠保證數(shù)據(jù)有序。同時(shí)，B樹還保證了在查找、插入、刪除等操作時(shí)性能都能保持在O(logn)，為大塊數(shù)據(jù)的讀寫操作做了優(yōu)化，同時(shí)它也可以用來描述外部存儲(chǔ)。
2、特點(diǎn)
- B樹可以定義一個(gè)M值作為預(yù)定范圍，即M路(階)B樹，每個(gè)節(jié)點(diǎn)最多有M個(gè)孩子；且M>2
- 根結(jié)點(diǎn)的兒子數(shù)為[2, M]
- 除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2, M]
- 每個(gè)結(jié)點(diǎn)存放至少M(fèi)/2-1（取上整）和至多M-1個(gè)關(guān)鍵字；（至少2個(gè)key）
- 非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù) = 指向兒子的指針個(gè)數(shù) – 1
- 非葉子結(jié)點(diǎn)的關(guān)鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]
- 非葉子結(jié)點(diǎn)的指針：P[1], P[2], …, P[M]，其中P[1]指向關(guān)鍵字小于K[1]的子樹，P[M]指向關(guān)鍵字大于K[M-1]的子樹，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹
- 所有葉子結(jié)點(diǎn)位于同一層
?
九、B+樹
1、簡介
?B+樹是B-樹的變體，也是一種多路搜索樹。
?B+的搜索與B-樹也基本相同，區(qū)別是B+樹只有達(dá)到葉子結(jié)點(diǎn)才命中（B-樹可以在非葉子結(jié)點(diǎn)命中），其性能也等價(jià)于在關(guān)鍵字全集做一次二分查找。
2、B+的特性
- 所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中（稠密索引），且鏈表中的關(guān)鍵字恰好是有序的
- 不可能在非葉子結(jié)點(diǎn)命中
- 非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引），葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層
- 更適合文件索引系統(tǒng)
?
3、稠密索引
????????稠密索引，即每一條記錄，對(duì)應(yīng)一個(gè)索引字段。稠密索引，訪問速度非常塊，但是維護(hù)成本大。根據(jù)索引字段不一樣，有候選鍵索引和非候選鍵索引之分 。
4、稀疏索引
- 相對(duì)稠密索引，稀疏索引并沒有每條記錄，建立了索引字段，而是把記錄分為若干個(gè)塊，為每個(gè)塊建立一條索引字段
- 稀疏索引字段，要求索引字段是按順序排序的，否則無法有效索引
稀疏索引是如何進(jìn)行定位的呢？
- 假設(shè)需要搜索字段值為K的記錄，那先檢索出比K小的最大值索引字段，再根據(jù)該字段所在的記錄集合，進(jìn)行順序查找，直到找到記錄K。
- 稀疏索引，數(shù)據(jù)查詢速度較慢，但是存儲(chǔ)空間小，維護(hù)成本低
那么如何設(shè)置索引字段呢？文章來源：http://www.zghlxwxcb.cn/news/detail-450879.html
- 既然索引是為了提高訪問速度，簡單說，要是一些數(shù)據(jù)經(jīng)常被使用、被查詢，那這些字段就應(yīng)該設(shè)置索引
文章來源地址http://www.zghlxwxcb.cn/news/detail-450879.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之樹和二叉樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
