AVL树
一种自平衡的二叉搜索树.AVL树通过在每个节点上维护一个平衡因子来确保树的平衡，平衡因子定义为左子树和右子树的高度差。
AVL树的性质要求任何节点的左右子树的高度差绝对值不超过1，这使得AVL树在插入和删除操作后能够通过旋转操作来保持平衡。
AVL 是大学教授 G.M. Adelson-Velsky 和 E.M. Landis 名称的缩写，他们提出的平衡二叉树的概念，为了纪念他们，将 平衡二叉树 称为 AVL树。
AVL树的主要特点包括：
- 自平衡性：AVL树通过旋转操作来保持平衡，确保树的左右子树高度差不超过1。
- 二叉搜索树：AVL树本质上是一棵二叉搜索树，其节点值满足左子节点小于父节点，右子节点大于父节点的规则。
- 高度平衡：AVL树的每个节点的左右子树高度差的最大值为1，因此也被称为高度平衡树。
1.为什么引入AVL树（平衡二叉搜索树）。平衡二叉排序树。插入数据导致不平衡时，需要旋转。
二叉搜索树，致命的弱点，接近排好序的数据，查找时会退化成 0(N)，相当于数组。AVL树能解决这个问题。
找资料（google）
左旋，右旋，先左旋后右旋，先右旋后左旋
AVL树 的定义：
- 左右两个子树的高度差，不会超过1；
- 空树也是平衡二叉树，每棵子树也是平衡二叉树。
平衡二叉搜索树的意义：普通的二叉搜索树，会出现极度不平衡的情况，复杂度有可能会退化成O(N), 所以引入AVL树。
平衡二叉搜索树，可以确保时间复杂度在O(logN)
2.旋转操作： 谁不平衡，旋转谁？
原数据：[3,2,1,4,5,6,7, 10,9,8]
发现如果打破了平衡的规则，就对其进行调整，使其满足一棵平衡二叉树。
右旋：3,2,1 把2提上来作为根节点，1不动 左边孩子，3作为2的右孩子。变成了平衡二叉树。3不平衡了，将3 往右边旋转了。
再插入4，不要调整；
左旋：再插入5，把4提上来变成根节点2的右孩子，原来的节点3作为4的左孩子，右边5保持不变。3不平衡了，将3往左边旋转了(作为4的左孩子)。
左旋：再插入6，此时对于2不平衡了，把4作为根节点，将2左旋（2不平衡了）。
【2进行 左旋，被提上去的节点4 左孩子非空，要作为原根节点的右孩子】
原来4节点的左孩子3，作为2的右孩子。
再插入7，在6的右节点位置，此时5不平衡了（左旋），6的左孩子5，右孩子7.
再插入10，在7的右节点位置，此时还是平衡的。
再插入9，在10的左边位置，此时不平衡了。此时7不平衡了。把10作为根。单纯左旋不满足需求，快要【先右旋10，再左旋7】.
左边的高度，大于右边的高度。
再插入8， 插入7的右节点位置，此时7/10/9都是平衡的。但是6是不平衡的。所以要旋转6.
单纯的左旋6，9变成根节点，左孩子6/右孩子10；6的左孩子5/右孩子7；7的右孩子8. 还是不平衡的。
因为9的左孩子，比右孩子的高度 高。
先对9右旋，7变成根节点。7的右节点 变成9，9的左节点8/右节点10.
此时对6还是不平衡，把6再左旋转一把，7成根节点，7的左孩子6, 6的左孩子5. 进而成平衡二叉树。
左旋的过程：加入9 的时候。7变得 不平衡了。
- 把(7) 的右孩子(10) 作为它的 根节点。
- 把根(7) 作为了现在根(10) 的 左孩子(7)。
- 如果原来的右孩子 的 左孩子 不为空(9)，就把这个左孩子作为 现在左孩子(7) 的 右孩子(9)。
左旋 特殊情况：左旋转完之后，发现（10）还是不平衡。一次左旋不能满足情况。
所以要先右旋，再左旋。
先右旋 再左旋。【左边的高度 大于 右边的高度】
先把节点(10)右旋，变成7的右节点9,9的右节点10. 此时是还是不平衡，
左旋(7不平衡，左旋7)，变成9根节点 提升，左节点7，右节点10.
先左旋 再右旋。【右边的高度3，大于左边的1】
修正一棵平衡二叉树：
左旋、右旋、先右旋再左旋、先左旋再右旋。 ---->红黑树。
【先左旋再右旋】eg: 3,-1(左子树),0(-1的右边) 的二叉树，单纯的右旋不行。
先左旋，变成3,左0, 左-1；
再右旋，变成0，左-1/右3.
优化app卡顿：
TraceView 找到卡顿的地方，二维带权的正泰分布函数(高斯函数)。
图片越大，算法复杂度也越高。
3.插入调整，增加的过程中不断地调整。
在新增的过程中，不断地进行调整。发现打破了平衡规则，就对其进行调整，使其满足平衡二叉树。
template<class K, class V>
struct TreeNode {
public:
TreeNode<K, V> *left = NULL;
TreeNode<K, V> *right = NULL;
K key;
V value;
int height;// 当前树的高度
TreeNode(K key, V value) : height(1) {// 初始节点的高度为 1
this->right = NULL;
this->left = NULL;
this->key = key;
this->value = value;
}
TreeNode(TreeNode<K, V> *pNode) : height(pNode->height) {
this->left = pNode->left;
this->right = pNode->right;
this->key = pNode->key;
this->value = pNode->value;
}
};
int getHeight(TreeNode<K, V> *pNode) {
return pNode ? pNode->height : 0;
}
// 四个旋转操作
// 右旋：pNode自己变成右孩子，原来的左孩子变成新根节点，原左孩子的右孩子 变成新右孩子的左孩子。
TreeNode<K, V> *R_Rotation(TreeNode<K, V> *pNode) {
TreeNode<K, V> *left = pNode->left; // 1.原来的左孩子作为根节点。用作返回
pNode->left = left->right; // 2.左节点的右孩子，将来作为原根节点的左孩子。
left->right = pNode; // 3.原来的根节点，作为新根节点的右孩子。
// 更新高度= 左边高度/右边高度最大值 +1.
pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
left->height = max(getHeight(left->left), getHeight(left->right)) + 1;
return left; // 4.返回原根节点的左孩子，作为新根节点。
}
// 左旋操作
TreeNode<K, V> *L_Rotation(TreeNode<K, V> *pNode) {
TreeNode<K, V> *right = pNode->right; // 1.原节点的左节点作为根节点。用作返回
pNode->right = right->left; // 2.右节点的左孩子，将要作为原根节点的右孩子。
right->left = pNode; // 3.原节点，作为新节点的左孩子。
// 更新高度
pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
right->height = max(getHeight(right->left), getHeight(right->right)) + 1;
return right; // 4.返回pNode的右节点right为 新根节点。
}
// 返回一个节点 (逻辑问题？ 1 ，2) ，多去理解
TreeNode<K, V> *addNode(TreeNode<K, V> *pNode, K key, V value) {
if (pNode == NULL) {
count++;
return new TreeNode<K, V>(key, value);
}
if (pNode->key > key) {// 小
pNode->left = addNode(pNode->left, key, value); // 往左边添加节点
if (getHeight(pNode->left) - getHeight(pNode->right) == 2) {
// 调整 , 不能简简单单的就做一次右旋。还会出现要先左 再右旋的情况。
pNode = R_Rotation(pNode);
}
} else if (pNode->key < key) {
pNode->right = addNode(pNode->right, key, value); // 往右边添加节点
if (getHeight(pNode->right) - getHeight(pNode->left) == 2) {
// 调整（要考虑先右再左旋）
pNode = L_Rotation(pNode);
}
} else {
pNode->value = value;
}
// 更新二叉树的高度
pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
return pNode;
}
4.删除调整--很复杂
