二叉树
二叉树
名词解释
- 叶子节点：末尾的子节点，自己下面不再连接有节点的节点（即末端），称为叶子节点（又称为终端结点）
二叉树旋转
左旋
逆时针旋：头节点变成了心头节点的左孩子
右旋
顺时针旋：头节点变成了新头结点的右孩子。
旋转的情况
LL
RR
LR
RL
遍历方式
广度优先遍历(BFS)
- 广度优先遍历先从树的最高层开始，从左向右逐层向下访问树中的每一个元素。
- 应用：
- 二叉树层序打印 力扣102
- 最短路径(无权最短路径问题)
深度优先遍历(DFS）
- 深度优先遍历会尽量从根节点访问到叶节点，再回溯至最近一次有未访问子节点的节点，再访问到其叶节点。根据其访问节点的先后顺序可以有多种访问的方式，但常用的主要是前序树遍历、中序树遍历和后序树遍历。
前序树遍历
- 对于每一个子树的遍历顺序：中 左 右
中序树遍历
- 对于每一个子树的遍历顺序：左 中 右
- 后继节点 前驱节点 ：在中序遍历中一个节点的下一个或上一个
- Morris遍历法：
后序树遍历
- 对于每一个子树的遍历顺序：右 左 中
Morris遍历
- 遍历标准： 当前节点为cur
- cur没有左子树，cue向右子树 移动(cur = cur.right)
- cur存在左子树，找到左子树上最右的节点 记为mostright
- mostright的右子树为空， 则设置mostright的右子树指向cur,然后cur向左移动
- mostright的右子树为cur,让其指向空，cur向右移动
- Morris遍历中， 如果一个节点有左子树，morris遍历能回到这个节点两次，当第二次到达这个节点的时候，说明左子树上的节点已经全部遍历完。如果一个节点没有左子树，则只到达这个节点一次。
满二叉树
- 满二叉树：一棵二叉树的结点要么是叶子结点，要么它有两个子结点（如果一个二叉树的层数为K，且结点总数是(2^k) -1，则它就是满二叉树。）
- 满二叉树的节点总数SUM和高度L的公式为 SUM = $2^{L}-1$
2-3树
2-3树是最简单的B-树（或-树）结构，其每个非叶节点都有两个或三个子女，而且所有叶都在统一层上。2-3树不是二叉树，其节点可拥有3个孩子。不过，2-3树与满二叉树相似。高为h的2-3树包含的节点数大于等于高度为h的满二叉树的节点数，即至少有2^h-1个节点
特质
- 2-3 树所有叶子节点都在同一层
- 1 个节点可以有 1 到 2 个数据，如果有三个需要调整树结构
- 1 个节点 1 个数据时，则有两个子节点
- 1 个节点 2 个数据时，则有三个子节点，且中间子节点是介于两个节点间的值
插入图解
完全二叉树CBT
- 若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边，这就是完全二叉树。
- 一个从0开始数组 (下标位置)【0，1，2，3，4，5.。。。。。】对应的二叉树的结构一些规律
- 子字节i的父节点的值是 (i-1)/2
- 父节点f的左右子树是 f * 2 + 1 和 f*2 +2
二叉查找树BST（搜索二叉树）
- 首先它也是一个二叉树，故满足递归定义;
- 其次每个节点只存在一个值;
- 需满足左子树任意值<=根值<=右子树任意值 ，故按照中序遍历会得到一个非递减(依次升序)序列。标注的搜索二叉树没有重复的值，因为相同的值可以压缩在一个节点上。
- 性质
- 1.在一棵二叉查找树上，执行查找、插入、删除等操作的时间复杂度为O（logn）。因为，一棵由n个结点，随机构造的二叉查找树的高度为lgn，所以顺理成章，一般操作的执行时间为O（lgn）。
- 2.但若是一棵具有n个结点的线性链，则此些操作最坏情况运行时间为O（n）。
平衡二叉树AVL
- 首先仍是一棵二叉树，满足递归定义;
- 其次又是一棵BST，满足有序;
- 每个节点左右子树高度差的绝对值不能超过1
- 性质
- 会发生左旋和右旋操作
红黑树Red Black Tree
- 首先仍是一棵二叉树，满足递归定义;
- 其次又是一棵BST，满足有序;
- 最长子树不超过最短子树的两倍
- 根节点是黑色，叶子节点为黑色。每个红色节点的子节点一定都是黑色。
- 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。红色节点不相邻
SB树
- TODO
自适应树
- 虽然平衡树能使树的平均路径深度得到有效降低，但是频繁的对树进行平衡操作会造成很大的性能浪费，因为通常我们更关心执行插入、删除和查找操作的效率而不是树的形状。因为我们对不同元素的访问有偏好性，因此根据访问频率沿着树向上移动元素从而形成一种优先树即自适应树是一个很好的解决方案。
- 自适应树的构造策略分为：1）单一旋转：如果访问子节点，则将子节点围绕它的父节点进行旋转。2）移动到根部：重复子节点-父节点的旋转，直至将被访问元素移到根部。
张开策略
半长开策略
treap树
- 二叉查找树的操作非常高效，但多次操作时会发生树的不平衡现象，堆是完全平衡树，可以快速访问最大或者最小元素，但是不能立即访问其他元素。如果有一个树同时满足堆的部分性质和二叉查找树的部分性质的树称为他treap树。它有多种实现方式。
显示优先级实现-笛卡尔树
- 对于它的每个节点包含一个键值对，其中键满足二叉树性质，值满足最大堆性质。
在其中插入元素时，首先生成随机的优先级，用键根据二叉查找树性质在树中找到合适的位置插入，再根据值通过旋转二叉树方式来恢复堆属性。
删除元素时将其优先级较高的节点围绕它进行旋转直至被删除的节点只有一个子节点后者没有子节点，此时直接将改元素删除。
隐式优先级实现
- treap树并不总是需要在每个节点储存其优先级，第一种方法是使用一个散列函数h，将具有键值k的某项优先级设置为h（k），但这种方案暂不讨论。另外一种是通过数组分方式实现treap树，其中数组的序号代表其优先级，这种方式类似于最小堆。但是节点和子节点在数组中序号的对应方式不能套用堆中的公式。
这种方案中插入一个节点，需要随机生成小于等于n的优先级i，如果i=n，则直接将节点放在数组末尾，否则需要将数组中占据i位置的项通过一系列的旋转操作变为叶节点，再将需要插入的节点根据二叉树的性质放在合适的位置，再根据其优先级恢复整个的堆性质就能得到新的treap树。在数组中直接插入对应索引即得到新的数组。
删除一个节点时，首先从treap树中删除节点，先通过二叉树删除节点规则将节点删除，然后在数组中将最后一个元素填到当前位置确定新的游优先级，再根据新的优先级恢复堆属性。
k-d树
- 通常二叉查找树的每个节点只有一个键值，当每个节点拥有多个键值时成为k-d树，k代表每个节点拥有的键值数。k-d树将各个维度在从根到子节点的每一层中有顺序的交替使用。通过这种方式可以在空间中划分很多不同的区域。
多叉树
- 二叉树中每个节点只有两个子节点，当每个节点最多包含m个节点时就是m阶多叉树
- 对于m阶的多差查找树有以下四个特性
- 每个节点都可以包含m个子节点和m-1个键值。
- 所有节点的键值都按升序排列。
- 前i个子节点中的键值都小于第i个键值。
- 后m-i个子节点中的键值都大于第i个键值。
B树
- B树属于多叉树又名平衡多路查找树
- m阶的B树具有以下性质：
- 根节点至少有两个子节点
- 每个节点有M-1个key，并且以升序排列
- 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
- 其它节点至少有M/2个子节点
B+树
B+树是在B树的基础上又一次的改进，其主要对两个方面进行了提升，一方面是查询的稳定性，另外一方面是在数据排序方面更友好。
B+树的非叶子节点不保存具体的数据，而只保存关键字的索引，而所有的数据最终都会保存到叶子节点。因为所有数据必须要到叶子节点才能获取到，所以每次数据查询的次数都一样，这样一来B+树的查询速度也就会比较稳定，而B树的查找过程中，不同的关键字查找的次数很有可能都是不同的（有的数据可能在根节点，有的数据可能在最下层的叶节点），所以在数据库的应用层面，B+树就显得更合适。
B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。因为叶子节点都是有序排列的，所以B+树对于数据的排序有着更好的支持。
B树和B+树的对比
- B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定。
- B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
- B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
- B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字和数据，所以在查询这种数据检索的时候会要比B+树快。
DSW算法
- DSW算法构建平衡二叉树：TODO
Trie 前缀树字典树
Trie树又被称为前缀树、字典树，把单词字母一条一条灌进一棵树中，每个节点是a-z之间的字母，对于都是数字的字符串，字符集就是0-9， 每一个节点包含三个元素，分别是节点对应的字符name，存储的子节点信息Map(name -> 节点对象), 是否是词尾标志end。 词尾标志可以记录到中间任一节点位置，词尾标志还能记录数量，为多少个字符串的结尾
字母应该放在边上，而不是节点上，放到节点上会增加实现难度