快速理解搜索树系列（一）AVL树

基本概念

• Balanced Binary Tree
• 每个节点的左右子树的高度之差不超过1
• 如果插入和删除节点后高度差大于1，则进行节点旋转，重新维护平衡状态
• 解决了二叉查找树退化成链表的问题，插入、查找、删除的时间复杂度最坏情况是O(logN)，最好情况也是(logN)。

四种不平衡的情况

• 左左 左孩子的左子树出现多出的节点---单旋转
• 左右 左孩子的右子树出现多出的节点---双旋转
• 右左 右孩子的左子树出现多出的节点---双旋转
• 右右 右孩子的右子树出现多出的节点---单旋转

两种旋转方式

• 单旋转，左左和右右。
• 双旋转，左右和右左。

代码实现

• 数据结构

struct TreeNode {
    int val;
    int height;
    struct TreeNode *left;
    struct TreeNode *right;

    TreeNode(int x) :
            val(x), height(0), left(NULL), right(NULL) {
    }
};

• 求树高，空树则返回-1

int height(TreeNode *T) {
    if (T == NULL)
        return -1;
    else
        return T->height;
}

• 两种类型的单旋转

  • 左单旋转

  void singleRotateWithLeft(TreeNode *&T) {
  
      TreeNode *K1 = T->left;
      T->left = K1->right;
      K1->right = T;
  
      T->height = max(height(T->left), height(T->right)) + 1;
      K1->height = max(height(K1->left),height(K1->right)) + 1;
      T = K1;
  
  }
  
  

  • 右单旋转

  void singleRotateWithRight(TreeNode *&T) {
  
      TreeNode *K1 = T->right;
      T->right = K1->left;
      K1->left = T;
  
      T->height = max(height(T->left), height(T->right)) + 1;
      K1->height = max(height((K1->left)), K1->height) + 1;
  
      T = K1;
  
  }
  

• 双旋转

  • 左右双旋转

  void doubleRotateWithRight(TreeNode *&T) {
      singleRotateWithLeft(T->right);
      singleRotateWithRight(T);
  }
  

  • 右左双旋转

  void doubleRotateWithLeft(TreeNode *&T) {
      singleRotateWithRight(T->left);
      singleRotateWithLeft(T);
  }
  

• 节点插入操作

void insert(int val, TreeNode *&root) {
    if (root == nullptr) {
        root = new TreeNode(val);
    } else if (val < root->val) {
        insert(val, root->left);
        if (height(root->left) - height(root->right) == 2)
            if (val < root->left->val)
                singleRotateWithLeft(root);
            else
                doubleRotateWithLeft(root);
    } else if (val > root->val) {
        insert(val, root->right);
        if (height(root->right) - height(root->left) == 2)
            if (val > root->right->val)
                singleRotateWithRight(root);
            else
                doubleRotateWithRight(root);
    }
    root->height = max(height(root->left), height(root->right)) + 1;
}

• 删除操作

void removeVal(int val, TreeNode *&root) {
    if (root == NULL) {
        return;
    }
    if (val < root->val) {
        removeVal(val, root->left);
        if (root->right->left != NULL &&  height(root->right->left) > height(root->right->right)) {
            doubleRotateWithLeft(root);
        } else {
            singleRotateWithLeft(root);
        }

    } else if (val > root->val) {
        removeVal(val, root->right);
        if (2 == height(root->left) - height(root->right)) {
            if (root->left->right != NULL && 2 == (height(root->left->right) > height(root->left->left))) {
                doubleRotateWithRight(root);
            } else {
                singleRotateWithRight(root);
            }
        }
    } else {
        if (root->left && root->right) {
            TreeNode *temp = root->right;
            while (!temp->left) temp = temp->left;
            root->val = temp->val;
            removeVal(root->val, root->right);
            if (height(root->left) - height(root->right) == 2) {
                if (root->left->right != NULL && (height(root->left->right) > height(root->left->left)))
                    doubleRotateWithRight(root);
                else
                    singleRotateWithLeft(root);
            }
        } else {
            TreeNode *temp = root;
            if (!root->left) {
                root = root->right;
            } else if (!root->right) {
                root = root->left;
            }
            delete (temp);
        }
    }
    if (!root) return;
    root->height = max(height(root->left), height(root->right)) + 1;
    return;

}