樹(shù)
樹(shù)是一種數(shù)據(jù)結(jié)構(gòu)认境，它是由n個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合
-
樹(shù)的特點(diǎn)：
每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)
沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱(chēng)為根節(jié)點(diǎn)
每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)
除了根節(jié)點(diǎn)外鞭盟，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹(shù)
二叉樹(shù)
概念
-
二叉樹(shù)是樹(shù)的特殊一種减细，具有如下特點(diǎn)：
每個(gè)結(jié)點(diǎn)最多有兩顆子樹(shù)单寂，結(jié)點(diǎn)的度最大為2
左子樹(shù)和右子樹(shù)是有順序的，次序不能顛倒
即使某結(jié)點(diǎn)只有一個(gè)子樹(shù)，也要區(qū)分左右子樹(shù)
二叉樹(shù)是一種有用的折中方案，既有鏈表的好處雀扶，也有數(shù)組的好處
添加，刪除元素都很快肆汹，并且在查找方面也有很多的算法優(yōu)化
代碼示例：
class TreeNode{
public $value = null;
public $right = null;
public $left = null;
function __construct($value) {
$this->value = $value;
}
}
二叉樹(shù)遍歷算法：
前置遍歷（根——>左——>右）
function preTraverse(TreeNode $node) {
if(!$node) {
return;
}
$this->visit($node->value);
$this->preTraverse($node->left);
$this->preTraverse($node->right);
}
中區(qū)遍歷（左——>根——>右）
function midTraverse(TreeNode $node) {
if(!$node) {
return;
}
$this->midTraverse($node->left);
$this->visit($node->value);
$this->midTraverse($node->right);
}
后置遍歷（左——>右——>根）
function sufTraverse(TreeNode $node) {
if(!$node) {
return;
}
$this->sufTraverse($node->left);
$this->sufTraverse($node->right);
$this->visit($node->value);
}
層次遍歷
function levelTraverse(TreeNode $node) {
$queue = [$node];
while (!empty($queue)) {
$temp = array_pop($queue);
$this->visit($temp);
if($temp->left) {
array_push($queue, $temp->left);
}
if($temp->right) {
array_push($queue, $temp->right);
}
}
}
滿二叉樹(shù)
高度為h愚墓，由2^h-1個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹(shù)稱(chēng)為滿二叉樹(shù)
完全二叉樹(shù)
完全二叉樹(shù)是由滿二叉樹(shù)而引出來(lái)的，若設(shè)二叉樹(shù)的深度為h昂勉，除第 h 層外浪册，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)(即1~h-1層為一個(gè)滿二叉樹(shù))，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊岗照，這就是完全二叉樹(shù)村象。注：左右兩邊沒(méi)有大小關(guān)系。
堆一般都是用完全二叉樹(shù)來(lái)實(shí)現(xiàn)的
二叉查找樹(shù)
沒(méi)有鍵值相等的節(jié)點(diǎn)
若左子樹(shù)不為空攒至，左子樹(shù)上節(jié)點(diǎn)值均小于根節(jié)點(diǎn)的值
若右子樹(shù)不為空厚者，右子樹(shù)上節(jié)點(diǎn)值均大于根節(jié)點(diǎn)的值
二叉查找樹(shù)查找算法
-
步驟：
1、若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字迫吐，成功库菲。
2、否則志膀，若小于根結(jié)點(diǎn)的關(guān)鍵字值熙宇，遞歸查左子樹(shù)鳖擒。
3、若大于根結(jié)點(diǎn)的關(guān)鍵字值烫止，遞歸查右子樹(shù)蒋荚。
4、若子樹(shù)為空馆蠕，查找不成功期升。
public function find(int $data) {
$p = $this->tree;
while ($p) {
if ($data < $p->data) {
$p = $p->left;
} elseif ($data > $p->data) {
$p = $p->right;
} else {
return $p;
}
}
return null;
}
二叉查找樹(shù)插入算法
-
步驟：
1、首先執(zhí)行查找算法荆几，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)吓妆。
2、判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左吨铸、右兒子行拢。將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。
3诞吱、若二叉樹(shù)為空舟奠。則首先單獨(dú)生成根結(jié)點(diǎn)。
public function insert(int $data) {
if (!$this->tree) {
$this->tree = new TreeNode($data);
return true;
}
$p = $this->tree;
while ($p) {
if ($data < $p->data) {
if(!$p->left){
$p->left = new TreeNode($data);
return true;
}
$p = $p->left;
} elseif ($data > $p->data) {
if(!$p->right){
$p->right = new TreeNode($data);
return true;
}
$p = $p->right;
} else {
return false;
}
}
}
平衡二叉樹(shù)
它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1
并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)
平衡二叉查找樹(shù)
- 既是一顆二叉查找樹(shù)又是一顆平衡二叉樹(shù)
B樹(shù)
平衡的多叉樹(shù)
根節(jié)點(diǎn)至少有兩個(gè)子節(jié)點(diǎn)（可以多個(gè)）
每個(gè)節(jié)點(diǎn)有M-1個(gè)key房维，并且以升序排列
位于M-1和M key的子節(jié)點(diǎn)的值位于M-1 和M key對(duì)應(yīng)的Value之間
其它節(jié)點(diǎn)至少有M/2個(gè)子節(jié)點(diǎn)
所有的葉子結(jié)點(diǎn)都位于同一層
B+樹(shù)
與B樹(shù)的區(qū)別：
-
B樹(shù)每個(gè)節(jié)點(diǎn)都存儲(chǔ)key和data沼瘫，所有節(jié)點(diǎn)組成這棵樹(shù)，并且葉子節(jié)點(diǎn)指針為null咙俩。
B Tree
-
B+樹(shù)只有葉子節(jié)點(diǎn)存儲(chǔ)data耿戚，非葉子節(jié)點(diǎn)存儲(chǔ)指針，葉子節(jié)點(diǎn)包含了這棵樹(shù)的所有鍵值阿趁，葉子節(jié)點(diǎn)不存儲(chǔ)指針膜蛔。
B+Tree
-
應(yīng)用場(chǎng)景：mysql索引
為什么mysql用B+樹(shù)：B+樹(shù)的非葉子節(jié)點(diǎn)存儲(chǔ)的是指針，相對(duì)與B樹(shù)更小脖阵，如果把所有同一內(nèi)部節(jié)點(diǎn)的關(guān)鍵字存放在同一盤(pán)塊中（分頁(yè)存儲(chǔ)）皂股，那么盤(pán)塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多，一次性讀入內(nèi)存的需要查找的關(guān)鍵字也就越多命黔，查詢效率更高呜呐；
紅黑樹(shù)
-
圖示：
紅黑樹(shù)
- 一種自平衡二叉查找樹(shù)
- 節(jié)點(diǎn)是紅色或黑色
- 根節(jié)點(diǎn)是黑色
- 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色
- 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)
- 三種操作：左旋、右旋和變色
- 使用場(chǎng)景：java中的TreeSet,TreeMap悍募，廣泛用在C++的STL中蘑辑。如map和set都是用紅黑樹(shù)實(shí)現(xiàn)的
字典樹(shù)
-
圖示
字典樹(shù)
- 用于統(tǒng)計(jì)，排序和保存大量的字符串坠宴，經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)
- 利用字符串的公共前綴來(lái)減少查詢時(shí)間以躯，最大限度地減少無(wú)謂的字符串比較，查詢效率比哈希樹(shù)高
- 應(yīng)用場(chǎng)景：搜索引擎，用在統(tǒng)計(jì)和排序大量字符串忧设，如自動(dòng)機(jī)
