[[353954]]

本文轉(zhuǎn)載自微信公眾號「小明菜市場」，作者小明菜市場 。轉(zhuǎn)載本文請聯(lián)系小明菜市場公眾號。

Hello ! 我是小小，今天總結(jié)一下什么是樹，以及關(guān)于樹的一些內(nèi)容。。

樹

樹是一種非常常用的數(shù)據(jù)結(jié)構(gòu)，與線性表，堆棧并駕齊驅(qū)。

樹的定義

樹是從自然界抽象出來的，它指的是N個父子節(jié)點的有限集合，對于這個有限集合，需要滿足如下條件：

1. 當(dāng)N=0時，該節(jié)點集合為空，這棵樹也為空
2. 在任意非空樹中，只能有一個根節(jié)點
3. 當(dāng)N>1時，除去跟節(jié)點意外的其余節(jié)點本身也要集合成為一顆樹。即，樹具有遞歸特性，一棵樹是由若干子樹組成，每顆樹又是由若干顆更小的子樹組成，如圖所示

二叉樹

二叉樹指每個節(jié)點最多只能有兩個子樹的有序樹。通常左邊子樹稱之為左子樹，右邊樹稱之為右子樹。二叉樹最多只能有兩顆對稱的樹，二叉樹有左，右之分。樹和二叉樹的區(qū)別

1. 樹的節(jié)點的度數(shù)沒有限制，二叉樹限制為2，樹沒有限制。

2. 無序樹的節(jié)點沒有左右之分，二叉樹的節(jié)點有左右之分。

二叉搜索樹

二叉搜索樹，它是一顆空樹，具有以下性質(zhì)的二叉樹，稱之為二叉搜索樹

1. 它的左子樹不為空，并且左子樹的所有節(jié)點值都要小于跟節(jié)點的值。
2. 它的右子樹不為空，則右子樹的所有節(jié)點的值都要大于跟節(jié)點的值。
3. 它的左右子樹分別為二叉排序樹。

平衡二叉樹

平衡二叉樹具有以下性質(zhì) 他是一顆控訴或者他的左右兩個子樹的高度差絕對值不超過1，并且左右兩個子樹都是一顆平衡二叉樹。平衡二叉樹實現(xiàn)有紅黑樹，AVL，伸展樹，最小二叉平衡樹的節(jié)點公示為：F(n)=F(n-1)+F(n-2)+1

B-樹

一顆m階B樹，是一顆平衡的m路搜索樹，或者是空樹，滿足以下性質(zhì)

1. 1根節(jié)點至少有兩個子女
2. 每個非跟節(jié)點包含k-1個元素和k個孩子，其中m/2 <= k <= m
3. 所有的葉子結(jié)點都位于同一層。
4. 每個節(jié)點中的元素從小到大排列，節(jié)點當(dāng)中k-1個元素正好是k個孩子包含的元素值域的劃分一般用于文件系統(tǒng)或者數(shù)據(jù)庫的索引

一般用于文件系統(tǒng)或者數(shù)據(jù)庫的索引

B+樹

B+樹具有以下特點

1. 有k個子樹的中間節(jié)點包含k個元素，每個元素不保存數(shù)據(jù)，只用來保存索引，所有數(shù)據(jù)保存在葉子節(jié)點。
2. 所有的葉子節(jié)點中包含了全部的元素信息，以及指向這些元素信息的執(zhí)政，并且葉子節(jié)點本身也是按照由大到小依次排列。
3. 所有的中間節(jié)點元素都保存在葉子節(jié)點，在子元素中總是最大或者最小的元素。

紅黑樹

紅黑樹是平衡二叉樹的實現(xiàn)，具有以下特征

1. 節(jié)點是紅色或者是黑色。
2. 根節(jié)點時黑色。
3. 每個葉子節(jié)點都是黑色節(jié)點的空節(jié)點
4. 每個紅色節(jié)點的兩個子節(jié)點都是黑色，從每個葉子節(jié)點到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點
5. 從任意節(jié)點到每個葉子節(jié)點所有的路徑都包含相同數(shù)目的黑色節(jié)點。