########################################
树
########################################

二叉树
****************************************

满足以下条件的树为二叉树：

- 任一节点的左子树小于右子树

二叉树的如下：

- 二叉树中，第 :math:`i` 层最多有 :math:`2^{i-1}` 个结点
- 如果二叉树的深度为 :math:`K` 。那么二叉树最多有 :math:`2^K-1` 个节点
- 设叶子节点数为 :math:`n_0` ，度为二的节点数为 :math:`n_2` ，那么 :math:`n_0=n_2+1`

此外还有一些特殊二叉树的性质：

满二叉树：

- 第 :math:`i` 层的节点数为 :math:`2^{n-1}` 个
- 深度为 :math:`k` 的满二叉树必有 :math:`2^k-1` 个节点，叶子数为 :math:`2^{k-1}`
- 具有 :math:`n` 个节点的满二叉树的深度为 :math:`\log_2(n+1)`

完全二叉树：二叉树除了最后一层外是满二叉树，而且左子树一定比右子树满

- :math:`n` 个结点的完全二叉树的深度为 :math:`\\lfloor log_2n\rfloor +1`

树之间的关系为：

.. mermaid::

   graph TD

      A[二叉树]-->|树左边比右边先满, 且左右子树高度之差不超过一| B[完全二叉树]
      B-->|节点全满| C[满二叉树]
      A-->|父节点大于左节点小于右节点| D[二叉排序树]
      D-->|左右子树高度之差不超过一| E[平衡二叉树]

二叉树的遍历
========================================

二叉树的遍历有三种：

- 先序遍历：NLR，
- 中序遍历：LNR
- 后序遍历：LRN

以及最后的 *层次遍历* 。层次遍历可以使用队列完成。从根节点开始，将节点入队，然后出队一个节点，再将出队节点的左右孩子入队。得到的就是层次遍历

先序遍历可以简单叙述为：

.. code-block:: none

   void PreOrderTraverse(BTree tree){
      stacks.push(root)
      while(auto node = stacks.pop()){
         visit(node);
         stacks.push(node.right());
         stacks.push(node.left());
      }
   }

使用序列还原二叉树
========================================

- 先序 + 中序：由先序遍历序列我们可以立刻确定根节点，那么在中序遍历序列中，我们定位这个找出来的根节点，该结点以左就是它的左子树，该结点以右就是它的右子树 [#pre]_

先+后不行，但是其他的都可以

.. [#pre] `已知二叉树的遍历序列去还原二叉树的超好用方法分析 <https://eezzh.blog.csdn.net/article/details/94837044>`_

平衡二叉树
****************************************

当二叉树插入的序列有序时，二叉树会退化成一个链表，为了解决这个问题，就提出了平衡二叉树。平衡二叉树的左右子树的高度之差不超过一。要保证这一点，在节点插入时可能需要用到多次树的旋转。

:abbr:`AVL (平衡二叉树)` 具有以下性质：

- 可以是空树
- 如果不是空树，那么左右子树都是平衡二叉树，且高度之差不超过一

AVL 中涉及到了平衡因子的概念，平衡因子就是左子树与右子树高度之差。AVL 中不存在平衡因子大于 1 的节点。平衡因子可能的取值是 -1、0、1 。

旋转
========================================

旋转分为以下几种：

- 左旋：

   #. 使用节点的右孩子代替此节点的位置
   #. 使右孩子的左子树变为该节点的右子树
   #. 节点变为右孩子的左子树

- 右旋：

  #. 节点的左孩子代替此节点
  #. 节点的左孩子的右子树变为节点的左子树
  #. 节点变为左孩子的右子树

插入
========================================

节点插入引起的失衡分为以下几种：

- 左孩子的左子树导致的失衡：对节点使用一次右旋
- 右孩子的右子树导致的失衡：对节点使用一次左旋
- 左孩子的右子树导致的失衡：先对失衡节点的左孩子进行左旋，再对节点进行右旋
- 右孩子的左子树导致的失衡：对失衡节点的右孩子进行右旋，再对失衡节点左左旋

最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。

.. seealso::

   - `什么是平衡二叉树（AVL） <https://zhuanlan.zhihu.com/p/56066942>`_

红黑树
****************************************

红黑树是一种弱化的 AVL。主要原因是：

- AVL 在插入时的旋转次数过多
- 红黑树和 AVL 的时间复杂度相差并不是太多
- 红黑树的整体性能更好

相比 AVL 而言，红黑树做出以下保证：

- 最长路径不超过最短路径的二倍，因而近似平衡

性质如下：

- 每个节点不是黑色就是红色
- 根节点是黑色的
- 红节点的两个子节点是黑色的（没有连续的红色节点）
- 对于每个节点，从该节点到其后代叶节点的简单路径上，均包含相同数目的黑色节点
- 插入最多两次旋转，删除最多三次旋转

红黑树在查找，插入删除的性能都是 :math:`O(\log n)` ，且性能稳定，所以 STL 里面很多结构包括 map 底层实现都是使用的红黑树。

红黑树依赖于节点的颜色对节点进行调整，当节点颜色满足定义时，红黑树也就自然满足它的性质了。

节点的插入：

由于插入黑色节点的代价太大（除了根节点），因此 *插入的节点的颜色都是红色* 的，插入后需要根据颜色对树进行调整，主要方式为：

+--------+----------+-----------+----------------------------------+----------------------------------------------------------------------------+
| 父节点 | 爷爷节点 | 叔叔节点  | 位置关系                         | 调整方式                                                                   |
+========+==========+===========+==================================+============================================================================+
| 黑     | 任意     | 任意      | 任意                             | 无需调整                                                                   |
+--------+----------+-----------+----------------------------------+----------------------------------------------------------------------------+
| 红     | 黑       | 红        | 任意                             | 父节点和叔叔节点改为黑色，爷爷节点改成红色，然后从爷爷节点向上继续调整颜色 |
+--------+----------+-----------+----------------------------------+----------------------------------------------------------------------------+
| 红     | 黑       | 不存在/黑 | 插入节点为左孩子、父节点左孩子   | 以父节点为轴心进行右旋                                                     |
+--------+----------+-----------+----------------------------------+----------------------------------------------------------------------------+
| 红     | 黑       | 不存在/黑 | 插入节点为右孩子、父节点右孩子   | 以父节点为轴心进行右旋                                                     |
+--------+----------+-----------+----------------------------------+----------------------------------------------------------------------------+
| 红     | 黑       | 不存在    | 插入节点为右孩子，父节点为左孩子 | 对父节点进行左旋                                                           |
+--------+----------+-----------+----------------------------------+----------------------------------------------------------------------------+
| 红     | 黑       | 不存在    | 插入节点为左孩子，父节点为右孩子 | 对父节点进行右旋                                                           |
+--------+----------+-----------+----------------------------------+----------------------------------------------------------------------------+

.. seealso::

   - `浅析红黑树（RBTree）原理及实现 <https://blog.csdn.net/tanrui519521/article/details/80980135>`_

哈夫曼树
****************************************

哈夫曼树是一种带权树。节点的带权路径长度被称为代价。

在构建哈夫曼树时，需要遵循一个原则：权值越大离根越近

构建哈夫曼树 [#hafu]_

对于给定的有各自权值的 :math:`n` 个结点，构建哈夫曼树有一个行之有效的办法：

- 在 :math:`n` 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
- 在原有的 :math:`n` 个权值中删除那两个最小的权值，同时将新的权值加入到 :math:`n–2` 个权值的行列中，以此类推；
- 重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。

.. [#hafu] `哈夫曼树（赫夫曼树、最优树）及C语言实现 <http://data.biancheng.net/view/33.html>`_

线段树
****************************************

- `算法学习笔记(14): 线段树 <https://zhuanlan.zhihu.com/p/106118909>`_