색인 - 최적화 데이터 구조 - 균형 이 진 트 리 (avl)

천하 의 문장 은 크게 베껴 쓰 고 있 습 니 다. 최근 에 2 판 검색엔진 을 만 들 고 있 습 니 다. 1 판 보다 많이 개선 되 어야 합 니 다.
먼저 생각 나 는 것 은 데이터 구 조 를 최적화 하려 면 원래 의 '역 렬 색인 - 이 진 트 리' 를http://blog.csdn.net/txgc0/article/details/8697380
이 글 에서 언급 한 이 진 트 리 를 최적화 시 키 는 것 은 모두 가 알 고 있 듯 이 단순 한 이 진 트 리 의 나 쁜 점 은 퇴화 를 두려워 하고 하나의 링크 로 퇴화 한 후에 이 검색 속 도 는 상당히 받 아들 이기 어렵다.
균형 이 잡 힌 이 진 트 리 의 장점 은 시간 복잡 도 를 logN 으로 유지 하고 최 악의 상황 이 발생 하지 않도록 하 는 것 이다.
물론 좋 은 물건 일수 록 귀 찮 습 니 다.
균형 이 잡 힌 이 진 트 리 가 가장 복잡 한 상황 은 나무의 회전 이다.이런 회전 과정 은 인터넷 의 많은 글 을 찾 아 볼 수 있 고 상세 하 게 말 할 수 있 지만 저 는 스스로 그림 을 그 려 서 어떻게 전환 하 는 과정 인지 보 는 것 이 좋 겠 습 니 다.
나 는 어떤 큰 신의 글 을 참고 하여 다음 과 같은 코드 를 얻 은 셈 이다.
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*)xmalloc(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)   
        {
            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)   
        {
            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)
{
	static int n = 0;
    if (NULL == pRoot)
        return;
    
    print_tree(pRoot->pLeft);
    printf("[%d]nData = %u
", ++n, pRoot->nData);
    print_tree(pRoot->pRight);
}

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);
    }
	return 0;
}

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

avl.h

#ifndef __AVL_H__
#define __AVL_H__



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

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

extern int find_tree(unsigned int data, struct AVLTree* pRoot);

void delete_tree(struct AVLTree** ppRoot);

extern void print_tree(struct AVLTree* pRoot);

#endif

main.c

#include <time.h>

#include "avl.h"
#include "utl.h"

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

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

//    PrintTree(pRoot);

 //   DeleteTree(&pRoot);

    return 0;
}

utl.h

#ifndef __UTL_H__
#define __UTL_H__

#include <stdio.h>
#include <stdlib.h>

inline void *xmalloc(int size)
{
    void *p;
    p = (void *)malloc(size);

    if(p == NULL)
    {
        printf("alloc error
");
        exit(1);
    }
    return p;
}
#define xfree(p) free(p)

#endif

나 는 작가 의 노동 성 과 를 존중 해 야 한다. 이 큰 신 이 직접 쓴 것 인지 아 닌 지 는 모 르 겠 지만 나 는 여기 서 보 았 기 때문에 나 는 온 곳 의 링크 를 밝 혀 야 한다.
http://blog.csdn.net/w397090770/article/details/8119616
솔직히 그 는 정말 잘 썼 다.인품 을 늘리다.