基本概念

• Balanced Binary Tree
• 每個(gè)節(jié)點(diǎn)的左右子樹的高度之差不超過1
• 如果插入和刪除節(jié)點(diǎn)后高度差大于1，則進(jìn)行節(jié)點(diǎn)旋轉(zhuǎn)，重新維護(hù)平衡狀態(tài)
• 解決了二叉查找樹退化成鏈表的問題，插入乌妙、查找炼绘、刪除的時(shí)間復(fù)雜度最壞情況是O(logN)，最好情況也是(logN)杨何。

四種不平衡的情況

• 左左 左孩子的左子樹出現(xiàn)多出的節(jié)點(diǎn)---單旋轉(zhuǎn)
• 左右 左孩子的右子樹出現(xiàn)多出的節(jié)點(diǎn)---雙旋轉(zhuǎn)
• 右左 右孩子的左子樹出現(xiàn)多出的節(jié)點(diǎn)---雙旋轉(zhuǎn)
• 右右 右孩子的右子樹出現(xiàn)多出的節(jié)點(diǎn)---單旋轉(zhuǎn)

兩種旋轉(zhuǎn)方式

• 單旋轉(zhuǎn)，左左和右右沥邻。
• 雙旋轉(zhuǎn)危虱，左右和右左。

代碼實(shí)現(xiàn)

• 數(shù)據(jù)結(jié)構(gòu)

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;
}

• 兩種類型的單旋轉(zhuǎn)

  • 左單旋轉(zhuǎn)

  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;
  
  }
  
  

  • 右單旋轉(zhuǎn)

  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;
  
  }
  

• 雙旋轉(zhuǎn)

  • 左右雙旋轉(zhuǎn)

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

  • 右左雙旋轉(zhuǎn)

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

• 節(jié)點(diǎn)插入操作

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;

}