樹
概念
它是由n（n>0）個有限節(jié)點組成一個具有層次關系的集合。特點
每個節(jié)點有零個或多個子節(jié)點色洞；
沒有父節(jié)點的節(jié)點稱為根節(jié)點戏锹；
每一個非根節(jié)點有且只有一個父節(jié)點；
除了根節(jié)點外火诸，每個子節(jié)點可以分為多個不相交的子樹锦针；
有序樹和無序樹
無序樹
樹中任意節(jié)點的子節(jié)點之間沒有順序關系，也稱自由樹惭蹂；有序樹
樹中任意節(jié)點的子節(jié)點之間有順序關系相關術語
節(jié)點的度：一個節(jié)點含有的子樹的個數稱為該節(jié)點的度伞插；
樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度盾碗；
葉節(jié)點或終端節(jié)點：度為零的節(jié)點媚污；
非終端節(jié)點或分支節(jié)點：度不為零的節(jié)點；
父親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點廷雅，則這個節(jié)點稱為其子節(jié)點的父節(jié)點耗美；
孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點；
兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點航缀；
節(jié)點的層次：從根開始定義起商架，根為第1層，根的子節(jié)點為第2層芥玉，以此類推蛇摸；
樹的高度或深度：樹中節(jié)點的最大層次；
堂兄弟節(jié)點：父節(jié)點在同一層的節(jié)點互為堂兄弟灿巧；
節(jié)點的祖先：從根到該節(jié)點所經分支上的所有節(jié)點赶袄；
子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫揽涮。
森林：由m（m>=0）棵互不相交的樹的集合稱為森林；
二叉樹
二叉樹是一種特殊的有序樹：每個節(jié)點至多有兩個分支（子節(jié)點）饿肺，分支具有左右次序蒋困，不能顛倒。
兩種特殊的二叉樹：
完全二叉樹：除最后一層外敬辣，若其余層都是滿的雪标，并且最后一層或者是滿的，或者是在右邊缺少連續(xù)若干節(jié)點（注意是右邊溉跃，而不能是左邊缺少）村刨。
滿二叉樹：每一層都是滿的（除了最后一層，這里的最后一層是指葉節(jié)點）喊积。
二叉搜索（查找）樹
二叉查找樹（英語：Binary Search Tree烹困，簡寫為BST），也稱二叉搜索樹乾吻、有序二叉樹（英語：ordered binary tree）髓梅，排序二叉樹（英語：sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：
a.若任意節(jié)點的左子樹不空绎签，則左子樹上所有結點的值均小于它的根結點的值枯饿；
b.若任意節(jié)點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值诡必；
c.任意節(jié)點的左奢方、右子樹也分別為二叉查找樹；
d.沒有鍵值相等的節(jié)點爸舒。
簡單的說就是：各節(jié)點值不同蟋字，并且對于任意一個子樹：左<根<右。
二叉查找樹相比于其他數據結構的優(yōu)勢在于查找扭勉、插入的時間復雜度較低鹊奖，期望O(log n)，最壞為O(n)涂炎。
查找效率與樹的高度成反比忠聚，關鍵在于減小二叉查找樹的高度為O(log n)。
平衡樹
平衡樹是一種改進的二叉查找樹唱捣，一般的二叉查找樹的查詢復雜度是跟目標結點到樹根的距離（即深度）有關两蟀，因此當結點的深度普遍較大時，查詢的均攤復雜度會上升震缭，為了更高效的查詢赂毯，平衡樹應運而生了。
在這里，平衡指所有葉子的深度趨于平衡欢瞪，更廣義的是指在樹上所有可能查找的均攤復雜度偏低活烙。樸素的理解：普通二叉查找樹徐裸，在新增/刪除等操作后遣鼓，會變得又高又瘦，會讓查找/新增/刪除操作的時間復雜度變大重贺，而平衡二叉樹在新增/刪除等操作后依然會保持矮矮胖胖的形態(tài)骑祟，使樹的高度維持在log n附近。這種形態(tài)就是平衡气笙，會使查找速度更快次企。為什么能夠保持這種好身材呢？通過在新增/刪除時的旋轉（左旋和右旋）潜圃。
常見的平衡樹：
AVL樹缸棵、Treap、伸展樹谭期、紅黑樹堵第、加權平衡樹、2-3樹隧出、AA樹踏志、替罪羊樹、節(jié)點大小平衡樹
紅黑樹
紅黑樹（英語：Red–black tree）是一種自平衡二叉查找樹胀瞪。
它的操作有著良好的最壞情況運行時間针余，并且在實踐中是高效的：它可以在O(log n)時間內做查找，插入和刪除凄诞，這里的n是樹中元素的數目圆雁。
- 紅黑樹的性質
- 節(jié)點是紅色或黑色。
- 根是黑色帆谍。
- 所有葉子都是黑色（葉子是NIL節(jié)點）伪朽。
- 每個紅色節(jié)點必須有兩個黑色的子節(jié)點。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點既忆。）
- 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數目的黑色節(jié)點驱负。
B樹
B樹（英語：B-tree）是一種自平衡的樹，能夠保持數據有序患雇。這種數據結構能夠讓查找數據跃脊、順序訪問、插入數據及刪除的動作苛吱，都在對數時間內完成酪术。B樹，概括來說是一個一般化的二叉查找樹（binary search tree），可以擁有多于2個子節(jié)點绘雁。與自平衡二叉查找樹不同橡疼，B樹為系統(tǒng)大塊數據的讀寫操作做了優(yōu)化。B樹減少定位記錄時所經歷的中間過程庐舟，從而加快存取速度欣除。B樹這種數據結構可以用來描述外部存儲。這種數據結構常被應用在數據庫和文件系統(tǒng)的實現(xiàn)上挪略。
概括關鍵詞：自平衡历帚，可以擁有多于2個子節(jié)點，適用于數據庫和文件系統(tǒng)杠娱。
待續(xù)挽牢。。摊求。
