樹(Tree)的基本概念
樹是由結點或頂點和邊組成的(可能是非線性的)且不存在著任何環(huán)的一種數據結構娩梨。沒有結點的樹稱為空(null或empty)樹丹擎。一棵非空的樹包括一個根結點糖儡，還(很可能)有多個附加結點斗躏，所有結點構成一個多級分層結構柱告。
二叉樹
每個結點至多擁有兩棵子樹(即二叉樹中不存在度大于2的結點)馏鹤，并且征椒，二叉樹的子樹有左右之分，其次序不能任意顛倒湃累。
二叉樹的性質
1.若二叉樹的層次從0開始勃救，則在二叉樹的第i層至多有2^i個結點(i>=0)
2.高度為k的二叉樹最多有2^(k+1) - 1個結點(k>=-1)(空樹的高度為-1)
3.對任何一棵二叉樹，如果其葉子結點(度為0)數為m, 度為2的結點數為n, 則m = n + 1
二叉樹又分為：完美二叉樹治力，完全二叉樹蒙秒，完滿二叉樹
完美二叉樹(滿二叉樹)
完全二叉樹
完滿二叉樹
區(qū)別
二叉樹的遍歷方法
中序遍歷：即左-根-右遍歷，對于給定的二叉樹根宵统，尋找其左子樹晕讲；對于其左子樹的根，再去尋找其左子樹马澈；遞歸遍歷瓢省，直到尋找最左邊的節(jié)點i，其必然為葉子痊班，然后遍歷i的父節(jié)點勤婚，再遍歷i的兄弟節(jié)點。隨著遞歸的逐漸出棧涤伐，最終完成遍歷
先序遍歷：即根-左-右遍歷
后序遍歷：即左-右-根遍歷
在Java中常見的樹結構
二叉查找樹
二叉查找樹也稱為有序二叉查找樹,滿足二叉查找樹的一般性質,是指一棵空樹具有如下性質：
任意節(jié)點左子樹不為空,則左子樹的值均小于根節(jié)點的值
任意節(jié)點右子樹不為空,則右子樹的值均大于于根節(jié)點的值
任意節(jié)點的左右子樹也分別是二叉查找樹
沒有鍵值相等的節(jié)點
局限性及應用
一個二叉查找樹是由n個節(jié)點隨機構成,所以馒胆，對于某些情況,二叉查找樹會退化成一個有n個節(jié)點的線性鏈.如下圖:
AVL樹
AVL樹是帶有平衡條件的二叉查找樹缨称，和紅黑樹相比,它是嚴格的平衡二叉樹,平衡條件必須滿足(所有節(jié)點的左右子樹高度差不超過1).不管我們是執(zhí)行插入還是刪除操作,只要不滿足上面的條件,就要通過旋轉來保持平衡,而旋轉是非常耗時的
使用場景：
AVL樹適合用于插入刪除次數比較少，但查找多的情況祝迂。
也在Windows進程地址空間管理中得到了使用
旋轉的目的是為了降低樹的高度睦尽，使其平衡
AVL樹特點：
AVL樹是一棵二叉搜索樹
AVL樹的左右子節(jié)點也是AVL樹
AVL樹擁有二叉搜索樹的所有基本特點
每個節(jié)點的左右子節(jié)點的高度之差的絕對值最多為1，即平衡因子為范圍為[-1,1]
紅黑樹
一種自平衡二叉查找樹, 通過對任何一條從根到葉子的路徑上各個節(jié)點著色的方式的限制,紅黑樹確保從根到葉子節(jié)點的最長路徑不會是最短路徑的兩倍型雳，用非嚴格的平衡來換取增刪節(jié)點時候旋轉次數的降低当凡，任何不平衡都會在三次旋轉之內解決
使用場景：
紅黑樹多用于搜索,插入,刪除操作多的情況下
紅黑樹應用比較廣泛：
1.廣泛用在C++的STL中。map和set都是用紅黑樹實現的纠俭。
2.著名的linux進程調度Completely Fair Scheduler,用紅黑樹管理進程控制塊宁玫。
3.epoll在內核中的實現，用紅黑樹管理事件塊
4.nginx中柑晒，用紅黑樹管理timer等
原因：
紅黑樹的查詢性能略微遜色于AVL樹，因為比AVL樹會稍微不平衡最多一層眷射，也就是說紅黑樹的查詢性能只比相同內容的AVL樹最多多一次比較匙赞，但是，紅黑樹在插入和刪除上完爆AVL樹妖碉，AVL樹每次插入刪除會進行大量的平衡度計算涌庭，而紅黑樹為了維持紅黑性質所做的紅黑變換和旋轉的開銷，相較于AVL樹為了維持平衡的開銷要小得多
性質：
1.節(jié)點是紅色或黑色欧宜。
2.根節(jié)點是黑色坐榆。
3.每個葉子節(jié)點都是黑色的空節(jié)點（NIL節(jié)點）。
4 每個紅色節(jié)點的兩個子節(jié)點都是黑色冗茸。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)
5.從任一節(jié)點到其每個葉子的所有路徑都包含相同數目的黑色節(jié)點席镀。
B樹
B-樹就是B樹,-只是一個符號.
B樹(B-Tree)是一種自平衡的樹,它是一種多路搜索樹（并不是二叉的），能夠保證數據有序夏漱。同時它還保證了在查找豪诲、插入、刪除等操作時性能都能保持在O(logn)挂绰，為大塊數據的讀寫操作做了優(yōu)化,同時它也可以用來描述外部存儲(支持對保存在磁盤或者網絡上的符號表進行外部查找)
特點：
1.定義任意非葉子結點最多只有M個兒子屎篱；且M>2
2.根結點的兒子數為[2, M]
3.除根結點以外的非葉子結點的兒子數為[M/2, M]
4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）
5.非葉子結點的關鍵字個數=指向兒子的指針個數-1
6.非葉子結點的關鍵字：K[1], K[2], …, K[M-1]葵蒂；且K[i] < K[i+1]
7.非葉子結點的指針：P[1], P[2], …, P[M]交播，其中P[1]指向關鍵字小于K[1]的子樹，P[M]指向關鍵字大于K[M-1]的子樹践付，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹
8.所有葉子結點位于同一層
如：（M=3）
插入與平衡過程
這個圖用以表示往 4 階 B 樹中依次插入下面這組數據的過程：
6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
4 階 B 樹表示每個節(jié)點最多有 4 個子樹秦士、3 個關鍵字，最少有 2 個子樹荔仁、一個關鍵字
添加/刪除也是一樣的伍宦，要考慮添加/刪除孩子后芽死，父節(jié)點是否還滿足子樹 k 介于 M/2 和 M 的條件，不滿足就得從別的節(jié)點拆子樹甚至修改相關子樹結構來保持平衡次洼。
B+樹
B+樹是B-樹的變體关贵，也是一種多路搜索樹
B+的搜索與B-樹也基本相同，區(qū)別是B+樹只有達到葉子結點才命中（B-樹可以在非葉子結點命中）卖毁，其性能也等價于在關鍵字全集做一次二分查找揖曾；
B+的特性：
1.所有關鍵字都出現在葉子結點的鏈表中（稠密索引），且鏈表中的關鍵字恰好是有序的
2.不可能在非葉子結點命中
3.非葉子結點相當于是葉子結點的索引（稀疏索引）亥啦，葉子結點相當于是存儲（關鍵字）數據的數據層
4.更適合文件索引系統(tǒng)
原因： 增刪文件（節(jié)點）時炭剪，效率更高，因為B+樹的葉子節(jié)點包含所有關鍵字翔脱，并以有序的鏈表結構存儲奴拦，這樣可很好提高增刪效率
如：（M=3）
使用場景：
文件系統(tǒng)和數據庫系統(tǒng)中常用的B/B+ 樹，他通過對每個節(jié)點存儲個數的擴展届吁，使得對連續(xù)的數據能夠進行較快的定位和訪問错妖，能夠有效減少查找時間，提高存儲的空間局部性從而減少IO操作疚沐。他廣泛用于文件系統(tǒng)及數據庫中暂氯，如：
Windows：HPFS 文件系統(tǒng)
Mac：HFS，HFS+ 文件系統(tǒng)
Linux：ResiserFS亮蛔，XFS痴施，Ext3FS，JFS 文件系統(tǒng)
數據庫：ORACLE究流，MYSQL辣吃，SQLSERVER 等中
B樹：有序數組+平衡多叉樹
B+樹：有序數組鏈表+平衡多叉樹
B+ 樹的優(yōu)點：
1.層級更低，IO 次數更少
2.每次都需要查詢到葉子節(jié)點梯嗽，查詢性能穩(wěn)定
3.葉子節(jié)點形成有序鏈表齿尽，范圍查詢方便
B+數插入和平衡
B+樹還有一個最大的好處，方便掃庫灯节，B樹必須用中序遍歷的方法按序掃庫循头，而B+樹直接從葉子結點挨個掃一遍就完了，B+樹支持range-query非常方便炎疆，而B樹不支持卡骂。這是數據庫選用B+樹的最主要原因。
比如要查 5-10之間的形入，B+樹一把到5這個標記全跨，再一把到10，然后串起來就行了亿遂，B樹就非常麻煩浓若。B樹的好處渺杉，就是成功查詢特別有利，因為樹的高度總體要比B+樹矮挪钓。不成功的情況下是越，B樹也比B+樹稍稍占一點點便宜。
