どうやってc++を使ってバランスのとれた二叉樹を実現しますか？

12181 ワード

c++ 二叉の木をバランスさせる AVLの木

一、概要
バランスのとれた二叉の木は以下の性質を持っています。空の木か、左右の二つのサブツリーの高さの差の絶対値は1を超えないで、左右の二つのサブツリーは全部1本のバランスの取れた二叉の木です。このスキームは、二叉検索ツリーをリンクに劣化させる問題をよく解決し、挿入、検索、削除の時間の複雑さを最高の場合と最悪の場合をOに維持します。しかし、頻繁に回転すると、O（logN）ぐらいの時間が挿入と削除されますが、ダブルツリーの場合は時間的に安定しています。

バランスのとれた二叉樹の大部分の操作は、二叉検索ツリーと似ています。主に、挿入削除時のバランスが変化する可能性があり、挿入点からルートノードへの経路上の接合点のバランスだけが変化する可能性があります。
二、二叉の木のバランスが取れていない場合
再バランスが必要な結点をα，任意の2つの結点は最大2人の息子しかいないので、高さがアンバランスな場合、α結点の2つの樹の高さの差2.このアンバランスが次の4つの場合に現れる可能性があります。
1.はいα左息子の左子樹を一度挿入します。
2.はいαの左息子の右子樹を一度挿入します。
3.はいαの右息子の左子樹を一度挿入します。
4.はいα右の息子の右の木を一度挿入します。

状況1と状況4は関係しています。αの鏡像対称、第二のケース2とケース3も関連しています。αの鏡像対称なので、理論的には二つの場合しかないが、プログラミングの角度から見るとまだ四つの場合である。
第一の場合は挿入が「外」の場合（左または右）であり、この場合は一回のシングル回転で調整が完了する。第二の場合は、挿入が「内部」の場合（左右または右左）であり、この場合は複雑であり、二重回転で調整する必要がある。
三、調整措置
3.1、シングル回転

上の図は左の場合、K 2の結点は平衡性を満たしておらず、左のサブツリーk 1は右のサブツリーzより2層深く、k 1のサブツリーの中でより深いのはk 1の左のサブツリーxであるため、左の場合に属する。
バランスを回復するためにxを上に移動してzを下に移動しましたが、この時はAVLツリーの性質要求を超えました。そのために、再び結点を設けて、等価な木を作る。木のバランスを取り戻すために、k 2をこの木のルートノードに変えます。k 2はk 1より大きいので、k 2をk 1の右子樹に置きます。k 1右子樹のYはk 1より大きいです。k 2より小さいです。Yをk 2の左子樹に置くと、二叉ルックアップツリーの性質を満足します。
この場合をシングル回転といいます。
3.2、ダブル回転
左右と右の両方の場合、シングル回転では解決できないので、二回回転します。

上の図の状況については、ツリーのバランスを取り戻すために、2ステップ、1ステップ目、K 1を根に右回り、1回回転すると左回りになりますので、2ステップ目に左回りをもう一回行い、最後にK 2を根にしたバランスの2つの木を得ました。
四、AVLツリーの削除操作
挿入操作と同じように、結点を削除する時にもバランスを崩す可能性があります。これは私達が削除する時にバランスを調整する必要があります。
削除には以下のようなものがあります。
まず、二叉ツリー全体で削除する結点を検索します。検索していない場合は、直接に返さない場合は、以下の操作を行います。
1.削除するノードは、現在のルートノードTである。
左右の木が全部空でなければ。高さの大きいサブツリーで削除操作を実施します。
二つの場合に分けます
（1）左のサブツリーの高さが右のサブツリーの高さよりも大きく、左のサブツリーの最大の要素を現在のルートノードに割り当て、左のサブツリーの中の要素値が一番大きいノードを削除する。
（1）左サブツリーの高さが右サブツリーの高さより小さい場合、右サブツリーの最小要素を現在のルートノードに割り当て、右サブツリーの中の要素値が一番小さいノードを削除する。
左右の子木の中に一つが空であるなら、その非空子樹またはNULLを直接使って、現在のルートノードを置き換えればいいです。
2、削除するノード要素の値は現在のルートノードT値より小さく、左サブツリーから削除されます。
再帰的に呼び出し、左サブツリーで削除を実行します。
これは、現在のルートノードがバランス条件を満たしているかどうかを判断する必要があります。
平衡条件が満たされるなら、現在のルートノードTの高さ情報だけを更新する必要がある。
回転調整が必要です。
Tの左サブノードの左サブツリーの高さがTの左サブノードの右サブツリーの高さより大きい場合、対応するシングル回転が行われる。そうでないとダブル回転します。
3、削除するノード要素値は現在のルートノードT値より大きく、右サブツリーから削除されます。
五、コード実現
Avl Tree.h


#include <iostream>
#include <algorithm>
using namespace std;
#pragma once

//       
template <typename T>
struct AvlNode
{
    T data;
    int height; //      
    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;
    //    
    void Insert(AvlNode<T> *&t, T x);
    //    
    bool Delete(AvlNode<T> *&t, T x);
    //            
    bool Contains(AvlNode<T> *t, const T x) const;
    //    
    void InorderTraversal(AvlNode<T> *t);
    //    
    void PreorderTraversal(AvlNode<T> *t);
    //     
    AvlNode<T> *FindMin(AvlNode<T> *t) const;
    //     
    AvlNode<T> *FindMax(AvlNode<T> *t) const;
private:
    //     
    int GetHeight(AvlNode<T> *t);
    //     
    AvlNode<T> *LL(AvlNode<T> *t);
    //     
    AvlNode<T> *RR(AvlNode<T> *t);
    //      
    AvlNode<T> *LR(AvlNode<T> *t);
    //      
    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;
}


//   
//          
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;
}

//   
//          
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;
}

//   
//     t        
template <typename T>
AvlNode<T> * AvlTree<T>::LR(AvlNode<T> *t)
{
    //              
    // t      RR  ，       LL  
    RR(t->left);
    return LL(t);
}

//   
//     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
        ;//    
    t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
}

template <typename T>
bool AvlTree<T>::Delete(AvlNode<T> *&t, T x)
{
    //t            
    if (t == NULL)
        return false;
    //         
    else if (t->data == x)
    {
        //       
        if (t->left != NULL && t->right != NULL)
        {//                 

            //      ，            ，       
            if (GetHeight(t->left) > GetHeight(t->right))
            {
                t->data = FindMax(t->left)->data;
                Delete(t->left, t->data);
            }
            else//       ，            ，       
            {
                t->data = FindMin(t->right)->data;
                Delete(t->right, t->data);
            }
        }
        else
        {//          ，                  
            AvlNode<T> *old = t;
            t = t->left ? t->left: t->right;//t         
            delete old;
        }
    }
    else if (x < t->data)//           
    {
        //           
        Delete(t->left, x);
        //            
        if (GetHeight(t->right) - GetHeight(t->left) > 1)
        {
            if (GetHeight(t->right->left) > GetHeight(t->right->right))
            {
                //RL   
                t = RL(t);
            }
            else
            {//RR   
                t = RR(t);
            }
        }
        else//             
        {
            t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
        }
    }
    else//           
    {
        //         
        Delete(t->right, x);
        //      
        if (GetHeight(t->left) - GetHeight(t->right) > 1)
        {
            if (GetHeight(t->left->right) > GetHeight(t->left->left))
            {
                //LR   
                t = LR(t);
            }
            else
            {
                //LL   
                t = LL(t);
            }
        }
        else//          
        {
            t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
        }
    }

    return true;
}

//    
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 << "          (-1  )：" << endl;
    while (cin >> value)
    {
        if (value == -1)
            break;
        tree.Insert(tree.root,value);
    }
    cout << "    ";
    tree.InorderTraversal(tree.root);
    cout << "
    :";
    tree.PreorderTraversal(tree.root);
    cout << "
         ：";
    cin >> tmp;
    if (tree.Contains(tree.root, tmp))
        cout << "    " << endl;
    else
        cout << "  " << tmp << "      " << endl;
    cout << "         ：";
    cin >> tmp;
    tree.Delete(tree.root, tmp);
    cout << "        ：";
    tree.InorderTraversal(tree.root);
    cout << "
        ：";
    tree.PreorderTraversal(tree.root);
}

テスト結果

以上はc++を使って、バランスのとれた二叉樹を実現するための詳細な内容です。c++バランス二叉樹に関する資料は他の関連記事に注目してください。