詳解如何用c++實(shí)現(xiàn)平衡二叉樹

更新時(shí)間：2021年06月11日 12:48:44 作者：zhangbaochong

平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹（有別于AVL算法），由前蘇聯(lián)的數(shù)學(xué)家Adelse-Velskil和Landis在1962年提出的高度平衡的二叉樹，根據(jù)科學(xué)家的英文名也稱為AVL樹。本文介紹了它的原理和如何用C++代碼來實(shí)現(xiàn)

一、概述

平衡二叉樹具有以下性質(zhì)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。這個(gè)方案很好的解決了二叉查找樹退化成鏈表的問題，把插入，查找，刪除的時(shí)間復(fù)雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉(zhuǎn)會(huì)使插入和刪除犧牲掉O(logN)左右的時(shí)間，不過相對(duì)二叉查找樹來說，時(shí)間上穩(wěn)定了很多。

平衡二叉樹大部分操作和二叉查找樹類似，主要不同在于插入刪除的時(shí)候平衡二叉樹的平衡可能被改變，并且只有從那些插入點(diǎn)到根結(jié)點(diǎn)的路徑上的結(jié)點(diǎn)的平衡性可能被改變，因?yàn)橹挥羞@些結(jié)點(diǎn)的子樹可能變化。

二、平衡二叉樹不平衡的情形

把需要重新平衡的結(jié)點(diǎn)叫做α，由于任意兩個(gè)結(jié)點(diǎn)最多只有兩個(gè)兒子，因此高度不平衡時(shí)，α結(jié)點(diǎn)的兩顆子樹的高度相差2.容易看出，這種不平衡可能出現(xiàn)在下面4中情況中：

1.對(duì)α的左兒子的左子樹進(jìn)行一次插入

2.對(duì)α的左兒子的右子樹進(jìn)行一次插入

3.對(duì)α的右兒子的左子樹進(jìn)行一次插入

4.對(duì)α的右兒子的右子樹進(jìn)行一次插入

情形1和情形4是關(guān)于α的鏡像對(duì)稱，二情形2和情形3也是關(guān)于α的鏡像對(duì)稱，因此理論上看只有兩種情況，但編程的角度看還是四種情形。

第一種情況是插入發(fā)生在“外邊”的情形（左左或右右），該情況可以通過一次單旋轉(zhuǎn)完成調(diào)整；第二種情況是插入發(fā)生在“內(nèi)部”的情形（左右或右左），這種情況比較復(fù)雜，需要通過雙旋轉(zhuǎn)來調(diào)整。

三、調(diào)整措施

3.1、單旋轉(zhuǎn)

上圖是左左的情況，k2結(jié)點(diǎn)不滿足平衡性，它的左子樹k1比右子樹z深兩層，k1子樹中更深的是k1的左子樹x，因此屬于左左情況。

為了恢復(fù)平衡，我們把x上移一層，并把z下移一層，但此時(shí)實(shí)際已經(jīng)超出了AVL樹的性質(zhì)要求。為此，重新安排結(jié)點(diǎn)以形成一顆等價(jià)的樹。為使樹恢復(fù)平衡，我們把k2變成這棵樹的根節(jié)點(diǎn)，因?yàn)閗2大于k1，把k2置于k1的右子樹上，而原本在k1右子樹的Y大于k1，小于k2，就把Y置于k2的左子樹上，這樣既滿足了二叉查找樹的性質(zhì)，又滿足了平衡二叉樹的性質(zhì)。

這種情況稱為單旋轉(zhuǎn)。

3.2、雙旋轉(zhuǎn)

對(duì)于左右和右左兩種情況，單旋轉(zhuǎn)不能解決問題，要經(jīng)過兩次旋轉(zhuǎn)。

對(duì)于上圖情況，為使樹恢復(fù)平衡，我們需要進(jìn)行兩步，第一步，把k1作為根，進(jìn)行一次右右旋轉(zhuǎn)，旋轉(zhuǎn)之后就變成了左左情況，所以第二步再進(jìn)行一次左左旋轉(zhuǎn)，最后得到了一棵以k2為根的平衡二叉樹。

四、AVL樹的刪除操作

同插入操作一樣，刪除結(jié)點(diǎn)時(shí)也有可能破壞平衡性，這就要求我們刪除的時(shí)候要進(jìn)行平衡性調(diào)整。

刪除分為以下幾種情況：

首先在整個(gè)二叉樹中搜索要?jiǎng)h除的結(jié)點(diǎn)，如果沒搜索到直接返回不作處理，否則執(zhí)行以下操作：

1.要?jiǎng)h除的節(jié)點(diǎn)是當(dāng)前根節(jié)點(diǎn)T。

如果左右子樹都非空。在高度較大的子樹中實(shí)施刪除操作。

分兩種情況：

(1)、左子樹高度大于右子樹高度，將左子樹中最大的那個(gè)元素賦給當(dāng)前根節(jié)點(diǎn)，然后刪除左子樹中元素值最大的那個(gè)節(jié)點(diǎn)。

(1)、左子樹高度小于右子樹高度，將右子樹中最小的那個(gè)元素賦給當(dāng)前根節(jié)點(diǎn)，然后刪除右子樹中元素值最小的那個(gè)節(jié)點(diǎn)。

如果左右子樹中有一個(gè)為空，那么直接用那個(gè)非空子樹或者是NULL替換當(dāng)前根節(jié)點(diǎn)即可。

2、要?jiǎng)h除的節(jié)點(diǎn)元素值小于當(dāng)前根節(jié)點(diǎn)T值，在左子樹中進(jìn)行刪除。

遞歸調(diào)用，在左子樹中實(shí)施刪除。

這個(gè)是需要判斷當(dāng)前根節(jié)點(diǎn)是否仍然滿足平衡條件，

如果滿足平衡條件，只需要更新當(dāng)前根節(jié)點(diǎn)T的高度信息。

否則，需要進(jìn)行旋轉(zhuǎn)調(diào)整：

如果T的左子節(jié)點(diǎn)的左子樹的高度大于T的左子節(jié)點(diǎn)的右子樹的高度，進(jìn)行相應(yīng)的單旋轉(zhuǎn)。否則進(jìn)行雙旋轉(zhuǎn)。

3、要?jiǎng)h除的節(jié)點(diǎn)元素值大于當(dāng)前根節(jié)點(diǎn)T值，在右子樹中進(jìn)行刪除。

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

AvlTree.h

#include <iostream>
#include <algorithm>
using namespace std;
#pragma once

//平衡二叉樹結(jié)點(diǎn)
template <typename T>
struct AvlNode
{
    T data;
    int height; //結(jié)點(diǎn)所在高度
    AvlNode<T> *left;
    AvlNode<T> *right;
    AvlNode<T>(const T theData) : data(theData), left(NULL), right(NULL), height(0){}
};

//AvlTree
template <typename T>
class AvlTree
{
public:
    AvlTree<T>(){}
    ~AvlTree<T>(){}
    AvlNode<T> *root;
    //插入結(jié)點(diǎn)
    void Insert(AvlNode<T> *&t, T x);
    //刪除結(jié)點(diǎn)
    bool Delete(AvlNode<T> *&t, T x);
    //查找是否存在給定值的結(jié)點(diǎn)
    bool Contains(AvlNode<T> *t, const T x) const;
    //中序遍歷
    void InorderTraversal(AvlNode<T> *t);
    //前序遍歷
    void PreorderTraversal(AvlNode<T> *t);
    //最小值結(jié)點(diǎn)
    AvlNode<T> *FindMin(AvlNode<T> *t) const;
    //最大值結(jié)點(diǎn)
    AvlNode<T> *FindMax(AvlNode<T> *t) const;
private:
    //求樹的高度
    int GetHeight(AvlNode<T> *t);
    //單旋轉(zhuǎn) 左
    AvlNode<T> *LL(AvlNode<T> *t);
    //單旋轉(zhuǎn) 右
    AvlNode<T> *RR(AvlNode<T> *t);
    //雙旋轉(zhuǎn) 右左
    AvlNode<T> *LR(AvlNode<T> *t);
    //雙旋轉(zhuǎn) 左右
    AvlNode<T> *RL(AvlNode<T> *t);
};

template <typename T>
AvlNode<T> * AvlTree<T>::FindMax(AvlNode<T> *t) const
{
    if (t == NULL)
        return NULL;
    if (t->right == NULL)
        return t;
    return FindMax(t->right);
}

template <typename T>
AvlNode<T> * AvlTree<T>::FindMin(AvlNode<T> *t) const
{
    if (t == NULL)
        return NULL;
    if (t->left == NULL)
        return t;
    return FindMin(t->left);
}


template <typename T>
int AvlTree<T>::GetHeight(AvlNode<T> *t)
{
    if (t == NULL)
        return -1;
    else
        return t->height;
}


//單旋轉(zhuǎn)
//左左插入導(dǎo)致的不平衡
template <typename T>
AvlNode<T> * AvlTree<T>::LL(AvlNode<T> *t)
{
    AvlNode<T> *q = t->left;
    t->left = q->right;
    q->right = t;
    t = q;
    t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
    q->height = max(GetHeight(q->left), GetHeight(q->right)) + 1;
    return q;
}

//單旋轉(zhuǎn)
//右右插入導(dǎo)致的不平衡
template <typename T>
AvlNode<T> * AvlTree<T>::RR(AvlNode<T> *t)
{
    AvlNode<T> *q = t->right;
    t->right = q->left;
    q->left = t;
    t = q;
    t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
    q->height = max(GetHeight(q->left), GetHeight(q->right)) + 1;
    return q;
}

//雙旋轉(zhuǎn)
//插入點(diǎn)位于t的左兒子的右子樹
template <typename T>
AvlNode<T> * AvlTree<T>::LR(AvlNode<T> *t)
{
    //雙旋轉(zhuǎn)可以通過兩次單旋轉(zhuǎn)實(shí)現(xiàn)
    //對(duì)t的左結(jié)點(diǎn)進(jìn)行RR旋轉(zhuǎn)，再對(duì)根節(jié)點(diǎn)進(jìn)行LL旋轉(zhuǎn)
    RR(t->left);
    return LL(t);
}

//雙旋轉(zhuǎn)
//插入點(diǎn)位于t的右兒子的左子樹
template <typename T>
AvlNode<T> * AvlTree<T>::RL(AvlNode<T> *t)
{
    LL(t->right);
    return RR(t);
}


template <typename T>
void AvlTree<T>::Insert(AvlNode<T> *&t, T x)
{
    if (t == NULL)
        t = new AvlNode<T>(x);
    else if (x < t->data)
    {
        Insert(t->left, x);
        //判斷平衡情況
        if (GetHeight(t->left) - GetHeight(t->right) > 1)
        {
            //分兩種情況 左左或左右

            if (x < t->left->data)//左左
                t = LL(t);
            else                  //左右
                t = LR(t);
        }
    }
    else if (x > t->data)
    {
        Insert(t->right, x);
        if (GetHeight(t->right) - GetHeight(t->left) > 1)
        {
            if (x > t->right->data)
                t = RR(t);
            else
                t = RL(t);
        }
    }
    else
        ;//數(shù)據(jù)重復(fù)
    t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
}

template <typename T>
bool AvlTree<T>::Delete(AvlNode<T> *&t, T x)
{
    //t為空 未找到要?jiǎng)h除的結(jié)點(diǎn)
    if (t == NULL)
        return false;
    //找到了要?jiǎng)h除的結(jié)點(diǎn)
    else if (t->data == x)
    {
        //左右子樹都非空
        if (t->left != NULL && t->right != NULL)
        {//在高度更大的那個(gè)子樹上進(jìn)行刪除操作

            //左子樹高度大，刪除左子樹中值最大的結(jié)點(diǎn)，將其賦給根結(jié)點(diǎn)
            if (GetHeight(t->left) > GetHeight(t->right))
            {
                t->data = FindMax(t->left)->data;
                Delete(t->left, t->data);
            }
            else//右子樹高度更大，刪除右子樹中值最小的結(jié)點(diǎn)，將其賦給根結(jié)點(diǎn)
            {
                t->data = FindMin(t->right)->data;
                Delete(t->right, t->data);
            }
        }
        else
        {//左右子樹有一個(gè)不為空，直接用需要?jiǎng)h除的結(jié)點(diǎn)的子結(jié)點(diǎn)替換即可
            AvlNode<T> *old = t;
            t = t->left ? t->left: t->right;//t賦值為不空的子結(jié)點(diǎn)
            delete old;
        }
    }
    else if (x < t->data)//要?jiǎng)h除的結(jié)點(diǎn)在左子樹上
    {
        //遞歸刪除左子樹上的結(jié)點(diǎn)
        Delete(t->left, x);
        //判斷是否仍然滿足平衡條件
        if (GetHeight(t->right) - GetHeight(t->left) > 1)
        {
            if (GetHeight(t->right->left) > GetHeight(t->right->right))
            {
                //RL雙旋轉(zhuǎn)
                t = RL(t);
            }
            else
            {//RR單旋轉(zhuǎn)
                t = RR(t);
            }
        }
        else//滿足平衡條件 調(diào)整高度信息
        {
            t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
        }
    }
    else//要?jiǎng)h除的結(jié)點(diǎn)在右子樹上
    {
        //遞歸刪除右子樹結(jié)點(diǎn)
        Delete(t->right, x);
        //判斷平衡情況
        if (GetHeight(t->left) - GetHeight(t->right) > 1)
        {
            if (GetHeight(t->left->right) > GetHeight(t->left->left))
            {
                //LR雙旋轉(zhuǎn)
                t = LR(t);
            }
            else
            {
                //LL單旋轉(zhuǎn)
                t = LL(t);
            }
        }
        else//滿足平衡性 調(diào)整高度
        {
            t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
        }
    }

    return true;
}

//查找結(jié)點(diǎn)
template <typename T>
bool AvlTree<T>::Contains(AvlNode<T> *t, const T x) const
{
    if (t == NULL)
        return false;
    if (x < t->data)
        return Contains(t->left, x);
    else if (x > t->data)
        return Contains(t->right, x);
    else
        return true;
}

//中序遍歷
template <typename T>
void AvlTree<T>::InorderTraversal(AvlNode<T> *t)
{
    if (t)
    {
        InorderTraversal(t->left);
        cout << t->data << ' ';
        InorderTraversal(t->right);
    }
}

//前序遍歷
template <typename T>
void AvlTree<T>::PreorderTraversal(AvlNode<T> *t)
{
    if (t)
    {
        cout << t->data << ' ';
        PreorderTraversal(t->left);
        PreorderTraversal(t->right);
    }
}

main.cpp

#include "AvlTree.h"

int main()
{
    AvlTree<int> tree;
    int value;
    int tmp;
    cout << "請(qǐng)輸入整數(shù)建立二叉樹(-1結(jié)束)：" << endl;
    while (cin >> value)
    {
        if (value == -1)
            break;
        tree.Insert(tree.root,value);
    }
    cout << "中序遍歷";
    tree.InorderTraversal(tree.root);
    cout << "\n前序遍歷:";
    tree.PreorderTraversal(tree.root);
    cout << "\n請(qǐng)輸入要查找的結(jié)點(diǎn)：";
    cin >> tmp;
    if (tree.Contains(tree.root, tmp))
        cout << "已查找到" << endl;
    else
        cout << "值為" << tmp << "的結(jié)點(diǎn)不存在" << endl;
    cout << "請(qǐng)輸入要?jiǎng)h除的結(jié)點(diǎn)：";
    cin >> tmp;
    tree.Delete(tree.root, tmp);
    cout << "刪除后的中序遍歷：";
    tree.InorderTraversal(tree.root);
    cout << "\n刪除后的前序遍歷：";
    tree.PreorderTraversal(tree.root);
}

測(cè)試結(jié)果