[[353954]]

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

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

樹

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

樹的定義

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

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

二叉樹

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

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

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

二叉搜索樹

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

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

平衡二叉樹

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

B-樹

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

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

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

B+樹

B+樹具有以下特點(diǎn)

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

紅黑樹

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

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