程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> AVL樹單旋轉和雙旋轉算法(c)

AVL樹單旋轉和雙旋轉算法(c)

編輯:關於C語言

要理解這段代碼必須把單旋轉和雙旋轉的算法搞明白。其次,要真正理解遞歸的用法。

[html]
/* 
 * avl tree. 
 */ 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
 
struct AvlNode; 
typedef struct AvlNode *Position; 
typedef struct AvlNode *AvlTree; 
 
struct AvlNode 

    int Element; 
    AvlTree Left; 
    AvlTree Right; 
    int Height; 
}; 
 
int Max(int a, int b)  

    return (a >  b) ? a : b ;     

 
static int HeightAvl(Position P) 

    if (P == NULL) 
    { 
        return -1; 
    } 
    else 
    { 
        return P->Height; 
    } 
 

 
 
static Position SingleRotateWithLeft(Position K2) 

        Position K1; 
 
        K1 = K2->Left; 
        K2->Left = K1->Right; 
        K1->Right = K2; 
 
        K2->Height = Max(HeightAvl(K2->Left), HeightAvl(K2->Right)) +1; 
        K1->Height = Max(HeightAvl(K1->Left), HeightAvl(K2->Right)) +1; 
 
        return K1; 

 
static Position SingleRotateWithRight(Position K2) 

    Position K1; 
 
    K1 = K2->Right; 
    K2->Right = K1->Left; 
    K1->Left = K2; 
 
    K2->Height = Max(HeightAvl(K2->Left), HeightAvl(K2->Right)) +1; 
    K1->Height = Max(HeightAvl(K1->Left), HeightAvl(K2->Right)) +1; 
 
    return K1; 

 
static Position DoubleRotateWithLeft(Position K3) 

    K3->Left = SingleRotateWithRight(K3->Left); 
    return SingleRotateWithLeft(K3); 

 
static Position DoubleRotateWithRight(Position K3) 

    K3->Left = SingleRotateWithLeft(K3->Left); 
    return SingleRotateWithRight(K3); 

 
AvlTree InsertAvl(int X, AvlTree T) 

    if (T == NULL) 
    { 
        T = (AvlTree)malloc(sizeof(AvlTree)); 
        if (T == NULL) 
        { 
            printf("out of space!!!\n"); 
        } 
        else 
        { 
            T->Left = NULL; 
            T->Right = NULL; 
        } 
        T->Element = X; 
        T->Height = 0; 
    } 
    else if (X < T->Element) 
    { 
        T->Left = InsertAvl(X, T->Left); 
         if (HeightAvl(T->Left) - HeightAvl(T->Right) == 2) 
         { 
            if (X < T->Left->Element) 
            { 
                T = SingleRotateWithLeft(T); 
            } 
            else 
            { 
                T = DoubleRotateWithLeft(T); 
            } 
         } 
    } 
    else if (X > T->Element) 
    { 
        T->Right = InsertAvl(X, T->Right); 
        if (HeightAvl(T->Right) - HeightAvl(T->Left) == 2) 
        { 
            if (X > T->Right->Element) 
            { 
                T = SingleRotateWithRight(T); 
            } 
            else 
            { 
                T = DoubleRotateWithRight(T); 
            } 
        } 
    } 
    T->Height = Max(HeightAvl(T->Left), HeightAvl(T->Right)) + 1; 
    return T; 

 
 
int main(void) 

    AvlTree Tree; 
    InsertAvl(1, Tree); 


摘自 angelbosj的專欄

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved