前言
最近在幫公司校招~~ 所以來(lái)整理一些數(shù)據(jù)結(jié)構(gòu)方面的知識(shí)，這些知識(shí)呢，光看一遍理解還是很淺的，看過(guò)跟動(dòng)手做過(guò)一遍的同學(xué)還是很容易分辨的喲~
一直覺(jué)得數(shù)據(jù)結(jié)構(gòu)跟算法，就好比金庸小說(shuō)里的《九陽(yáng)神功》，學(xué)會(huì)九陽(yáng)神功后，有了內(nèi)功基礎(chǔ)，再去學(xué)習(xí)其他武功，速度就有質(zhì)的提升
內(nèi)容大概包含這些，會(huì)分多篇文章來(lái)整理：
- 二叉搜索樹
- 平衡二叉樹（AVL）
- 二叉堆
- 堆排序
- 四叉樹
- 八叉樹
- 圖，深度優(yōu)先DFS、廣度優(yōu)先BFS
- 最短路徑
二叉樹
二叉樹，也就是每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子的樹。多用于搜索，查找，還有可以用來(lái)求最短編碼的哈弗曼樹，也稱為最優(yōu)二叉樹。
二叉排序/搜索樹
如圖，樹的每個(gè)有孩子的節(jié)點(diǎn)都滿足：左節(jié)點(diǎn)的值<根節(jié)點(diǎn)的值<右節(jié)點(diǎn)的值條件的樹，稱為二叉排序樹，也叫二叉搜索樹。
如果對(duì)這個(gè)樹進(jìn)行中序遍歷，就能得到一個(gè)排序的數(shù)列，非常簡(jiǎn)單，下面貼出插入操作跟遍歷的代碼
插入操作
public void Add(BinaryTree node)
{
if (node.Value < Value)
{
if (this.Left != null)
{
this.Left.Add(node);
}
else
{
this.Left = node;
}
}
else
{
if (this.Right != null)
{
this.Right.Add(node);
}
else
{
this.Right = node;
}
}
}
中序遍歷輸出排序列表
public void InOrder(List<int> list)
{
if (Left != null)
{
Left.InOrder(list);
}
list.Add(this.Value);
if (Right != null)
{
Right.InOrder(list);
}
}
但是二叉排序樹極端的情況，效率會(huì)變成鏈表線性結(jié)構(gòu)，這樣查找起來(lái)時(shí)間復(fù)雜度會(huì)變成O(n)，就失去了樹形結(jié)構(gòu)的意義，如圖：
這時(shí)就要引出我們的另外一種二叉樹樹結(jié)構(gòu)了
平衡二叉樹
平衡二叉樹（AVL）簡(jiǎn)單來(lái)說(shuō)就是插入的時(shí)候，要保證子節(jié)點(diǎn)的平衡，別老往一邊一直插入下去，那樣又成了鏈表效率了
首先來(lái)搞懂這個(gè)幾個(gè)定義
平衡因子：即左子樹的高度減去右子樹的高度
平衡二叉樹上所有節(jié)點(diǎn)的平衡因子都必須為：-1、0和1。否則該二叉樹就不是平衡二叉樹
如下圖，圖左邊是一顆平衡二叉樹，圖右根節(jié)點(diǎn)平衡因子為-2，則不是平衡二叉樹
如何保持樹的平衡
每當(dāng)插入一個(gè)節(jié)點(diǎn)的時(shí)候，都檢查這次插入是否會(huì)破壞平衡性，若是，則找出最小不平衡子樹，在保持二叉排序樹的前提下，進(jìn)行相應(yīng)旋轉(zhuǎn)，使之成為新的平衡子樹。
通常會(huì)有四種旋轉(zhuǎn)情況：
單向右旋平衡處理
也有地方稱為L(zhǎng)eft Left旋轉(zhuǎn)，是不是覺(jué)得很奇怪，一下左，一下右邊的，它估計(jì)是想把你轉(zhuǎn)暈，好套出你的花唄密碼。
那么到底是什么意思呢，請(qǐng)看下圖
這棵樹有三個(gè)節(jié)點(diǎn)：6，4，2
我們把節(jié)點(diǎn)2當(dāng)成是最新插入進(jìn)來(lái)的節(jié)點(diǎn)，由于這個(gè)節(jié)點(diǎn)2的插入，導(dǎo)致節(jié)點(diǎn)6的平衡因子變成了2，不符合-1、0、1的規(guī)定，破壞了平衡性，所以我們需要對(duì)節(jié)點(diǎn)6進(jìn)行右旋轉(zhuǎn)，而節(jié)點(diǎn)2又是節(jié)點(diǎn)6的Left節(jié)點(diǎn)的Left節(jié)點(diǎn)，所以也稱為L(zhǎng)L旋轉(zhuǎn)。
右旋操作
也就是如果結(jié)點(diǎn)6的左孩子節(jié)點(diǎn)4有右孩子，則將節(jié)點(diǎn)4的右孩子變成節(jié)點(diǎn)6的左孩子，最后將節(jié)點(diǎn)6變成節(jié)點(diǎn)4的右孩子
單向左旋平衡處理
左旋平衡處理也叫RR旋轉(zhuǎn)，是LL的鏡像操作
雙向旋轉(zhuǎn)（先右后左）平衡處理 (Right Left)
為什么會(huì)有這種情況出現(xiàn)呢，因?yàn)槲覀兊钠胶鈽?，首先也是一顆二叉排序樹，必須滿足左節(jié)點(diǎn)<根節(jié)點(diǎn)<右節(jié)點(diǎn)的插入規(guī)則。
所以如下圖，節(jié)點(diǎn)4插入導(dǎo)致樹失去平衡，單向旋轉(zhuǎn)已經(jīng)不能滿足要求了，需要先讓節(jié)點(diǎn)6右旋，然后再把節(jié)點(diǎn)2左旋
雙向旋轉(zhuǎn)（先左后右）平衡處理 (Left Right)
同理，是RL的鏡像操作
代碼實(shí)現(xiàn)
//右旋轉(zhuǎn)
public BinaryTree RightRotate(BinaryTree root)
{
BinaryTree lchild = root.Left;
root.Left = lchild.Right;
lchild.Right = root;
return lchild;
}
//左旋轉(zhuǎn)
public BinaryTree LeftRotate(BinaryTree root)
{
BinaryTree rchild = root.Right;
root.Right = rchild.Left;
rchild.Left = root;
return rchild;
}
//先左后右旋轉(zhuǎn)
public BinaryTree LeftRightRotate(BinaryTree root)
{
root.Left = root.Left.LeftRotate(root);
return RightRotate(root);
}
//先右后左旋轉(zhuǎn)
public BinaryTree RightLeftRotate(BinaryTree root)
{
root.Right = root.Right.RightRotate(root);
return LeftRotate(root);
}
//計(jì)算平衡因子，取絕對(duì)值
public int Balance(BinaryTree root)
{
int val = 0;
if (root.Left != null) val += Height(root.Left);
if (root.Right != null) val -= Height(root.Right);
return Math.Abs(val);
}
//計(jì)算樹的高度
public int Height(BinaryTree root)
{
int leftHeight = 0;
int rightHeight = 0;
if (root != null && root.Left != null)
{
leftHeight += Height(root.Left);
}
if (root != null && root.Right != null)
{
rightHeight += Height(root.Right);
}
return rightHeight > leftHeight ? ++rightHeight : ++leftHeight;
}
插入操作
public BinaryTree Inster(BinaryTree root, int key)
{
if (root == null)
{
root = new BinaryTree(key);
}
else if (key < root.Value)//插入到左邊
{
root.Left = Inster(root.Left, key);
if (Balance(root) > 1)//插入左節(jié)點(diǎn)導(dǎo)致樹失衡了
{
if (key < root.Left.Value)//LL處理，右旋
{
root = RightRotate(root);
}
else
{
root = LeftRightRotate(root);//LR處理，先左后右
}
}
}
else
{
root.Right = Inster(root.Right, key);
if (Balance(root) > 1)//插入右節(jié)點(diǎn)導(dǎo)致失衡
{
if (key > root.Right.Value)//RR處理， 左旋
{
root = LeftRotate(root);
}
else
{
root = RightLeftRotate(root);//RL處理，先右后左
}
}
}
return root;
}
使用平衡二叉樹后，查詢起來(lái)時(shí)間復(fù)雜度就從O(n)變?yōu)榱薕( log n)。
總結(jié)
平衡二叉樹的優(yōu)點(diǎn)在于因?yàn)闃浣Y(jié)構(gòu)維護(hù)的較好，所以搜索查詢速度很快，但在插入，刪除的時(shí)候，為了保持樹的平衡會(huì)做一次或多次旋轉(zhuǎn)。
適合用于插入刪除操作少，而搜索操作很多的情況。
為了減少插入，刪除在旋轉(zhuǎn)方面的消耗，另一種自平衡樹結(jié)構(gòu)出現(xiàn)了
它就是：紅黑樹
紅黑樹不追求"完全平衡"，即不像AVL那樣要求節(jié)點(diǎn)的 |平衡因子| <= 1，它只要求部分達(dá)到平衡，但是提出了為節(jié)點(diǎn)增加顏色，紅黑是用非嚴(yán)格的平衡來(lái)?yè)Q取增刪節(jié)點(diǎn)時(shí)候旋轉(zhuǎn)次數(shù)的降低，任何不平衡都會(huì)在三次旋轉(zhuǎn)之內(nèi)解決，而AVL是嚴(yán)格平衡樹，因此在增加或者刪除節(jié)點(diǎn)的時(shí)候，根據(jù)不同情況，旋轉(zhuǎn)的次數(shù)比紅黑樹要多。
學(xué)會(huì)了AVL在去看紅黑樹也就很簡(jiǎn)單了~~
參考
https://www.cnblogs.com/sench/p/7786718.html
https://baijiahao.baidu.com/s?id=1577200621749785094&wfr=spider&for=pc
