這是數(shù)據(jù)結(jié)構類重新復習筆記的第 三 篇，同專題的其他文章可以移步：http://www.reibang.com/nb/39256701
樹
樹的實現(xiàn)
實現(xiàn)樹時蝶俱，對于每一個節(jié)點班利，除了存儲該節(jié)點的數(shù)據(jù)以外，還需要存儲一些外鏈榨呆。
一個典型的存儲方式是：左孩子右兄弟法罗标，即對于每一個節(jié)點，存儲節(jié)點的數(shù)據(jù)积蜻、指向其孩子中最左邊的孩子的指針闯割、指向其緊鄰的右側(cè)的兄弟節(jié)點的指針。
struct TreeNode
{
Object element;
TreeNode * firstChild;
TreeNode * nextSiling;
};
如下邊的這棵樹通過這種方式表現(xiàn)的結(jié)果是這樣的：
二叉樹
二叉樹（binary tree）是一棵每個節(jié)點都不能有多于兩個兒子的樹
二叉樹的特點
- 二叉樹第i層上至多有 2i-1 個節(jié)點
- 深度為k的二叉樹至多有 2k-1 個節(jié)點
- 對于一棵非空二叉樹竿拆，如果其葉子節(jié)點數(shù)為n0宙拉，度為2的節(jié)點數(shù)為n2，則n0=n2+1
- 具有n個節(jié)點的完全二叉樹的深度為 [log2n]+1 (向下取整數(shù))
- 如果對于n個節(jié)點的完全二叉樹丙笋，第 i>0 的節(jié)點谢澈，其父節(jié)點為 [(i-1)/2] (向下取整)
二叉樹的一個性質(zhì)是平均二叉樹的深度要比結(jié)點個數(shù)N小得多，這個性質(zhì)有時很重要御板。分析表明锥忿，這個平均深度為O(√N)，而對于特殊類型的二叉樹怠肋，即二叉查找樹( binary search tree)敬鬓，其深度的平均值是O(logN)。當然極端的樹的深度也可以大到N-1笙各。
二叉樹的實現(xiàn)
由于二叉樹的每個節(jié)點最多有兩個兒子列林，所以可以直接連接到它們。
struct BinaryNode
{
Object element;
BinaryNode * left;
BinaryNode * red;
};
二叉查找樹
二叉查找樹（Binary Search Trees）是二叉樹酪惭，它的特點是：對于任何一個節(jié)點X希痴，其左子樹中的所有節(jié)點的值都小于該節(jié)點X，其右子樹中的所有節(jié)點的值都大于該節(jié)點X春感。如下圖中的左邊就是一棵二叉查找是砌创，而右側(cè)不是：
重要的方法與其實現(xiàn)
-
isEmpty：是否為空樹，這一點很重要鲫懒，一般在進行樹的相關操作時都會先確定是否是一個空樹嫩实，只要指向根節(jié)點的指針為NULL，就表示是一個空樹 -
contains：是否包含某項窥岩，在確定樹非空后甲献，查找是否包含某個項，將目標項與根節(jié)點進行比較開始颂翼，如果比該節(jié)點大晃洒，就從右子樹查找慨灭，如果比該節(jié)點小，就從左子樹查找球及，如果出現(xiàn)相等的則表示包含該項氧骤，如果一直不相等且無子樹可以繼續(xù)查找，則不包含此項 -
findMin：找到最小值吃引，一直找左子樹筹陵，直到找到?jīng)]有左子樹的左子樹最左邊的節(jié)點就是最小值 -
findMax：找到最大值，一直找右子樹镊尺，直到找到?jīng)]有右子樹的右子樹最右邊的節(jié)點就是最大值 -
insert：插入某個值朦佩，從根節(jié)點開始比較，如果目標值比該節(jié)點大就插入其右子樹庐氮，否則插入左子樹语稠，如果出現(xiàn)相等的情況說明有該元素不需要再插入，直到插入某個空節(jié)點為止 -
remove：刪除節(jié)點- 刪除葉子節(jié)點：直接刪除
-
刪除有一個子節(jié)點的節(jié)點：將該子節(jié)點掛到被刪除的節(jié)點的父節(jié)點上旭愧，取代刪除節(jié)點的位置
刪除只有一個子節(jié)點的子節(jié)點 -
刪除有兩個子節(jié)點的節(jié)點：找到該節(jié)點右子樹中的最小值或者左子樹中的最大值，將其替換要刪除的元素宙暇，然后遞歸地刪除用來替換的最大/小值输枯，為什么是遞歸地刪除呢？因為被拿出來替換被刪除值的那個最大/小值也會有子樹占贫，所以刪除它的時候還要執(zhí)行刪除remove操作桃熄。但是最多只進行一次單子節(jié)點的刪除工作，因為無論是右子樹中的最小值還是左子樹中的最大值型奥，最多只有一個子樹
刪除有兩個子節(jié)點的子節(jié)
平均情況分析
| 操作 | 平均時間復雜度 |
|---|---|
| isEmpty | O(1) |
| contains | O(logN) |
| findMin/findMax | O(logN) |
| insert | O(logN) |
| remove | O(1) |
AVL樹
AVL（Adelson-Velskii and Landis）樹是帶有平衡條件（balance condition）的二叉查找樹瞳收，這個平衡條件很容易保持并且保證了樹的深度為O(logN)。
AVL樹要求每個節(jié)點的左子樹和右子樹的高度差最多為1厢汹。
AVL樹除了插入操作外螟深，其他所有的操作都可以最多以O(logN)的時間執(zhí)行
AVL樹的插入
AVL樹的插入比較復雜的點在于插入的值可能會破壞樹原本的平衡，所以在插入值后需要進行旋轉(zhuǎn)（rotation）
旋轉(zhuǎn)的情況可以根據(jù)插入后的樹的情況分為如下四種：
示意圖來源：https://blog.csdn.net/gabriel1026/article/details/6311339
| 插入后的情況 | 描述 | 旋轉(zhuǎn)方式 |
|---|---|---|
| LL-左子樹左高 | 在左子樹根節(jié)點的左子樹上插入節(jié)點而破壞平衡 | 右旋轉(zhuǎn) |
| RR-右子樹右高 | 在右子樹根節(jié)點的右子樹上插入節(jié)點而破壞平衡 | 左旋轉(zhuǎn) |
| LR-左子樹右高 | 在左子樹根節(jié)點的右子樹上插入節(jié)點而破壞平衡 | 先左旋后右旋 |
| RL-右子樹左高 | 在右子樹根節(jié)點的左子樹上插入節(jié)點而破壞平衡 | 先右旋后左旋 |
-
LL-左子樹左高的情況
LL-左子樹左高 -
RR-右子樹右高的情況
RR-右子樹右高 -
LR-左子樹右高的情況
LR-左子樹右高 -
RL-右子樹左高的情況
RL-右子樹左高
伸展樹
伸展樹與攤還時間
伸展樹（splay tree）保證從空樹開始任意連續(xù)M此對樹的操作最多花費O(MlogN)的時間烫葬，即這M次連續(xù)的操作中即使有些操作耗時長界弧，但是也有一些耗時短的操作，使得這M個連續(xù)的操作花費的總時間最壞為O(MlogN)搭综。
攤還（amortized）：一般說來垢箕，當M次操作的序列總的最壞情形運行時間為O(M f(N))時,我們就說它的攤還(amortized)運行時間為O(f(N))。因此兑巾，一棵伸展樹每次操作的攤還代價是O(logN)条获。經(jīng)過一系列的操作，有的操作可能花費時間多一些蒋歌，有的可能要少一些帅掘，不存在不好的輸入隊列委煤。
如果任意特定操作可以有最壞時間界O(N)，而我們?nèi)匀灰笠粋€O(logN)的攤還時間界锄开，那么很清楚素标，只要有一個結(jié)點被訪問，它就必須被移動萍悴。否則头遭，一旦我們發(fā)現(xiàn)一個深層的結(jié)點，就有可能不斷地對它進行訪問癣诱。如果這個結(jié)點不改變位置计维，而每次訪問又花費O(N)，那么M次訪問將花費O(MN)的時間撕予。這個思想和數(shù)據(jù)庫中將經(jīng)常訪問到的數(shù)據(jù)前移以及操作系統(tǒng)中將經(jīng)常訪問的數(shù)據(jù)放入cache高速緩存等思想相同鲫惶。（在許多應用中，當一個結(jié)點被訪問時实抡，它就很可能不久再被訪問欠母。研究表明，這種情況的發(fā)生比人們預料的要頻繁得多吆寨。）
伸展（splaying）
伸展樹的基本思想是將訪問到的一個較深的節(jié)點通過旋轉(zhuǎn)的方式將其旋轉(zhuǎn)到根節(jié)點的位置赏淌，但是為了保證旋轉(zhuǎn)過程中不讓一些較淺的節(jié)點也被淪落到較深的位置，這里的伸展采用一定的策略：
- 首先啄清，一個要被旋轉(zhuǎn)到樹根處的深節(jié)點X六水，如果X的父節(jié)點就是根節(jié)點，那么只要旋轉(zhuǎn)X和樹根即可
- 如果X的父節(jié)點不是根節(jié)點辣卒，將其父節(jié)點命名為P掷贾，同時X一定有祖父節(jié)點G，X荣茫、P想帅、G三個節(jié)點存在兩種排列關系：
-
“之字形”（zig-zag）：這種情況下執(zhí)行一次AVL樹同理的雙旋轉(zhuǎn)
“之字形”（zig-zag） -
“一字形”（zig-zig）：這種情況下直接將樹左右對調(diào)（類似于蹺蹺板）
“一字形”（zig-zig）
-
一個例子
如下圖，想把 K1 節(jié)點調(diào)至樹根處
首先由K1啡莉、K2博脑、K3構成了一個“之字形”結(jié)構，使用雙旋轉(zhuǎn)方式得到如下的第一次調(diào)整
然后由K1票罐、K4叉趣、K5構成了一個“一字形”結(jié)構，采用蹺蹺板的方式做第二次調(diào)整
樹的遍歷
樹的遍歷分為三種
- 先根遍歷：每棵樹按照 根-左子樹-右子樹 順序遍歷
- 中根遍歷：每棵樹按照 左子樹-根-右子樹 順序遍歷
- 后根遍歷：每棵樹按照 左子樹-右子樹-根 順序遍歷
B樹
B樹的思想很簡單该押，如果我們使用二叉樹疗杉，樹的平均深度為logN，如果我們是一個M叉樹（每個節(jié)點最多有M個子樹），則樹的平均深度為logMN烟具，顯然這樣會使得樹的深度降低梢什。
M階B樹的規(guī)范
- 數(shù)據(jù)項存儲在樹葉上
- 非葉結(jié)點存儲直到 M-1 個鍵，以指示搜索的方向朝聋；鍵 i 代表子樹 i+1 中的最小的鍵
- 樹的根或者是一片樹葉嗡午，或者其兒子數(shù)在2和M之間
- 除根外，所有非樹葉結(jié)點的兒子數(shù)在 [M/2]（向上取整）和M之間
- 所有的樹葉都在相同的深度上并有 [L/2]（向上取整）和L之間個數(shù)據(jù)項
一個5階B樹的例子
一個5階的B樹冀痕，所有的非葉子節(jié)點的兒子都在3和5之間荔睹，從而有2到4個鍵，根可能只有兩個的兒子言蛇，L=5僻他，因此每個樹葉有3到5個數(shù)據(jù)項，要求節(jié)點一半滿腊尚，保證B樹不致退化成簡單的二叉樹
向B樹中插入 57 數(shù)據(jù)項：按照鍵索引到插入數(shù)據(jù)的位置吨拗，插入數(shù)據(jù)項
再插入 55 數(shù)據(jù)項，導致該葉子節(jié)點數(shù)據(jù)超出5婿斥，所以需要分裂其父節(jié)點成為兩個葉子
再插入 40 數(shù)據(jù)項劝篷，引起樹葉被分裂成兩片然后又造成父結(jié)點的分裂
從B樹中刪除 99 數(shù)據(jù)項導致葉子節(jié)點的數(shù)據(jù)少于3從而合并葉子采转，而父節(jié)點也少于3從而再一次合并
標準庫（SLT）中的set和map
set
set是一個排序后的容器徒河，不允許重復。set特有的操作是高效的插入衡创、刪除和執(zhí)行基本查找勘高。set也允許使用iterator來遍歷峡蟋。
set的方法
- 與
vector和list相同的方法-
iterator begin()：返回容器開始的迭代器 -
iterator end()：返回容器結(jié)尾處的迭代器 -
int size() const：返回容器內(nèi)的元素個數(shù) -
bool empty()：如果容器沒有元素坟桅，返回true华望，否則返回false
-
- 特有的插入操作，
set使用insert進行插入操作仅乓，由于非重復性赖舟，導致插入有可能會失敗，insert操作返回一個iterator指明插入新項的位置或者失敗時已有的項的位置.夸楣。pair是一個類模板宾抓，并且提供兩個成員 first 和 second 用來訪問返回值的兩項成員-
pair<iterator, bool> insert( const Object & x);：插入Object x -
pair<iterator, bool> insert( iterator hint, const Object & x);：在指定索引hint處插入Object x，比單參數(shù)的插入快得多豫喧，通常為O(1)
-
-
erase刪除操作-
int erase( const Object & x);：刪除x石洗，如果找到的話，返回刪除元素的個數(shù)紧显，顯然只能返回0或者1 -
iterator erase( iterator itr);：刪除有iterator指定的位置的對象 -
iterator erase( iterator start, iterator end);：刪除由兩個iterator指定的位置對象中間包含的所有元素讲衫，包含前不包含后
-
-
find查找操作-
iterator find( const Object & x) const;：查找x返回其位置
-
map
map用來存儲排序后的由鍵和值組成的項的集合，鍵必須唯一孵班，但是多個鍵可以同時對應一個值涉兽，即值不需要唯一招驴，鍵保持邏輯排序后的順序
map的方法
map的方法和set很像，但是其返回值是一個鍵-值對： pair<KeyType, ValueType>枷畏，map支持 begin别厘、end、size拥诡、enmty触趴、insert、find袋倔、erase雕蔽、find
-
insert操作必須提供pair<KeyType, ValueType>對象 -
find僅需要一個鍵，但是返回值的iterator還是指向一個pair<KeyType, ValueType>對象宾娜，并可以用first訪問返回的鍵批狐，使用second訪問返回的值
map還重載了數(shù)組索引的操作符 []：
ValueType & operator[] ( const KeyType & key );
如果map中存在key就返回只想相應值的引用，如果不存在key就在map中插入一個默認的值前塔，然后返回指向這個插入的默認值的引用
轉(zhuǎn)載請注明出處嚣艇，本文永久更新鏈接：https://blogs.littlegenius.xin/2019/08/19/【數(shù)據(jù)結(jié)構】三樹/
