[セットトップ]データ構造:バランスツリー

一、定義
バランスツリー(Balanced Binary Tree)はAVLツリー(AVLアルゴリズムとは異なる)とも呼ばれ、1本の空木またはその左右の2つのサブツリーの高さ差の絶対値が1を超えず、左右の2つのサブツリーがバランスツリーであるという性質を有する.バランスツリーの一般的なアルゴリズムとしては,赤黒ツリー,AVL,Treap,伸展ツリーなどがある.
バランスツリーは、二叉ソートツリー(BST)に導入されており、二叉ソートツリーのアンバランスを解決するために時間的複雑度が大幅に低下すると、AVLは(BST)の最適な時間的複雑度O(logn)を保持するので、挿入と削除のたびに二叉ツリーのバランスを確保しなければならない.バランスツリーを図1に示す.
図1(a)バランスツリー(b)非バランスツリー
二、作用
一般的な二叉探索木(Binary Search Tree)については、その所望の高さ(すなわち、1本のバランス木の場合)がlog 2 nであり、その各操作の時間的複雑さ(O(log 2 n))もこれによって決定される.しかし、いくつかの極端な場合(挿入されたシーケンスが秩序化されている場合など)、二叉探索ツリーは近似鎖または鎖に劣化し、この場合、その動作の時間的複雑さは線形、すなわちO(n)に劣化する.このような状況を回避するために、ランダム化により二叉探索ツリーを構築することができるが、複数回の操作を行った後、削除時に削除対象ノードの後続をそれ自体に置き換えることを選択するため、常に右側のノード数が減少し、ツリーが左に沈む.これにより、ツリーのバランスが破壊され、操作の時間的複雑さが低下します.平衡二叉探索木(Balanced Binary Tree)は、1本の空木またはその左右の2つのサブツリーの高さ差の絶対値が1を超えず、左右の2つのサブツリーが1本の平衡二叉木であるという性質を有する.常用アルゴリズムとしては,赤黒樹,AVL,Treap,伸展樹などがある.平衡二叉探索ツリーでは,その高さは一般にO(log 2 n)に良好に維持され,動作の時間的複雑さを大幅に低減することが分かった.
三、ダイナミックバランス技術
1.ダイナミックバランス技術
Adelson-VelskiiとLandisは二叉1を動的に保持することを提案した.動的平衡技術Adelson-VelskiiとLandisは、二叉並べ替えツリーの平衡を動的に維持する方法を提案した.その基本思想は、二叉並べ替えツリーを構築する過程で、一つのノードを挿入するたびに、まず挿入によってツリーの平衡性が破壊されたかどうかを検査し、挿入ノードによってツリーの平衡性が破壊された場合、すると、最小アンバランスサブツリーを見つけ、ソートツリーの特性を維持した上で、最小アンバランスサブツリー内の各ノード間の接続関係を調整して、新しいバランスを達成します.このようにして得られるバランス二叉ソートツリーは、通常、AVLツリーと略称される.
2.最小アンバランスサブツリー
挿入ノードに最も近く、バランス係数の絶対値が1より大きいノードをルートノードとするサブツリー.議論を簡略化するために、二叉ソートツリーの最小アンバランスサブツリーのルートノードがAであると仮定すると、このサブツリーを調整する法則は以下の4つの状況にまとめることができる.
(1)LLタイプ:Aの左の子の左の木に新しいノードXが挿入されています.調整方法は図2(a)を参照してください.図中はBを軸心として、A接点をBの右上からBの右下側に回し、AをBの右子とする.
図2
(2)RR型:Aの右の子の右の木に新しいノードXが挿入されている.調整方法は図2(b)を参照.図中はBを軸心として、A接点をBの左上からBの左下側に回し、AをBの左子とする.(3)LR型:Aの左の子の右の木に新しいノードXが挿入されている.調整方法は図2(c)を参照.第1ステップはXを軸として、BをXの左上からXの左下側に回し、BをXの左子、XをAの左子とする.第2ステップはLL型と同様に処理します(Xを軸にします).(4)RL型:Aの右の子の左の木に新しいノードXが挿入されている.調整方法は図2(d)を参照.2つのステップに分けて行う:第1ステップはXを軸心とし、BをXの右上からXの右下側に回し、BをXの右子、XをAの右子とする.第2ステップはRR型と同様に処理する(Xを軸とすべき).
実際の挿入状況は、図2よりも複雑である可能性があります.A、Bの接点には子木があるかもしれないからです.一例を挙げて説明すると、記録されたキーワードのセットを、図3に示すように、4、5、7、2、1、3、6の順に挿入する.図3において、キーワード3のノードを挿入すると、ノード3に最も近い平衡係数2の祖先がルートノード5であるためである.したがって、第1回目の回転は、ノード4を軸として、ノード2をノード4の左上から左下側に回転させ、ノード5の左の子がノード4であり、ノード4の左の子がノード2であり、元のノード4の左の子がノード2の右の子となる.ステップ2では、さらにノード4を軸にLLタイプで変換します.この挿入とバランス調整の方法はアルゴリズムとプログラムを編成することができ,ここでは議論しない.
図3バランスツリーの構築
3.コード実装
utl.h

#ifndef UTL_H_
#define UTL_H_
/*
 *          ，     
 */
#include <stdio.h>
#include <stdlib.h>

/*    */
inline void *xalloc(int size)
{
    void *p;
    p = (void *)malloc(size);
    /*    */
    if(p == NULL)
    {
        printf("alloc error
");
        exit(1);
    }
    return p;
}
/*    */
#define xfree(p) free(p)

#endif

avl.h

#ifndef AVL_H__
#define AVL_H__
/*
 *avl          
 */
#include <stdio.h>
#include <stdlib.h>

struct AVLTree
{
    unsigned int nData;    /*    */
    struct AVLTree* pLeft;    /*     */
    struct AVLTree* pRight;    /*     */
    int nHeight;    /*     */
};

/*    */
struct AVLTree* insert_tree(unsigned int nData, struct AVLTree* pNode);

/*    ，    1，  ，  0*/
int find_tree(unsigned int data, struct AVLTree* pRoot);

/*    ,      */
void delete_tree(struct AVLTree** ppRoot);

/*    */
void print_tree(struct AVLTree* pRoot);

#endif

avl.c

#include "avl.h"

#include "utl.h"

static int Max(int a, int b);
static int Height(struct AVLTree* pNode);

/*    */
static struct AVLTree* SingleRotateWithLeft(struct AVLTree* pNode);
static struct AVLTree* SingleRotateWithRight(struct AVLTree* pNode);
static struct AVLTree* DoubleRotateWithLeft(struct AVLTree* pNode);
static struct AVLTree* DoubleRotateWithRight(struct AVLTree* pNode);

struct AVLTree* insert_tree(unsigned int nData, struct AVLTree* pNode)
{
    if (NULL == pNode)
    {
        pNode = (struct AVLTree*)xalloc(sizeof(struct AVLTree));
        pNode->nData = nData;
        pNode->nHeight = 0;
        pNode->pLeft = pNode->pRight = NULL;
    }
    else if (nData < pNode->nData)    /*       */
    {
        pNode->pLeft = insert_tree(nData, pNode->pLeft);
        if (Height(pNode->pLeft) - Height(pNode->pRight) == 2)    /*AVL    */
        {
            if (nData < pNode->pLeft->nData)
            {
                /*         ,     */
                pNode = SingleRotateWithLeft(pNode);
            }
            else
            {
                /*         ,     */
                pNode = DoubleRotateWithLeft(pNode);
            }
        }
    }
    else if (nData > pNode->nData)    /*       */
    {
        pNode->pRight = insert_tree(nData, pNode->pRight);
        if (Height(pNode->pRight) - Height(pNode->pLeft) == 2)    /*AVL    */
        {
            if (nData > pNode->pRight->nData)
            {
                /*         ,     */
                pNode = SingleRotateWithRight(pNode);
            }
            else
            {
                /*         ,     */
                pNode = DoubleRotateWithRight(pNode);
            }
        }
    }

    pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;

    return pNode;
}


/*   */
void delete_tree(struct AVLTree** ppRoot)
{
    if (NULL == ppRoot || NULL == *ppRoot)
        return;

    delete_tree(&((*ppRoot)->pLeft));
    delete_tree(&((*ppRoot)->pRight));
    xfree(*ppRoot);
    *ppRoot = NULL;
}

/*            ,       <     <    ,                */
void print_tree(struct AVLTree* pRoot)
{
    if (NULL == pRoot)
        return;

    static int n = 0;


    print_tree(pRoot->pLeft);
    printf("[%d]nData = %u
", ++n, pRoot->nData);
    print_tree(pRoot->pRight);
}

/*
 *    ，    1，  ，  0
 *data       
 *pRoot:avl    
 */
int find_tree(unsigned int data, struct AVLTree* pRoot)
{
    static int k=1;    /*    */
    if (NULL == pRoot)
    {
        printf("not find %d times
", k);
        return 0;
    }

    if(data == pRoot->nData)
    {
        printf("find:%d times
", k);
        return 1;
    }
    else if(data < pRoot->nData)
    {
        ++k;
        return find_tree(data, pRoot->pLeft);
    }
    else if(data > pRoot->nData)
    {
        ++k;
        return find_tree(data, pRoot->pRight);
    }
}

static int Max(int a, int b)
{
    return (a > b ? a : b);
}

/*        */
static int Height(struct AVLTree* pNode)
{
    if (NULL == pNode)
        return -1;

    return pNode->nHeight;
}

/********************************************************************
      pNode pNode->pLeft
      / \
  pNode->pLeft ==> pNode
      \     /
  pNode->pLeft->pRight pNode->pLeft->pRight
 *********************************************************************/
static struct AVLTree* SingleRotateWithLeft(struct AVLTree* pNode)
{
    struct AVLTree* pNode1;

    pNode1 = pNode->pLeft;
    pNode->pLeft = pNode1->pRight;
    pNode1->pRight = pNode;

    /*       ,          */
    pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
    pNode1->nHeight = Max(Height(pNode1->pLeft), pNode->nHeight) + 1;

    return pNode1;
}

/********************************************************************
  pNode pNode->pRight
  \ /
  pNode->pRight ==> pNode
  / \
  pNode->pRight->pLeft pNode->pRight->pLeft
 *********************************************************************/
static struct AVLTree* SingleRotateWithRight(struct AVLTree* pNode)
{
    struct AVLTree* pNode1;

    pNode1 = pNode->pRight;
    pNode->pRight = pNode1->pLeft;
    pNode1->pLeft = pNode;

    /*       ,          */
    pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
    pNode1->nHeight = Max(Height(pNode1->pRight), pNode->nHeight) + 1;

    return pNode1;
}

static struct AVLTree* DoubleRotateWithLeft(struct AVLTree* pNode)
{
    pNode->pLeft = SingleRotateWithRight(pNode->pLeft);

    return SingleRotateWithLeft(pNode);
}

static struct AVLTree* DoubleRotateWithRight(struct AVLTree* pNode)
{
    pNode->pRight = SingleRotateWithLeft(pNode->pRight);

    return SingleRotateWithRight(pNode);
}

テスト関数

#include <stdio.h>

#include <time.h>

#include "avl.h"

int main()
{
    int i,j;
    AVLTree* pRoot = NULL;

    srand((unsigned int)time(NULL));
    
    for (i = 0; i < 10; ++i)
    {
            j = rand();
            printf("%d
", j);
        pRoot = Insert(j, pRoot);
    }

    PrintTree(pRoot);

    DeleteTree(&pRoot);

    return 0;
}

四、参考文献
1、http://sjjg.js.zwu.edu.cn/SFXX/chazhao/chazhao7.3.2.2.html
2、baike.baidu.com/view/593144.htm
3、http://caoruntao.iteye.com/blog/1013550