[TOC]
说明：以下文字来源《大话数据结构》 作者：程杰。
好文推荐：https://www.cnblogs.com/skywang12345/p/3576328.html
视频推荐：https://www.bilibili.com/video/BV1tE411f7tP?from=search&seid=9664635478433438112
概述
之前我们一直谈的是一对一的线性结构，可现实中，还有很多一对多的情况需要处理，所以我们需要研究这种一对多的数据结构—-“树”。
树是n( n>= 0) 个结点的有限集。n = 0时称为空树。在任意一颗非空树中，有且只有一个特定的称为根(Root)的结点。当n > 1 时，某余结点可分为m ( m > 0) 个 互不相交的有限集 T1, T2, T3….Tm , 其中每一个集合本身又是一课树，并且称为根的子树。
需要注意，子树和子树是不能相交的，下面的属于不是树形结构。
结点分类
结点关系
结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。因为对于结点来说其父母同体，唯一的一个。
同一个双亲的孩子之间互称为兄弟。
树的其他相关概念
如果将树中结点的各子树看成从左到右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
森林是M ( m >= 0) 课互不相交的树的集合。
线性表结构和树结构对比
线性结构
- 第一个数据元素：无前驱。
- 最后一个数据元素：无后续。
- 中间元素：一个前驱一个后续。
树结构
- 根结点：无双亲，唯一。
- 叶结点：无孩子，可以多。
- 中间节结点：一个双亲多个孩子。
存储结构
充分利用顺序存储和链式存储结构的特点，完全可以实现对树的存储结构进行表示。介绍三种常见的不同表示方法：
1. 双亲表示法
我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。也就是说，每个结点除了知道自己是谁以外，还知道双亲在哪里。
这也意味着，我们所有的结点都存有它双亲的位置。
但是如上面的存储，如果要知道孩子的结点是什么，我们就要遍历整个结构才行。
存储结构的设计是一个非常灵活的过程，一个存储结构设计得是否合理，取决于基于该存储结构的运算是否合适，是否方便，时间复杂度好不好等。如下，我们在设计的时候加入
记录长子节点下标
记录右兄弟下标
灵活记录指针域，以便于抽象成自己理解的树形结构。
2. 孩子表示法
具体办法是，把每个结点的孩子结点排列起来，以单链表作存储结构，则n个节点有n个孩子链表，如果是叶子节点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中，如图：
这样的结构对于我们要查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。对于遍历整颗树也是很方便的，对头结点的数组循环即可。
如果需要查找他的双亲，在指针域中加入双全就好了，如下：
3. 孩子兄弟表示法
任意一颗树，他的结点的第一个孩子如果存在就是唯一的，他的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。对应上面的书这个表示法如图：
二叉树
二叉树是n ( n >= 0 )个结点的有限集合，该集合或者为空集 (称为空二叉树 )，或者由一个根结点和两颗互不相交的，分别称为根结点的左子树和右子树的二叉树组成。
特点
- 每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一颗子树都是可以的。
- 左子树和右子树是有顺序的，次序不能任意颠倒。就像人是双手，双脚，但显然左手，左脚和右手，右脚是不一样的。
- 即使树中某结点只有一颗树，也要区分它是左子树还是右子树。
五种型态
- 空二叉树
- 只有一个根结点
- 根结点只有左子树
- 根结点只有右子树
- 根结点既有左子树又有右子树
二叉树查询出来的结果的复杂度就是这个树的深度
二叉树的性质
查看文章：https://www.cnblogs.com/skywang12345/p/3576328.html
存储结构
顺序存储结构
二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系。
完全二叉树的顺序存储结构
一般二叉树的顺序存储结构
如上图，这样的形式的顺序结构只能适合完全二叉树，不然对内存的浪费是很大的。
二叉链表
二叉树的每个结点最多有两个孩子，所以为他设计一个数据域和两个指针域是比较自然的，我们称这样的链表为二叉链表，结点的结构图如下：
其中data是数据域，lchild 和 rchild都是指针域，分别存放指向左孩子和右孩子的指针：
如上，如果我们需要， 还可以增加一个指向其双亲的指针域，那样的我就称之为三叉链表。
平衡二叉树
转载地址：https://zhuanlan.zhihu.com/p/27700617
概念
平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构；
特点
平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度；平衡二叉树的数据结构组装过程有以下规则
-
非叶子节点只能允许最多两个子节点存在。
-
每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的，比如hash值)；
平衡树的层级结构
因为平衡二叉树查询性能和树的层级（h高度）成反比，h值越小查询越快、为了保证树的结构左右两端数据大致平衡降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡，实现了这种算法的有比如Treap、红黑树，使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于1.，通过这样避免树形结构由于删除增加变成线性链表影响查询效率，保证数据平衡的情况下查找数据的速度近于二分法查找；
总结平衡二叉树特点
（1）非叶子节点最多拥有两个子节点；
（2）非叶子节值大于左边子节点、小于右边子节点；
（3）树的左右两边的层级数相差不会大于1;
（4）没有值相等重复的节点;
B树(B-tree)
概念
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构，让我们来看看他有什么特点;
规则
1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
2）子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；
3）关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
4）所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;
最后我们用一个图和一个实际的例子来理解B树（这里为了理解方便我就直接用实际字母的大小来排列C>B>A）
B树的查询流程
如上图我要从上图中找到E字母，查找流程如下
1）获取根节点的关键字进行比较，当前根节点关键字为M，E<M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；
2）拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；
3）拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；
B树的插入节点流程
定义一个5阶树（平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;
遵循规则：
1）节点拆分规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须<=5-1（这里关键字数>4就要进行节点拆分）；
2）排序规则：满足节点本身比左边节点大，比右边节点小的排序规则;
先插入 3、8、31、11
再插入23、29
再插入50、28
B树节点的删除
规则：
1）节点合并规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于ceil（5/2）（这里关键字数<2就要进行节点合并）；
2）满足节点本身比左边节点大，比右边节点小的排序规则;
3）关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；
特点
B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度;
B+树
概念
B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别
规则(B+ VS B树)
1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
4）非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料 这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）;
（百度百科算法结构示意图）
（维基百科算法结构示意图）
特点
1、B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快
2、B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
3、B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
4、B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。
红黑树
好文推荐：https://segmentfault.com/a/1190000012728513
一种高效的查找算法。
nil 节点就是空节点，在红黑树的实现中，nil 节点代替二叉树中的 NULL：叶子节点的左节点和右节点指针都指向 nil 节点；只一个子树的节点，其另外一个子节点指针也指向 nil 节点；根节点的父节点也指向 nil 节点。nil节点的父节点和右节点都是自己，左节点为红黑树的根节点。如果红黑树为空（没有根节点），那么nil节点的左节点就也是自己。nil节点的存在大大方便了很多操作。
总结
1、相同思想和策略
从平衡二叉树、B树、B+树、B*树总体来看它们的贯彻的思想是相同的，都是采用二分法和数据平衡策略来提升查找数据的速度；
2、不同的方式的磁盘空间利用
不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变，每一次演变都是为了让节点的空间更合理的运用起来，从而使树的层级减少达到快速查找数据的目的；
二叉查询法
转载：https://blog.csdn.net/lcore/article/details/8889176
package com.kiritor;
/**
* Java实现二叉查找树
* @author Kiritor
* @param <T>*/
public class BinarySearchTree<T extends Comparable<? super T>> {
/**结点数据结构*/
static class BinaryNode<T>
{
T data;
BinaryNode<T> left;
BinaryNode<T> right;
public BinaryNode(T data) {
this(data,null,null);
}
public BinaryNode( T data, BinaryNode<T> left, BinaryNode<T> right) {
this.data =data;
this.left = left;
this.right =right;
}
public BinaryNode()
{
data =null;
this.left = left;
this.right =right;
}
}
private BinaryNode<T> rootTree;
/**构造一颗空的二叉查找树*/
public BinarySearchTree()
{
rootTree = null;
}
/**清空二叉查找树*/
public void clear()
{
rootTree = null;
}
/**判断是否为空*/
public boolean isEmpty()
{
return rootTree == null;
}
/**查找指定的元素,默认从
* 根结点出开始查询*/
public boolean contains(T t)
{
return contains(t, rootTree);
}
/**找到二叉查找树中的最小值*/
public T findMin()
{
if(isEmpty())
{
System.out.println("二叉树为空");
return null;
}else
return findMin(rootTree).data;
}
/**找到二叉查找树中的最大值*/
public T findMax()
{
if(isEmpty())
{
System.out.println("二叉树为空");
return null;
}else
return findMax(rootTree).data;
}
/**插入元素*/
public void insert(T t)
{
rootTree = insert(t, rootTree);
}
/**删除元素*/
public void remove(T t)
{
rootTree = remove(t,rootTree);
}
/**打印二叉查找树*/
public void printTree()
{
}
/**从某个结点出开始查找元素*/
public boolean contains(T t, BinaryNode<T> node)
{
if(node==null)
return false;
int result = t.compareTo(node.data);
if(result>0)
return contains(t,node.right);
else if(result<0)
return contains(t, node.left);
else
return true;
}
/**查询出最小元素所在的结点*/
public BinaryNode<T> findMin(BinaryNode<T> node)
{
if(node==null)
return null;
else if(node.left==null)
return node;
return findMin(node.left);//递归查找
}
/**查询出最大元素所在的结点*/
public BinaryNode<T> findMax(BinaryNode<T> node)
{
if(node!=null)
{
while(node.right!=null)
node=node.right;
}
return node;
}
/**在某个位置开始判断插入元素*/
public BinaryNode<T> insert(T t,BinaryNode<T> node)
{
if(node==null)
{
//新构造一个二叉查找树
return new BinaryNode<T>(t, null, null);
}
int result = t.compareTo(node.data);
if(result<0)
node.left= insert(t,node.left);
else if(result>0)
node.right= insert(t,node.right);
else
;//doNothing
return node;
}
/**在某个位置开始判断删除某个结点*/
public BinaryNode<T> remove(T t,BinaryNode<T> node)
{
if(node == null)
return node;//没有找到,doNothing
int result = t.compareTo(node.data);
if(result>0)
node.right = remove(t,node.right);
else if(result<0)
node.left = remove(t,node.left);
else if(node.left!=null&&node.right!=null)
{
node.data = findMin(node.right).data;
node.right = remove(node.data,node.right);
}
else
node = (node.left!=null)?node.left:node.right;
return node;
}
public BinaryNode<Integer> init()
{
BinaryNode<Integer> node3 = new BinaryNode<Integer>(3);
BinaryNode<Integer> node1 = new BinaryNode<Integer>(1);
BinaryNode<Integer> node4 = new BinaryNode<Integer>(4,node3,null);
BinaryNode<Integer> node2 = new BinaryNode<Integer>(2,node1,node4);
BinaryNode<Integer> node8 = new BinaryNode<Integer>(8);
BinaryNode<Integer> root = new BinaryNode<Integer>(6,node2,node8);
return root;
}
public void preOrder(BinaryNode node) {
if (node != null) {
System.out.print(node.data);
preOrder(node.left);
preOrder(node.right);
}
}
/*简单测试*/
public static void main(String[] args) {
BinarySearchTree searchTree = new BinarySearchTree<>();
BinaryNode<Integer> node= searchTree.init();
searchTree.rootTree=node;
searchTree.preOrder(searchTree.rootTree);
searchTree.remove(4);
searchTree.preOrder(searchTree.rootTree);
}
}
「真诚赞赏，手留余香」
真诚赞赏，手留余香
使用微信扫描二维码完成支付
