平衡二叉樹 AVL

平衡二叉樹 AVL

先弄清楚幾個概念：

1）滿二叉樹：除了葉子節點，都是滿的；

2）完全二叉樹：整體而言，空缺的節點一定是位于樹的右下方；整棵樹的葉子節點最大深度值和最小深度值，相差不會超過1；

3）平衡二叉樹：對于任意一個節點，左子樹和右子樹的高度差不能超過1。

1 平衡因子

通過

平衡因子

可以判斷出是否為平衡二叉樹，這決定了是否需要進行左旋轉或右旋轉操作。

第一步，标注節點的高度；節點的高度=其左右子節點的最大高度值+1；葉子節點的高度為1。

第二步，平衡因子=左右子節點的高度之差。

從上圖中可以看到8,、12節點，平衡因子>1，導緻了不平衡。

标注節點高度和平衡因子的實作：

//傳回高度值
int getHeight(AVLNode<K,V> *node){
	if(node== nullptr)
	    return 0;
    return node->height;//節點高度作為成員變量，初始值為1
}

//獲得節點node的平衡因子
int getBalanceFactor(AVLNode<K,V> *node){
	if(node==nullptr)
    	return 0;
    return getHeight(node->left)-getHeight(node->right);//左右子樹高度之差
}
           

判斷一棵樹的平衡性：

//判斷是否是一顆平衡二叉樹，自頂向下周遊，遞歸算法
bool isBalanced(AVLNode<K,V> *node){
	if(node==nullptr)
	    return true;
    int balanceFactor=getBalanceFactor(node);
    if(std::abs(balanceFactor)>1)//平衡因子>1
        return false;
    return isBalanced(node->left)&&isBalanced(node->right);//左右子樹同時滿足
}
           

2 維護平衡操作

維護的時機：

二叉樹添加一個元素，一定是插入到一個葉子節點。由于新添加了一個節點，才有可能導緻樹失去平衡性。相應地，這個不平衡的節點隻有可能發生從插入的這個位置節點向父親去找。

加入節點後，沿着節點向上維護平衡性。

2.1 右旋轉（以x為旋轉點）

右旋轉的實作：

//右旋轉
AVLNode<K,V> *rightRotate(AVLNode<K,V> *y){
	AVLNode<K,V> *x=y->left;//x是誰？是y的左子樹
    AVLNode<K,V> *T3=x->right;//暫存T3，因為後面要把它接到y節點，作為左子樹
    //向右旋轉
    x->right=y;
    y->left=T3;
    //更新height，先更新y的高度值，因為x是基于y來計算的
    y->height=std::max(getHeight(y->left),getHeight(y->right))+1;
    x->height=std::max(getHeight(x->left),getHeight(x->right))+1;

    return x;
}
           

2.2 左旋轉（以x為旋轉點）

左旋轉的實作：

AVLNode<K,V> *leftRotate(AVLNode<K,V> *y){
    AVLNode<K,V> *x=y->right;
    AVLNode<K,V> *T3=x->left;
    //向左旋轉
    x->left=y;
    y->right=T3;
    //更新height
    y->height=std::max(getHeight(y->left),getHeight(y->right))+1;
    x->height=std::max(getHeight(x->left),getHeight(x->right))+1;

    return x;
}
           

2.3 添加元素在不平衡節點的左側的右側

前面實作的左旋轉和右旋轉，如果新添加的節點位于不平衡節點的左側的左側，就是LL；如果新添加的節點位于不平衡節點的右側的右側，就是RR；

如果新添加的節點位于不平衡節點的左側的右側，就是LR；

以x進行左旋轉；

如果新添加的節點位于不平衡節點的右側的左側，就是RL；

以x進行右旋轉；

平衡性維護實作：

if(balanceFactor>1 && getBalanceFactor(node->left)>=0)
    return rightRotate(node);
//RR
if(balanceFactor<-1 && getBalanceFactor(node->right)<=0)
    return leftRotate(node);
//LR
if(balanceFactor>1 && getBalanceFactor(node->left)<0){
    node->left=leftRotate(node->left);
    return rightRotate(node);
}
//RL
if(balanceFactor<-1 && getBalanceFactor(node->right)>0){
    node->right=rightRotate(node->right);
    return leftRotate(node);
}
           

AVL添加操作實作：

AVLNode<K,V> *add(AVLNode<K,V> *node,K key,V value){
    if(node== nullptr){
        size++;
        return new AVLNode<K,V>(key,value);
    }
    if(key==node->key){
        node->value=value;
    } else if(key<node->key){
        node->left=add(node->left,key,value);
    }else {
        node->right=add(node->right,key,value);
    }
    //更新height
    node->height=1+std::max(getHeight(node->left),getHeight(node->right));
    //計算平衡因子
    int balanceFactor =getBalanceFactor(node);
    //平衡維護
    //LL
    if(balanceFactor>1 && getBalanceFactor(node->left)>=0)
        return rightRotate(node);
    //RR
    if(balanceFactor<-1 && getBalanceFactor(node->right)<=0)
        return leftRotate(node);
    //LR
    if(balanceFactor>1 && getBalanceFactor(node->left)<0){
        node->left=leftRotate(node->left);
        return rightRotate(node);
    }
    //RL
    if(balanceFactor<-1 && getBalanceFactor(node->right)>0){
        node->right=rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}
           

AVL删除操作實作：

// 删除掉以node為根的二分搜尋樹中鍵值為key的節點
// 傳回删除節點後新的二分搜尋樹的根
AVLNode<K,V> *remove(AVLNode<K,V> *node, K key) {
    if (node == nullptr) {
        return nullptr;
    }

    AVLNode<K,V> *retNode=nullptr;
    if (key < node->key) {
        node->left = remove(node->left, key);
        retNode=node;
    } else if (key > node->key) {
        node->right = remove(node->right, key);
        retNode= node;
    } else {
        if (node->left == nullptr) {
            AVLNode<K,V> *rightNode = node->right;
            delete node;
            size--;
            retNode= rightNode;
        }

        else if (node->right == nullptr) {
            AVLNode<K,V> *leftNode = node->left;
            delete node;
            size--;
            retNode= leftNode;
        }
        else{
            AVLNode<K,V> *successor = new AVLNode<K,V>(minimum(node->right));
            //Node *precursor = new Node(maximum(node->right));
            size++;
            successor->right = remove(node->right,successor->key);
            successor->left = node->left;
            //precursor->left = removeMax(node->left);
            //precursor->right = node->right;

            delete node;
            size--;

            retNode= successor;
            //return precursor;
        }
    }
    if(retNode== nullptr)
        return nullptr;
    //更新height
    retNode->height=1+std::max(getHeight(retNode->left),getHeight(retNode->right));
    //計算平衡因子
    int balanceFactor =getBalanceFactor(retNode);
    //平衡維護
    //LL
    if(balanceFactor>1 && getBalanceFactor(retNode->left)>=0)
        return rightRotate(retNode);
    //RR
    if(balanceFactor<-1 && getBalanceFactor(retNode->right)<=0)
        return leftRotate(retNode);
    //LR
    if(balanceFactor>1 && getBalanceFactor(retNode->left)<0){
        retNode->left=leftRotate(retNode->left);
        return rightRotate(retNode);
    }
    //RL
    if(balanceFactor<-1 && getBalanceFactor(retNode->right)>0){
        retNode->right=rightRotate(retNode->right);
        return leftRotate(retNode);
    }
    return retNode;
}