AVL平衡树

特征：

• AVL 树既是二叉搜索树，也是平衡二叉树，同时满足这两类二叉树的所有性质
• AVL 树是一种平衡二叉搜索树

属性：

• 节点高度
• 节点平衡因子：节点左子树的高度减去右子树的高度，空节点的平衡因子为0

AVL 树旋转：

• 作用：
  • AVL 树的特点在于“旋转”操作，它能够在不影响二叉树的中序遍历序列的前提下，使失衡节点重新恢复平衡
  • 旋转操作既能保持“二叉搜索树”的性质，也能使树重新变为“平衡二叉树”
• 旋转：
  • 左旋
  • 右旋
  • 先左旋再右旋
  • 先右旋再左旋