《数据结构 - 二叉树》

一：什么是二叉树？

　　- 概念

　　　　- 是 n (n > 0) 个结点的有限结合，该集合或者为空集。

　　　　- 或者由一个根节点和两颗互不相交的分别称为根结点的左子树和右子树的二叉树组成。

　　- 定义
　　　　- 每个节点最多两颗子树，所以二叉树中不存在 度 大于 2 的结点。（没有子树/一个子树也是可以的）

　　　　- 左子树和右子树 是有顺序的，不能颠倒。

　　　　- 即使树中某结点只有一棵子树，也需要区分是左子树还是右子树。

　　- 性质

　　　　- 在 二叉树 的 第 i 层上至多有 2（i-1）个结点。

　　　　- 在 深度 为 k 的二叉树至多有 2（k)-1 个结点。

二：什么是空二叉树？

　　- 定义

　　　　- 结点数（n=0）即为空二叉树。

三：什么是斜树？

　　- 定义

　　　　- 所有的结点只有左子树/只有右子树。

四：什么是满二叉树？

　　- 定义

　　　　- 所有的分支结点都存在左右子树，并且叶子节点在同一层上。

　　　　- 非叶子结点的度一定是2

　　- 图示

　　　　-

五：什么是完全二叉树？

　　- 定义

　　　　- 若二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

　　- 特点

　　　　- 满二叉树是一棵特殊的完全二叉树，但完全二叉树不一定是满二叉树。

　　- 图示

　　　　-

六：什么是 （BST）二叉搜索树？

　　- 概念

　　　　- 二叉搜索树又称为二叉查找树。

　　- 定义

　　　　- 它首先是一颗二叉树，当树中的每个节点N，其左子树所有节点的值都小于节点N的值，右子树节点的值都大于节点N的值。

　　- 图示

　　　　-
　

七：什么是 （AVL 平衡二叉树）？

　　- 为什么需要 AVL 平衡二叉树？

　　　　- 二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序时，二叉树退化成单链表，搜索效率降低为 O(n)。

　　　　　　-

　　　　- 二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。
　　　　　　-

　　　　
　　　　- 可以看出当节点数目一定，保持树的左右两端保持平衡，树的查找效率最高。

　　　　- 这种左右子树的高度相差不超过 1 的树为平衡二叉树。

　　- 定义

　　　　- 可以是空树。

　　　　- 假如不是空树，任何一个节点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。

　　- 详解

　　　　- https://www.cnblogs.com/fivestudy/p/10348045.html


八：什么是 B-树？

　　- 为什么要有 B-树？

　　　　- 二叉查找树查询的时间复杂度是O（logN），查找速度最快和比较次数最少

　　　　- 既然性能已经如此优秀，但为什么实现索引是使用B-Tree而不是二叉查找树，关键因素是磁盘IO的次数。

　　　　　　- 数据库索引是存储在磁盘上，当表中的数据量比较大时，索引的大小也跟着增长，达到几个G甚至更多。

　　　　　　- 当我们利用索引进行查询的时候，不可能把索引全部加载到内存中，只能逐一加载每个磁盘页，这里的磁盘页就对应索引树的节点。

　　　　-分析情况来看，减少磁盘IO的次数就必须要压缩树的高度，让瘦高的树尽量变成矮胖的树，所以B-Tree就在这样伟大的时代背景下诞生了。

　　- 定义

　　　　- m阶B-Tree满足以下条件

　　　　　　- 每个节点最多拥有m个子树

　　　　　　- 根节点至少有2个子树

　　　　　　- 分支节点至少拥有m/2颗子树（除根节点和叶子节点外都是分支节点）

　　　　　　- 所有叶子节点都在同一层、每个节点最多可以有m-1个key，并且以升序排列。

　　- 优点

　　　　- 相同数量的数据下，B-树压缩了整个树的高度，磁盘的I/O更少。

　　　　- 叶子节点可以保存更多的数据，容纳更多的结点元素。

　　- 图示（3阶B-树）

　　　　-

　　- 详解

　　　　- https://www.cnblogs.com/dongguacai/p/7239599.html

九：什么是 B+树？

　　- 为什么要有B+树？

　　　　- B-树通常用作索引，但是面对数据量大的情况下，B-树的阶级变大，查找性能下降。

　　　　- B+Tree是B树的变种，有着比B树更高的查询性能。可以在B-的基础上在压缩树的高度，减少I/O。

　　- 定义

　　　　- 有m个子树的节点包含有m个元素（B-Tree中是m-1）

　　　　- 根节点和分支节点中不保存数据，只用于索引，所有数据都保存在叶子节点中。

　　　　- 所有分支节点和根节点都同时存在于子节点中，在子节点元素中是最大或者最小的元素。

　　　　- 叶子节点会包含所有的关键字，以及指向数据记录的指针，并且叶子节点本身是根据关键字的大小从小到大顺序链接。

　　- B+的优点

　　　　- B+树的节点不存储（真实数据），所以同样大小的磁盘页可以容纳更多的节点元素，在相同数量的数据下，B+树就相对来说要更加矮胖些，磁盘IO的次数更少。

　　　　- 由于只有叶子节点才保存卫星数据，B+树每次查询都要到叶子节点；而B树每次查询则不一样，最好的情况是根节点，最坏的情况是叶子节点，没有B+树稳定。

　　　　- 叶子节点形成有顺链表，范围查找性能更优。

　　- 详解

　　　　- https://www.cnblogs.com/dongguacai/p/7241860.html

　　- 图解

　　　　- 

十：什么是（RBT）红黑树？

　　- 为什么要有 红黑树？

　　　　- 二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序时，二叉树退化成单链表，搜索效率降低为 O(n)。

　　　　- 为了解决二叉树多次插入新节点导致的不平衡。

　　- 新插入结点的默认是什么颜色？

　　　　- 从红黑树的性质我们知道，红黑树的左右子树具有相等的黑高。

　　　　- 如果新插入的节点默认设置为黑色，则势必会破坏左右子树的黑高相等的特点。

　　　　- 此时，再调整红黑树，就会比较繁琐。

　　　　- 而如果默认将新插入的节点设置为红色，它不会破坏相等黑高的已有状态，我们只需要解决红节点的左右孩子必须是黑节点的问题即可。

　　　　- 所以，红黑树新插入的节点，默认设置为红色。

　　- 调整红黑树的方式？

　　　　- 变色/旋转

　　- 红黑树和平衡二叉树区别？

　　　　- 红黑树即为平衡二叉树。

　　　　- 只不过它的每个节点多加了一个标志属性，用于增加和删除节点。

　　　　- 相对于平衡二叉树来说，红黑树在增加/删除节点的性能更好。

　　　　- 红黑树和B-树的区别？

　　　　- 二者都是有序数据结构，可用作数据容器。

　　　　- 红黑树多用在内部排序，即全放在内存中的，微软STL的map和set的内部实现就是红黑树。

　　　　- B树多用在内存里放不下，大部分数据存储在外存上时。因为B树层数少，因此可以确保每次操作，读取磁盘的次数尽可能的少。

　　　　- 在数据较小，可以完全放到内存中时，红黑树的时间复杂度比B树低。

　　　　- 反之，数据量较大，外存中占主要部分时，B树因其读磁盘次数少，而具有更快的速度。

　　- 定义

　　　　- 节点是红色或黑色。

　　　　- 根节点是黑色。

　　　　- 每个叶子节点都是黑色的空节点（NIL节点）。

　　　　- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点).

　　　　- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。