树
树是一种数据结构，它是由n个有限节点组成一个具有层次关系的集合
-
树的特点：
每个节点有零个或多个子节点
没有父节点的节点称为根节点
每一个非根节点有且只有一个父节点
除了根节点外，每个子节点可以分为多个不相交的子树
二叉树
概念
-
二叉树是树的特殊一种，具有如下特点：
每个结点最多有两颗子树，结点的度最大为2
左子树和右子树是有顺序的，次序不能颠倒
即使某结点只有一个子树，也要区分左右子树
二叉树是一种有用的折中方案，既有链表的好处，也有数组的好处
添加，删除元素都很快，并且在查找方面也有很多的算法优化
代码示例：
class TreeNode{
public $value = null;
public $right = null;
public $left = null;
function __construct($value) {
$this->value = $value;
}
}
二叉树遍历算法：
前置遍历（根——>左——>右）
function preTraverse(TreeNode $node) {
if(!$node) {
return;
}
$this->visit($node->value);
$this->preTraverse($node->left);
$this->preTraverse($node->right);
}
中区遍历（左——>根——>右）
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);
}
}
}
满二叉树
高度为h，由2^h-1个节点构成的二叉树称为满二叉树
完全二叉树
完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。注：左右两边没有大小关系。
堆一般都是用完全二叉树来实现的
二叉查找树
没有键值相等的节点
若左子树不为空，左子树上节点值均小于根节点的值
若右子树不为空，右子树上节点值均大于根节点的值
二叉查找树查找算法
-
步骤：
1、若根结点的关键字值等于查找的关键字，成功。
2、否则，若小于根结点的关键字值，递归查左子树。
3、若大于根结点的关键字值，递归查右子树。
4、若子树为空，查找不成功。
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;
}
二叉查找树插入算法
-
步骤：
1、首先执行查找算法，找出被插结点的父亲结点。
2、判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
3、若二叉树为空。则首先单独生成根结点。
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;
}
}
}
平衡二叉树
它的左右两个子树的高度差的绝对值不超过1
并且左右两个子树都是一棵平衡二叉树
平衡二叉查找树
- 既是一颗二叉查找树又是一颗平衡二叉树
B树
平衡的多叉树
根节点至少有两个子节点（可以多个）
每个节点有M-1个key，并且以升序排列
位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
其它节点至少有M/2个子节点
所有的叶子结点都位于同一层
B+树
与B树的区别：
-
B树每个节点都存储key和data，所有节点组成这棵树，并且叶子节点指针为null。
B Tree
-
B+树只有叶子节点存储data，非叶子节点存储指针，叶子节点包含了这棵树的所有键值，叶子节点不存储指针。
B+Tree
-
应用场景：mysql索引
为什么mysql用B+树：B+树的非叶子节点存储的是指针，相对与B树更小，如果把所有同一内部节点的关键字存放在同一盘块中（分页存储），那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，查询效率更高；
红黑树
-
图示：
红黑树
- 一种自平衡二叉查找树
- 节点是红色或黑色
- 根节点是黑色
- 每个红色节点的两个子节点都是黑色
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
- 三种操作：左旋、右旋和变色
- 使用场景：java中的TreeSet,TreeMap，广泛用在C++的STL中。如map和set都是用红黑树实现的
字典树
-
图示
字典树
- 用于统计，排序和保存大量的字符串，经常被搜索引擎系统用于文本词频统计
- 利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高
- 应用场景：搜索引擎，用在统计和排序大量字符串，如自动机
