AVL树简介 AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis。AVL树是最先发明的自平衡二叉查找树（Self-Balancing Binary Search Tree,简称平衡二叉树）。 一棵AVL树有如下必要条件：条件一：它必须是二叉查找树。条件二：每个节点的左子树和右子树的高度差至多为1。 图一中左边二叉树的节点45的左孩子46比45大，不满足二叉搜索树的条件，因此它也不是一棵平衡二叉树。 右边二叉树满足二叉搜索树的条件，同时它满足条件二，因此它是一棵平衡二叉树。 左边二叉树的节点45左子树高度2，右子树高度0，左右子树高度差为2-0=2，不满足条件二；右边二叉树的节点均满足左右子树高度差至多为1，同时它满足二叉搜索树的要求，因此它是一棵平衡二叉树。 AVL树的查找、插入、删除操作在平均和最坏的情况下都是O（logn），这得益于它时刻维护着二叉树的平衡。但由于每次插入都需要不断的调整和维护，所以，实际上如果插入操作次数太多则同样会陷入超时的死局，最具优势的操作在于查找，因为它的底层设计使得它无论插入多少个元素，这颗二叉树总是严格平衡的，所以AVL树适用于插入操作不是很频繁，但查找操作极度频繁的情况，如果需要在插入和查找操作找一个均衡点，那么就只能选择红黑树了。AVL树的相关概念 平衡因子：将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor)。 在图二右边的AVL树上： 节点50的左子树高度为3，右子树高度为2，BF= 3-2 = 1； 节点45的左子树高度为2，右子树高度为1，BF= 2-1 = 1； 节点46的左子树高度为0，右子树高度为0，BF= 0-0 = 0； 节点65的左子树高度为0，右子树高度为1，BF= 0-1 = -1； 对于平衡二叉树，BF的取值范围为[-1,1]。如果发现某个节点的BF值不在此范围，则需要对树进行调整。 最小不平衡树：距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树。 在图三中，左边二叉树的节点45的BF = 1，插入节点43后，节点45的BF = 2。节点45是距离插入点43最近的BF不在[-1,1]范围内的节点，因此以节点45为根的子树为最小不平衡子树。(这正好对应了递归的后序返回操作 中序的前驱和后继：顾名思义，就是中序遍历下的前一个结点和后一个结点，由于时二叉搜索树，所以中序遍历的前一个结点对应比这个结点小的最大结点，而后一个结点对应比这个结点大的最小结点。(这个可以看后面代码再进行理解)这个概念在进行删除结点的操作时很有用，因为删除结点后需要同时保证仍然为二叉搜索树。 关于对前驱和后继的一些寻找方法，请看我的另一篇博客：面试题 04.06. 后继者AVL树的实现详解 总体思维导图实现。 1. 结点结构struct node { int val; int depth; node *lchild; node *rchild; node() : val(0), lchild(nullptr), rchild(nullptr) {} node(int x) : val(x), lchild(nullptr), rchild(nullptr) {} }; val，结点的值。depth，该结点的高度(它的左右子树中最高的高度+1)。lchild，左孩子。rchild，右孩子。2. AVL树的抽象数据结构（ADT）class AVLTree { /*date part*/ node *head; int length; public: /*construct and destruct part*/ AVLTree() : head(nullptr), length(0) {} AVLTree(int x) : head(new node(x)), length(1) {} ~AVLTree() { destroy(head); } public: /*iterator part*/ class iterator {//封装迭代器：内部类--只能调用外部类的静态函数 node *head; node *root; public: iterator(node *head, node *root) : head(head), root(root) {} iterator &operator++(); bool operator==(const iterator &x); bool operator!=(const iterator &x); iterator operator++(int); iterator &operator--(); iterator operator--(int)…