平衡二叉树

平衡二叉树又称AVL树，它要么是一颗空树，要么是具有下列性质的二叉树：

• 它的左子树和右子树都是平衡二叉树，并且高度之差的绝对值不会超过1。

某节点的左子树与右子树的高度差即为该节点的平衡因子。在一棵平衡二叉树中，节点的平衡因子只能取 0 、1 或者 -1。

平衡二叉树的节点结构：

typedef struct AVLNode *Tree;

typedef int ElementType;

struct AVLNode{

    int depth; //深度，这里计算每个节点的深度，通过深度的比较可得出是否平衡

    Tree parent; //该节点的父节点

    ElementType val; //节点值

    Tree lchild;

    Tree rchild;

    AVLNode(int val=0) {
        parent = NULL;
        depth = 0;
        lchild = rchild = NULL;
        this->val=val;
    }
};

增加和删除元素的操作可能需要进行一次或多次树旋转，以实现树的重新平衡。

平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。旋转有左旋和右旋两种处理方式。

对节点进行左旋的操作流程如下：

• 节点的右孩子替代此节点位置；
• 右孩子的左子树变为该节点的右子树；
• 节点本身变为右孩子的左子树。

对节点进行右旋的操作流程如下：

• 节点的左孩子代表此节点；
• 节点的左孩子的右子树变为节点的左子树；
• 将此节点作为左孩子节点的右子树。

查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn）。