Avl树

前言

众所周知，二叉搜索树的性质是，节点的左子树键值都比节点的小，右子树键值都比节点的大。当单调增加或减少的值一一插入时，插入等时间复杂度严重退化成线性。所以我们要控制左右子树的高度差，作为平衡因子，将一次操作的时间复杂度控制在对数级内。

在实习的应用场景中，我想将一个时间复杂度高达 的算法，降到 ，以便于给后面的 算法腾出点儿时间（划掉）。查询资料，我选择了 Avl 树作为底层数据结构。接下来，我将写一个针对那个问题的c++模板类，以便于后续的更改。

（以后要不要来点酸爽的红黑树呢？）

实现

时间复杂度测试