数据结构之树_数据结构树叶

1、满二叉树

除叶子节点外，每个节点都有两个子节点，除了最后一层，每一层上的节点数达到最大值，第K层有2(k-1)个子节点，高度为m的满二叉树总共有2m-1个子节点（注意k和m为指数）

2、完全二叉树

除最后一层（或两层）外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点

3、排序（搜索）二叉树

二叉搜索树借鉴了二分查找的思想，在构造树过程中保持节点按key“有序”

（1）定义：设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么会有y.key<=x.key；如果y是x右子树中的一个节点，那么有y.key>=x.key
（2）时间复杂度：若假设树的高度是h，那么查找过程的时间复杂度就是O(h)=O(N)

4、平衡二叉树

（1）与二叉搜索树区别：平衡二叉树是对二叉搜索树(又称为二叉排序树)的一种改进。二叉搜索树有一个缺点就是，树的结构是无法预料的，随意性很大，它只与节点的值和插入的顺序有关系，往往得到的是一个不平衡的二叉树
（2）定义
可以是空树
假如不是空树，任何一个结点左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1
（3）平衡二叉树数据结构
数据项 / 左子树 / 右子树 / 平衡因子（平衡因子的取值只可能为0,1,-1）
（4）失衡与处理：
失衡调整：在插入节点的时候，如果插入节点之后有一个节点的平衡因子要大于2或者小于-2的时候，就需要对其进行调整
调整方式：平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现

（5）查找时间复杂度：O(h) = O(logN)

5、红黑树

每个节点使用一个bit用于保存当前节点的颜色
（1） 每个节点要么是红色，要么是黑色
（2） 根节点是黑色
（3） 每个叶子节点（NIL）是黑色
（4） 如果一个节点是红色，则它的子节点必须是黑色的
（5） 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点
红黑树是相对平衡的二叉树：确保没有一条路径会比其它路径长出两倍
红黑树应用：主要用于存储有序的数据，时间复杂度是O(logn)，例如Java中的TreeSet、TreeMap（默认按Key升序排列）等
红黑树是一种特殊的平衡二叉树

6、BTree

BTree是为了磁盘或其它存储设备而设计的一种多叉平衡查找树
一个节点由若干个Key及若干个指针构成，每个节点内Key是有序的，方便二分查找

7、B-Tree和B+Tree

B-Tree一般是数据库索引所采用的数据结构
每个非叶子节点均有N（N>2）个子节点，每个叶子节点的深度都一样
每个节点的数据结构是一样的，每个节点在构造时申请同等大小的空间，具体实现中，每个节点对应磁盘上的一页，每个节点读取只需要一次IO

为什么选择B-Tree：一个节点大小为一页，磁盘预读性原理，尽量减少磁盘IO
B-Tree的性质：假设索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，搜索时间复杂度为logdN

B-Tree和B+Tree区别：
非叶节点是否存放数据引用，即叶子节点和非叶节点的数据结构不完全相同
非叶节点不存储数据引用的情况下，反而可以存储更多key，因此节点出度d更大，树高度更小，查询性能更好

改进的B+Tree
叶节点之间增加顺序访问指针，以支持区间访问

8、MySQL中MyISAM和InnoDB两种存储引擎索引实现

在MySQL中，二者均采用B+Tree作为索引数据结构

MyISAM索引实现：使用B+Tree，叶子节点Data域存放实际数据的地址，该实现中，Key的顺序与实际数据的存储顺序没有必然联系，属于非聚集索引。同时辅助索引与主索引也没有明显差别，只是主索引要求key不能重复，辅助索引允许key重复

InnoDB索引实现：使用B+Tree，叶子节点Data域存放实际数据记录，该实现中，Key的顺序决定了实际数据的物理存储顺序，属于聚集索引。辅助索引是建立在主索引基础上，具体来说，辅助索引的叶子节点Data域存放的是主索引Key，因此通过辅助索引查询时，先根据【辅助索引】查询出【主索引Key】，然后再根据主索引定位到实际数据，相当于经过了【两次】索引查询

聚簇索引和非聚簇索引的区别
Key的顺序与实际数据的存储顺序是否有联系