树
二叉树
满足以下条件的树为二叉树：
任一节点的左子树小于右子树
二叉树的如下：
二叉树中，第 \(i\) 层最多有 \(2^{i-1}\) 个结点
如果二叉树的深度为 \(K\) 。那么二叉树最多有 \(2^K-1\) 个节点
设叶子节点数为 \(n_0\) ，度为二的节点数为 \(n_2\) ，那么 \(n_0=n_2+1\)
此外还有一些特殊二叉树的性质：
满二叉树：
第 \(i\) 层的节点数为 \(2^{n-1}\) 个
深度为 \(k\) 的满二叉树必有 \(2^k-1\) 个节点，叶子数为 \(2^{k-1}\)
具有 \(n\) 个节点的满二叉树的深度为 \(\log_2(n+1)\)
完全二叉树：二叉树除了最后一层外是满二叉树，而且左子树一定比右子树满
\(n\) 个结点的完全二叉树的深度为 \(\\lfloor log_2n\rfloor +1\)
树之间的关系为：
graph TD
A[二叉树]-→ B[完全二叉树] B-→ C[满二叉树] A-→ D[二叉排序树] D-→ E[平衡二叉树]
二叉树的遍历
二叉树的遍历有三种：
先序遍历：NLR，
中序遍历：LNR
后序遍历：LRN
以及最后的 层次遍历 。层次遍历可以使用队列完成。从根节点开始，将节点入队，然后出队一个节点，再将出队节点的左右孩子入队。得到的就是层次遍历
先序遍历可以简单叙述为：
void PreOrderTraverse(BTree tree){
stacks.push(root)
while(auto node = stacks.pop()){
visit(node);
stacks.push(node.right());
stacks.push(node.left());
}
}使用序列还原二叉树
先序
中序：由先序遍历序列我们可以立刻确定根节点，那么在中序遍历序列中，我们定位这个找出来的根节点，该结点以左就是它的左子树，该结点以右就是它的右子树[1]
先+后不行，但是其他的都可以
平衡二叉树
当二叉树插入的序列有序时，二叉树会退化成一个链表，为了解决这个问题，就提出了平衡二叉树。平衡二叉树的左右子树的高度之差不超过一。要保证这一点，在节点插入时可能需要用到多次树的旋转。
AVL (平衡二叉树) 具有以下性质：
可以是空树
如果不是空树，那么左右子树都是平衡二叉树，且高度之差不超过一
AVL 中涉及到了平衡因子的概念，平衡因子就是左子树与右子树高度之差。AVL 中不存在平衡因子大于 1 的节点。平衡因子可能的取值是 -1、0、1 。
旋转
旋转分为以下几种：
左旋：
使用节点的右孩子代替此节点的位置
使右孩子的左子树变为该节点的右子树
节点变为右孩子的左子树
右旋：
节点的左孩子代替此节点
节点的左孩子的右子树变为节点的左子树
节点变为左孩子的右子树
插入
节点插入引起的失衡分为以下几种：
左孩子的左子树导致的失衡：对节点使用一次右旋
右孩子的右子树导致的失衡：对节点使用一次左旋
左孩子的右子树导致的失衡：先对失衡节点的左孩子进行左旋，再对节点进行右旋
右孩子的左子树导致的失衡：对失衡节点的右孩子进行右旋，再对失衡节点左左旋
最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。
红黑树
红黑树是一种弱化的 AVL。主要原因是：
AVL 在插入时的旋转次数过多
红黑树和 AVL 的时间复杂度相差并不是太多
红黑树的整体性能更好
相比 AVL 而言，红黑树做出以下保证：
最长路径不超过最短路径的二倍，因而近似平衡
性质如下：
每个节点不是黑色就是红色
根节点是黑色的
红节点的两个子节点是黑色的（没有连续的红色节点）
对于每个节点，从该节点到其后代叶节点的简单路径上，均包含相同数目的黑色节点
插入最多两次旋转，删除最多三次旋转
红黑树在查找，插入删除的性能都是 \(O(\log n)\) ，且性能稳定，所以 STL 里面很多结构包括 map 底层实现都是使用的红黑树。
红黑树依赖于节点的颜色对节点进行调整，当节点颜色满足定义时，红黑树也就自然满足它的性质了。
节点的插入：
由于插入黑色节点的代价太大（除了根节点），因此 插入的节点的颜色都是红色 的，插入后需要根据颜色对树进行调整，主要方式为：
父节点 | 爷爷节点 | 叔叔节点 | 位置关系 | 调整方式 |
黑 | 任意 | 任意 | 任意 | 无需调整 |
红 | 黑 | 红 | 任意 | 父节点和叔叔节点改为黑色，爷爷节点改成红色，然后从爷爷节点向上继续调整颜色 |
红 | 黑 | 不存在/黑 | 插入节点为左孩子、父节点左孩子 | 以父节点为轴心进行右旋 |
红 | 黑 | 不存在/黑 | 插入节点为右孩子、父节点右孩子 | 以父节点为轴心进行右旋 |
红 | 黑 | 不存在 | 插入节点为右孩子，父节点为左孩子 | 对父节点进行左旋 |
红 | 黑 | 不存在 | 插入节点为左孩子，父节点为右孩子 | 对父节点进行右旋 |
哈夫曼树
哈夫曼树是一种带权树。节点的带权路径长度被称为代价。
在构建哈夫曼树时，需要遵循一个原则：权值越大离根越近
构建哈夫曼树[2]
对于给定的有各自权值的 \(n\) 个结点，构建哈夫曼树有一个行之有效的办法：
在 \(n\) 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
在原有的 \(n\) 个权值中删除那两个最小的权值，同时将新的权值加入到 \(n–2\) 个权值的行列中，以此类推；
重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。