树 — 二叉树 顺序性(左子树 根节点 右子树) — 二叉排序树 限制 — AVL树(二叉平衡树)AVL树的定义限制 — 每个结点的左右子树的高度差不超过1。一个结点的平衡因子是其左右子树的高度差对BST树加上限制每个结点的平衡因子的绝对值不超过1 --------------AVL树自平衡二叉树 / 平衡二叉树 / 二叉平衡树 AVL树的旋转操作在插入过程中如果插入某个结点后失衡需要进行调整重新让树保持平衡调整的过程就是旋转操作左单旋x为失衡结点(1) x的右子树变成y的左子树x-righty-left(2) y的左孩子变成xy-leftx(3)return y让外层递归得到新的(子树的)根节点右单旋x为失衡结点(1) x的左子树变成y的右子树x-lefty-right(2) y的右孩子变成xy-rightx(3)return y让外层递归得到新的(子树的)根节点AVL树的操作查找 — 和BST树一模一样插入插入一个数据x(1) 先按照BST步骤进行插入(2) 再对失衡结点进行旋转操作优先调整最小失衡子树。最小失衡子树从新插入的结点往上查找以第一个平衡因子的绝对值超过1的结点为根的子树称为最小平衡子树。我们只需要调整最小的不平衡子树即可四种失衡情况LL往A的左孩子的左子树中插入一个结点导致A的左子树比右子树高以A为中心右旋LR往A的左孩子的右子树中插入一个结点导致A的右子树比左子树高(1) 以A-left为中心左旋 ---- 转化成LL(2) 按照LL情况进行操作RR往A的右孩子的右子树中插入一个结点导致A的右子树比左子树高以A为中心左旋RL往A的右孩子的左子树中插入一个结点导致A的右子树比左子树高(1) 以A-right为中心右旋 ---- 转化成RR(2) 按照RR的情况进行操作四种调整函数的代码实现//四种调整函数//LL -- 以失衡结点x为中心右旋AVLTreeLL_rotation(AVLTree x){AVLNode*yx-left;x-lefty-right;y-rightx;//xy变了则它的高度就可能会变//先更新x再更新yx-hmax(getH(x-left),getH(x-right))1;y-hmax(getH(y-left),getH(y-right))1;returny;}//RR -- 以失衡结点为中心左旋AVLTreeRR_rotation(AVLTree x){AVLNode*yx-right;x-righty-left;y-leftx;//xy变了则它的高度就可能会变//先更新x再更新yx-hmax(getH(x-left),getH(x-right))1;y-hmax(getH(y-left),getH(y-right))1;returny;}//LR -- 先以x-left为中心左旋再以失衡结点x为中心右旋AVLTreeLR_rotation(AVLTree x){x-leftRR_rotation(x-left);xLL_rotation(x);returnx;}//RL -- 先以x-right为中心右旋再以失衡结点x为中心左旋AVLTreeRL_rotation(AVLTree x){x-rightLL_rotation(x-right);xRR_rotation(x);returnx;}