EzDoum

찾기
처음으로 | 찾기 | 아카이브 | 글 올리기 | 링크 | 자료실 | 통계 | 연락처 | 자유게시판
이지도움 특집
전체보기
네트워크
TI OMAP35x
TI DaVinci
Analog Blackfin
RobotWar2005
임베디드!
캐쉬의 모든것
메모리 할당 알고리즘
CPU 파이프라이닝
자료구조(Tree)
금융

Login
이름

암호

기억하기


사용자 등록

현재 접속중인 등록 사용자는 0명, 익명 사용자는 2명 입니다.
전체 등록 사용자: 751명

마지막 답장
·libcurl + fuse 조합으로 되는게 많네. (1)
·Linux Ftrace에 관해 (3)
·Android MTP ( Media Transfer Protocol ) (1)
·Lighttpd에 인증을 digest 사용시 IE 오동작 문제? (1)
·Dtrace에 관해 (1)

최근글
·OpenSSL and multi-threads (0)
·ARM 환경에서 OpenCL 사용 (0)
·IoT용 WIFI 모듈 비교 ( MCU ) 클래스 (0)
·Glances - 리눅스 여러 가지 항목을 한 화면에서 모니터링 (0)
·plugin 방식의 로그 분석기 (0)

뜨거운 감자
·나는 인터렉티브한 환경에서 역어셈블 한다. (12)
·GNU REGEX (정규표현식) 프로그래밍 강좌 (7)
·SoCRobotWar 2005 - 신입생 기초 교육자료 (7)
·ASP.NET의 데이터 그리드와 사용자 컨트롤 (7)
·DHTML Editing Control (7)

가장 많이 읽은 글
·[Cache] 2-way Set-Associative 방식이란 무엇일까? (2)
·멀티쓰레드(Pthread) 프로그래밍
·GNU REGEX (정규표현식) 프로그래밍 강좌 (7)
·Sorting Algorithm Animation (2)
·SoCRobotWar 2005 - 신입생 기초 교육자료 (7)

GNU libavl
글쓴이: EzDoum 글쓴날: 2002년 06월 26일 오후 02:35




동적인 자료 구조중에 빠른 검색이 필요하다면 선택되는 것이 균형트리일 것입니다. 이것에 관한 library입니다. 문서와 소스가 아주 깔끔해서 tree의 실제적인 구현을 공부하기 좋은 소스입니다.

Binary search trees provide O(lg n) performance on average for important operations such as item insertion, deletion, and search operations. Balanced trees provide O(lg n) even in the worst case.

GNU libavl is the most complete, well-documented collection of binary search tree and balanced tree library routines anywhere. It supports these kinds of trees:

Plain binary trees:
 Binary search trees
 AVL trees
 Red-black trees

Threaded binary trees:
 Threaded binary search trees
 Threaded AVL trees
 Threaded red-black trees

Right-threaded binary trees:
 Right-threaded binary search trees
 Right-threaded AVL trees
 Right-threaded red-black trees

Binary trees with parent pointers:
 Binary search trees with parent pointers
 AVL trees with parent pointers
 Red-black trees with parent pointers


Online HTML
http://www.msu.edu/user/pfaffben/avl/libavl.html/

ps.
온라인 도움말을 상당히 잘 만들었습니다.

AVL Tree Applet (splay, Red-black, AVL tree)
http://www.seanet.com/users/arsen/avltree.html

tree에 관한 글 모음
http://www.ezdoum.com/search.php?query=tree


C++로 코딩을 한다면 STL을 사용할텐데, C환경이라면 그림에 떡이죠 ^^ 그래서 비슷한 역할을 하는 것을 맹글어 볼까하고 자료를 찾던중에 이미 삽질을 한 사람을 찾아서리...

덕분에 트리에 관한 확실한 예제와 함께 각종 트리의 장단점및 구현에 대해서 잘 공부 할수 있게 됐네요..

아 그리고 한가지더.. 이번에 출시한 VS.net에 포함된 ATL 7.0에서 CRBTree란 템플릿라이브리가 추가 됐는데, 템플릿 형태로 트리만 어떤식으로 구현됐는지 공부하기 좋은 예가 될듯 합니다. ^^

ATL Collection Classes란 주제로 더 찾아 보시면 다른 컨테이너의 예도 볼수 있습니다.

  • 첨부 파일: SNAG-0148.jpg SNAG-0148.jpg (95 KiB(97,459 Bytes))

    [Image Size 680 x 1332]
    SNAG-0148.jpg



  • 관련 링크
  • [분류: C/C++ 인쇄용 페이지 본문 email로 보내기 ]

    <  Tree Rebalancing in Optimal Time and Space | [샤이] 당근과 구리구리송~  >
    GNU libavl | 답장: 3개 | 본문에 답장
    정렬 :  
    답장 EzDoum 2002년 07월 01일 오전 12:28 [ 이글에 답장 | 본문에 답장 | 책갈피 ]
    ● 빨강-검정 나무의 성질 (c로 배우는 알고리즘 - 이재규지음)

    1. 각 외부 노드로 가는 경로의 검정 노드의 수는 같다.
    2. 새로 삽입되는 노드는 빨강 노드이다.
    3. 경로상에 연이어 두 개의 빨강 노드가 나타날 수 없다.(회전 필요)
    4. 부모의 두 자식 노드가 모두 빨강 노드이면 부모는 빨강 노드로 하고 자식은 검정 노드로 바꿀 수 있다. (색상변환)
    5. 루트 노드는 빨강 노드일 수 없다. 검정색으로 바뀜
    6. 빨강 노드는 자식이 없든가 있으면 두 개의 검정 노드여야 한다.
    7. 검정 노드는 자식이 없던가 있으면 하나의 빨강 노드나 두 개의 빨강 노드나 두개의 검정 노드를 가진다. 단 하나의 검정 노드를 자식으로 가질 수 없다.
    --
    걀걀걀...


    [수정]

    답장 EzDoum 2004년 09월 20일 오후 01:10 [ 이글에 답장 | 본문에 답장 | 책갈피 ]
    사이트 주소 바뀜
    http://www.stanford.edu/~blp/avl/index.html
    [수정]

    답장 EzDoum 2004년 12월 22일 오후 04:44 [ 이글에 답장 | 본문에 답장 | 책갈피 ]
    http://byte.csc.lsu.edu/~othmane/projects/programs/csc3102-2.htm
    
    Program 2
    
    
    Write a program to implement the ADT Binary Search Tree and the ADT AVL tree for
    a data record described as:
    
       lname, fname
        50 chars
    
    As always, all programs MUST be modular, structured programs.  You should
    use ADTs for all DS.  You must follow all programming rules.
    
    You will read in master.data and store in each tree.  Then you will read in
    search.dat
    and search for each string in this file.  You will count the search steps by
    counting either the recursion or the
     iteration for each string.  Do not count every step, count only the big O
    steps!!
    
    Example master.dat:
    
    traxler, k
    university, ls
    thornton, billy bob
    
    
    Your output will be a columnar report that lists each string in the search file
    and whether or not it was found,
    how many searches in the bst and how many searches in the AVL tree.
    
                                      Search Report
    
    String          Found      BST             AVL
    s1               Y          22              14
    s2               N          14              18
    s3               Y          32              12
    
    
    You will look at this report and  and turn in a written report giving your
    opinion on the differences between the
     two search counts.  Thhis report does not have to be long, but it must be well
    thought out and well written.
    
    You must hard code the path to the data files in my account, this saves
    space and time for the grader and is a requirement for the program.  IF
    you don't do this the grader will get a segmentation fault when he runs
    the program and you get a zero.
    
    You must use separate files and send a makefile.  In the makefile you
    must name your executable prog.exe
    
    /************************************************************************/
    /*	Name:			Othmane Rahmouni
    	Class:			CSC 3102
    	Assignement:	ADT specifications, Algorithm & Data Structures
    					for Program 2
    	Due Date:		10/09/03
    */
    /************************************************************************/
    
    MAX_LENGTH 50
    
    the data structures:
    
    /* the list record for the BST tree including the alias to the list record to
    	the node
    		char	Name[MAX_LENGTH];
    		Lchild, Rchild;
    	called BST_NODE, BST_NPTR;
    */
    
    /* the list record for the AVL tree including the alias to the list record to
    	the node
    		char	Name[MAX_LENGTH];
    		int		BalFactor;
    		Lchild, Rchild;
    	called BST_NODE, BST_NPTR;
    */
    
    BST_NPTR BsTree;
    AVL_NPTR AvlTree;
    int  status  = 0;
    
    The algorithm:
    
    LEVEL 0
        a)  initialize_BsTree(BsTree);
        b)  initialize_AvlTree(AvlTree);
        c)  status = process_Names(BsTree,AvlTree);
    			if(CONTINUE == status)
        d)  status = process_Searches(BsTree,AvlTree);
        e)  clean_up(BsTree,AvlTree);
    
    
    LEVEL I
       a) initialize_BsTree(BsTree)
           set BsTree to empty
    
       b) initialize_AvlTree(AvlTree)
            set AvlTree to empty
    
       c) process_Names(BsTree,AvlTree)
          open master.data
          if file !exist
           call no_file_error(master.data)
          else
           while(!EOF)
             read name record
             insert name record into BsTree
             insert name record into AvlTree
    
       d) process_Searches(BsTree,AvlTree)
          if(BsTree !empty && AvlTree !empty)
           open search.dat
           if file !exist
             call no_file_error(search.dat)
           else
    			print the headers for the report
    			while(!EOF)
    				read name to be searched
    				search for the name in the BsTree and return the
    number of steps
    				search for the name in the AvlTree and return
    the number of steps
    				print the line specific to this search in the
    report
       e) clean_up(BsTree,AvlTree)
          if(!empty(BsTree))
            destroy_BsTree(BsTree)
          if(!empty(AvlTree))
            destroy_AvlTree(AvlTree)
           
    ADT Specifications:
    
    The Common ADTs for the BsTree and AvlTree:
    	->same create, Destroy, Search
    
      The ADT create tree funtion
        INPUT       the tree
        OUTPUT      the updated tree
        PROCESSING: the tree is set to empty to indicate an empty tree
                  
      The ADT Destroy function
       INPUT       the tree
       OUTPUT      the entire tree is destroyed
       PROCESSING  if the tree is not empty traverse in a postorder way
                    destroying all the nodes in the tree
    
      The ADT Search function
        INPUT      the tree, the key to search for and the StepCounter
        OUTPUT     the updated StepCounter, the tree is unchaged,
    				returns 1 if found 0 if not
        PROCESSING if the tree is not empty then compare the data on the tree to
    				the key. IF the keys are equal then return 1 and
    set the
    				StepCounter to 1
                   Else if the search key is less than the tree key then
                        - process the left side
                        - increment the StepCounter
                   Else if the search key is greater than the tree key then
                        - process the right side
                        - increment the StepCounter
                       
    The Specific ADTs for the BsTree:
                       
      The ADT insert node function for the BST
       INPUT       the tree and the new data to add
       OUTPUT      the updated tree or error routine
       PROCESSING  IF the node does not exist and there is room in the tree
                     output is the updated tree
                   ELSE output is an error message
                  If the tree is empty add the new node
                   Else if the new key is less than the tree's key then
                        process the left side
                   Else if the new key is greater than the tree's key then
                        process the right side
                   Else print there is a duplicate.
                  
    The Specific ADTs for the AvlTree:
    
      The ADT insert node function for the AVLtree
       INPUT       the tree, the new data to add, the unbalanced variable
       OUTPUT      the updated and balanced tree or error routine
       PROCESSING  IF the node does not exist and there is room in the tree
                     output is the updated and balanced tree
                   ELSE output is an error message
                  If the tree is empty add the new node
                   Else if the new key is less than the tree's key then
                        - process the left side
                        - check the unbalanced variable to know if balancing is
    needed
                   Else if the new key is greater than the tree's key then
                        - process the right side
                        - check the unbalanced variable to know if balancing is
    needed
                   Else print there is a duplicate.
                  
     The ADT LeftRoation function for the AVLtree
       INPUT       the tree, the unbalanced variable
       OUTPUT      the updated and balanced tree
       PROCESSING  IF the balance factor of the left child is 1
                     Do a left-left rotation
                   ELSE
    				 Do a left-right rotation
                   Adjust the different balance factor depending on the balance
                   factor of the right child of the left child   
    
     The ADT RightRoation function for the AVLtree
       INPUT       the tree, the unbalanced variable
       OUTPUT      the updated and balanced tree
       PROCESSING  IF the balance factor of the right child is -1
                     Do a right-right rotation
                   ELSE
    				 Do a right-left rotation
                   Adjust the different balance factor depending on the balance
                   factor of the left child of the right child
    
    
    
    /************************************************************
                             CSC 3102
                             Othmane rahmouni
                             Section 1
                             Program 2
                             main.c
    ***************************************************************/
    
    #include "header.h"
    
    
    int main(void)
    {
        BST_NPTR BsTree;
        AVL_NPTR AvlTree;
        int  status  = 0;
    
        Initialize_BsTree(&BsTree);
        Initialize_AvlTree(&AvlTree);
    
        status = process_Names(&BsTree,&AvlTree);
       
       
        if(1 == status)
            status = process_Searches(BsTree,AvlTree);
       
        clean_up(BsTree,AvlTree);
    
        return 0;
    }
    
    
    /************************************************************
                             CSC 3102
                             Othmane rahmouni
                             Section 1
                             Program 2
                             datarecords.h
    ***************************************************************/
    
    #ifndef _HEADER_H
      #define _HEADER_H
    
    /* includes these libraries */
        #include
        #include
        #include
    
    /* define the following limits */
        #define MAX_LENGTH 51
        #define FALSE  0
        #define TRUE  1
    
    /* the datastructure for the BsTree */
    
        typedef struct bst
        {
            char    Name[MAX_LENGTH];
            struct bst *Lchild, *Rchild;   
        }BST_NODE, *BST_NPTR;
    
    /* the datastructure for the AvlTree */
    
        typedef struct avl
        {
            char    Name[MAX_LENGTH];
            int     BalFactor;
            struct  avl *Lchild, *Rchild;  
        }AVL_NODE, *AVL_NPTR;
    
    #endif
    
    
    /************************************************************
                             CSC 3102
                             Othmane rahmouni
                             Section 1
                             Program 2
                             solution.c
    ***************************************************************/
    
    #include "header.h"
    
    
    int process_Names(BST_NPTR *BsTree,AVL_NPTR *AvlTree);
    int process_Searches(BST_NPTR BsTree,AVL_NPTR AvlTree);
    void clean_up(BST_NPTR BsTree,AVL_NPTR AvlTree);
    
    /* 
        The process_Names function
        INPUT       the root of BsTree and the AvlTree
        OUTPUT      the updated root of BsTree and the AvlTree
        PROCESSING: open master.dat
                if file !exist
                    call no_file_error(master.dat)
                else
                    while(!EOF)
                        read name record
                        insert name record into BsTree
                        insert name record into AvlTree
    */
    
    int process_Names(BST_NPTR *BsTree,AVL_NPTR *AvlTree)
    {
       FILE *fpMaster;
       char NewData[51];
       char junk1[51];
       char junk;
       int result = 1;
       int unbalanced;
    
       if( !(fpMaster = fopen("/classes/cs3102/cs3102a/program2/master.dat","r")))
       {
           printf("The file master.dat could not be opened\n");
           result = 0;
       }
       else
       {
          while(fscanf(fpMaster, "%50[^\n]",NewData ) != EOF)
          {
                fscanf( fpMaster,"%c" , &junk);
                if(junk != '\n')
                {
                    fscanf(fpMaster, "%[^\n]",junk1);
                    fscanf( fpMaster,"%c" , &junk);
                }
                InsertBsTree(BsTree, NewData);
                avl_insert(AvlTree, NewData,&unbalanced);
          }
       }
       fclose(fpMaster);
       return result;
    }
    
    /* 
        The process_Searches function
        INPUT       the BsTree and the AvlTree
        OUTPUT      the 2 trees are searched and the report is printed with the
                    result of the searches
        PROCESSING: if(BsTree !empty && AvlTree !empty)
                open search.dat
                if file !exist
                    call no_file_error(search.dat)
                else
                    print the headers for the report
                    while(!EOF)
                        read name to be searched
                        search for the name in the BsTree and return the number of
    steps
                        search for the name in the AvlTree and return the number of
    steps
                        print the line specific to this search in the report
    */
    
    int process_Searches(BST_NPTR BsTree,AVL_NPTR AvlTree)
    {
        FILE *fpSearch;
       char TobeSearched[51];
       char junk;
       char junk1[51];
       int result = 1;
       int BSTfound, AVLfound, BSTcounter, AVLcounter;
       int unbalanced;
       char Found;
    
       if( !(fpSearch = fopen("/classes/cs3102/cs3102a/program2/search.dat","r")))
       {
           printf("The file search.dat could not be opened\n");
           result = 0;
       }
       else
       {
          printf("\n\t\t\t\tSearch Report\n\nString\t\t\tFound\tBST\tAVL\t\n\n");
          while(fscanf(fpSearch, "%50[^\n]",TobeSearched ) != EOF)
          {
                fscanf( fpSearch,"%c" , &junk);
                if(junk != '\n')
                {
                    fscanf(fpSearch, "%[^\n]",junk1);
                    fscanf( fpSearch,"%c" , &junk);
                }
                BSTfound = SearchBsTree(BsTree,TobeSearched, &BSTcounter);
                AVLfound = SearchAvlTree(AvlTree,TobeSearched, &AVLcounter);
    
                if(BSTfound == 1 && AVLfound == 1)
                    Found = 'Y';
                else
                    Found = 'N';
    
                if(strlen(TobeSearched)<8)
                    printf("%s\t\t\t",TobeSearched);
                else
                    printf("%s\t\t",TobeSearched);
                printf("%c\t%d\t%d\n",Found,BSTcounter,AVLcounter);
          }
       }
       fclose(fpSearch);
       return result;
    
    }
    
    /*   The clean_up function
        INPUT       the root of the BsTree and the AvlTree
        OUTPUT      the 2 trees are destroyed
          if(!empty(BsTree))
            destroy_BsTree(BsTree)
          if(!empty(AvlTree))
            destroy_AvlTree(AvlTree)
    */
    
    void clean_up(BST_NPTR BsTree,AVL_NPTR AvlTree)
    {
        if(BsTree != NULL)
            DestroyBsTree(BsTree);
    
        if(AvlTree != NULL)
            DestroyAvlTree(AvlTree);
    
    }
    
    
    /************************************************************
                             CSC 3102
                             Othmane rahmouni
                             Section 1
                             Program 2
                             avl.c
    ***************************************************************/
    
    #include "header.h"
    
    void Initialize_AvlTree(AVL_NPTR *AvlTree);
    void DestroyAvlTree(AVL_NPTR AvlTree);
    int SearchAvlTree(AVL_NPTR AvlTree, char ToBeSearched[], int *StepCounter);
    void avl_insert(AVL_NPTR *parent, char TobeInserted[], int *unbalanced);
    void left_rotation(AVL_NPTR *parent, int *unbalanced);
    void right_rotation(AVL_NPTR *parent, int *unbalanced);
    
    /*The ADT create tree funtion
        INPUT       the tree
        OUTPUT      the updated tree
        PROCESSING: the tree is set to empty to indicate an empty tree*/
         
    void Initialize_AvlTree(AVL_NPTR *AvlTree)
    {
       *AvlTree = NULL;
       return;
    }
    
    /*  The ADT Destroy function
       INPUT       the tree
       OUTPUT      the entire tree is destroyed
       PROCESSING  if the tree is not empty traverse in a postorder way
                    destroying all the nodes in the tree*/
    
    void DestroyAvlTree(AVL_NPTR AvlTree)
    {
       if(NULL != AvlTree)
       { 
           DestroyAvlTree(AvlTree->Lchild);
             DestroyAvlTree(AvlTree->Rchild);
            free(AvlTree);
       }
       return;
    }
    
      /*The ADT Search function
        INPUT      the tree, the key to search for and the StepCounter
        OUTPUT     the updated StepCounter, the tree is unchaged,
                    returns 1 if found 0 if not
        PROCESSING if the tree is not empty then compare the data on the tree to
                    the key. IF the keys are equal then return 1 and set the
                    StepCounter to 1
                   Else if the search key is less than the tree key then
                        - process the left side
                        - increment the StepCounter
                   Else if the search key is greater than the tree key then
                        - process the right side
                        - increment the StepCounter*/
                       
    int SearchAvlTree(AVL_NPTR AvlTree, char ToBeSearched[], int *StepCounter)
    {
    
       int success = 0;
    
       if(NULL != AvlTree)
       {
            if(strcmp(ToBeSearched,AvlTree->Name) == 0)
            {
                *StepCounter = 1;
                success = 1;
            }
            else
            {
                if(strcmp(ToBeSearched,AvlTree->Name) < 0)
                {
                    success = 
    SearchAvlTree(AvlTree->Lchild,ToBeSearched,StepCounter);
                    *StepCounter += 1;
                }  
                else if( strcmp(ToBeSearched,AvlTree->Name) > 0 )
                {
                    success =
    SearchAvlTree(AvlTree->Rchild,ToBeSearched,StepCounter);
                    *StepCounter += 1;
                }
            }
       }
       else
            *StepCounter = 1;
        return success;
    }             
    
    /*  The ADT insert node function for the AVLtree
       INPUT       the tree, the new data to add, the unbalanced variable
       OUTPUT      the updated and balanced tree or error routine
       PROCESSING  IF the node does not exist and there is room in the tree
                     output is the updated and balanced tree
                   ELSE output is an error message
                  If the tree is empty add the new node
                   Else if the new key is less than the tree's key then
                        - process the left side
                        - check the unbalanced variable to know if balancing is
    needed
                   Else if the new key is greater than the tree's key then
                        - process the right side
                        - check the unbalanced variable to know if balancing is
    needed
                   Else print there is a duplicate.*/
             
    void avl_insert(AVL_NPTR *parent, char TobeInserted[], int *unbalanced)
    {
        if (*parent == NULL)
       {
           *unbalanced = TRUE;
            *parent = (AVL_NPTR) malloc(sizeof(AVL_NODE) );
            if (*parent == NULL )
            {
                printf("Error: Out of memory\n");
                exit(1);
            }
            (*parent)->Lchild = (*parent)->Rchild = NULL;
            (*parent)->BalFactor = 0;
            strcpy((*parent)->Name,TobeInserted);
         }
       else
        if (strcmp(TobeInserted,(*parent)->Name) < 0)
         {
             avl_insert(&(*parent)->Lchild, TobeInserted, unbalanced);
            if (*unbalanced)
            {
             /* left branch has grown higher */
              switch ((*parent)->BalFactor)
               {
                 case -1: (*parent)->BalFactor = 0;
                          *unbalanced = FALSE;
                          break;
                 case 0:  (*parent)->BalFactor = 1;
                          break;
                 case 1:  left_rotation(parent, unbalanced);
               } /*  end switch  */
            }
          }      /*  end ifx.key < (*parent)->data.key  */
    
        else
         if (strcmp(TobeInserted,(*parent)->Name) > 0)
          {
              avl_insert(&(*parent)->Rchild, TobeInserted, unbalanced);
             if (*unbalanced)
             {
                       /* right branch has grown higher */
              switch((*parent)->BalFactor)
               {
                 case  1:  (*parent)->BalFactor = 0;
                           *unbalanced = FALSE;
                           break;
                 case  0:  (*parent)->BalFactor = -1;
                           break;
                 case -1:  right_rotation(parent, unbalanced);
                }  /* switch */
             }
           }  /* if x.key > (*parent)->data.key  */
         else
          {
            *unbalanced = FALSE;
            printf("The key is already in the AVL tree\n");
           }  /*  else */
     }  /* avl_insert function  */
    
     /*The ADT LeftRoation function for the AVLtree
       INPUT       the tree, the unbalanced variable
       OUTPUT      the updated and balanced tree
       PROCESSING  IF the balance factor of the left child is 1
                     Do a left-left rotation
                   ELSE
                     Do a left-right rotation
                   Adjust the different balance factor depending on the balance
                   factor of the right child of the left child */ 
    
    void left_rotation(AVL_NPTR *parent, int *unbalanced)
    {
       AVL_NPTR grand_child, child;
    
       child  =  (*parent)->Lchild;
       if (1 == child->BalFactor)
        {      /*   LL rotation   */
          (*parent)->Lchild  =  child->Rchild;
          child->Rchild  =  *parent;
          (*parent)->BalFactor  =  0;
          (*parent)  =  child;
        }        /*  if  LL rotation   */
       else
        {                        /*  LR rotation  */
          grand_child  =   child->Rchild;
          child->Rchild  =  grand_child->Lchild;
          grand_child->Lchild  =  child;
          (*parent)->Lchild = grand_child->Rchild;
           grand_child->Rchild  =  *parent;
      
           switch(grand_child->BalFactor)
            {
              case  1:  (*parent)->BalFactor  =  0;
                        child->BalFactor  =  -1;
                        break;
              case  0:  (*parent)->BalFactor  = child->BalFactor = 0;
                        break;
              case -1:  (*parent)->BalFactor  =  1;
                        child->BalFactor  =  0;
            }    /*   switch  */
           *parent  =  grand_child;
         }  /*   else  LR rotation   */
       (*parent)->BalFactor  =  0;
       *unbalanced  =  FALSE;
    }  /*   function   */
    
     /*The ADT RightRoation function for the AVLtree
       INPUT       the tree, the unbalanced variable
       OUTPUT      the updated and balanced tree
       PROCESSING  IF the balance factor of the right child is -1
                     Do a right-right rotation
                   ELSE
                     Do a right-left rotation
                   Adjust the different balance factor depending on the balance
                   factor of the left child of the right child */
    
    void right_rotation(AVL_NPTR *parent, int *unbalanced)
    {
        AVL_NPTR grand_child, child;
    
       child  =  (*parent)->Rchild;
       if (-1 == child->BalFactor)
        {      /*   RR rotation   */
          (*parent)->Rchild  =  child->Lchild;
          child->Lchild  =  *parent;
          (*parent)->BalFactor  =  0;
          (*parent)  =  child;
        }        /*  if  RR rotation   */
       else
        {                        /*  RL rotation  */
          grand_child  =   child->Lchild;
          child->Lchild  =  grand_child->Rchild;
          grand_child->Rchild  =  child;
          (*parent)->Rchild = grand_child->Lchild;
           grand_child->Lchild  =  *parent;
      
           switch(grand_child->BalFactor)
            {
              case  1:  (*parent)->BalFactor  =  -1;
                        child->BalFactor  =  0;
                        break;
              case  0:  (*parent)->BalFactor  = child->BalFactor = 0;
                        break;
              case -1:  (*parent)->BalFactor  =  0;
                        child->BalFactor  =  1;
            }    /*   switch  */
           *parent  =  grand_child;
         }  /*   else  RL rotation   */
       (*parent)->BalFactor  =  0;
       *unbalanced  =  FALSE;
    }  /*   function   */
    
    
    /************************************************************
                             CSC 3102
                             Othmane rahmouni
                             Section 1
                             Program 2
                             bst.c
    ***************************************************************/
    
    #include "header.h"
    
    void Initialize_BsTree(BST_NPTR *BsTree);
    void DestroyBsTree(BST_NPTR BsTree);
    int SearchBsTree(BST_NPTR BsTree, char ToBeSearched[], int *StepCounter);
    int InsertBsTree(BST_NPTR *BsTree, char ToBeInserted[]);
    
    /*The ADT create tree funtion
        INPUT       the tree
        OUTPUT      the updated tree
        PROCESSING: the tree is set to empty to indicate an empty tree*/
    
    void Initialize_BsTree(BST_NPTR *BsTree)
    {
       *BsTree = NULL;
       return;
    }
                  
    /*  The ADT Destroy function
       INPUT       the tree
       OUTPUT      the entire tree is destroyed
       PROCESSING  if the tree is not empty traverse in a postorder way
                    destroying all the nodes in the tree*/
    
    void DestroyBsTree(BST_NPTR BsTree)
    {
    
        if(NULL != BsTree)
       {
            DestroyBsTree(BsTree->Lchild);
             DestroyBsTree(BsTree->Rchild);
             free(BsTree);
       }
       return;
    }
    
    /*  The ADT Search function
        INPUT      the tree, the key to search for and the StepCounter
        OUTPUT     the updated StepCounter, the tree is unchaged,
                    returns 1 if found 0 if not
        PROCESSING if the tree is not empty then compare the data on the tree to
                    the key. IF the keys are equal then return 1 and set the
                    StepCounter to 1
                   Else if the search key is less than the tree key then
                        - process the left side
                        - increment the StepCounter
                   Else if the search key is greater than the tree key then
                        - process the right side
                        - increment the StepCounter*/
        
    int SearchBsTree(BST_NPTR BsTree, char ToBeSearched[], int *StepCounter)
    {
    
       int success = 0;
    
       if(NULL != BsTree)
       {
            if(strcmp(ToBeSearched,BsTree->Name) == 0)
            {
                *StepCounter = 1;
                success = 1;
            }
            else
            {
                if(strcmp(ToBeSearched,BsTree->Name) < 0)
                {
                    success = 
    SearchBsTree(BsTree->Lchild,ToBeSearched,StepCounter);
                    *StepCounter += 1;
                }  
                else if( strcmp(ToBeSearched,BsTree->Name) > 0 )
                {
                    success = SearchBsTree(BsTree->Rchild,ToBeSearched,StepCounter);
                    *StepCounter += 1;
                }
            }
       }
        return success;
    }
    
    /* The ADT insert node function for the BST
       INPUT       the tree and the new data to add
       OUTPUT      the updated tree or error routine
       PROCESSING  IF the node does not exist and there is room in the tree
                     output is the updated tree
                   ELSE output is an error message
                  If the tree is empty add the new node
                   Else if the new key is less than the tree's key then
                        process the left side
                   Else if the new key is greater than the tree's key then
                        process the right side
                   Else print there is a duplicate.*/
    
    int InsertBsTree(BST_NPTR *BsTree, char ToBeInserted[])
    {
       int success = 0;
      
       if (NULL == *BsTree)
        {
            *BsTree = (BST_NPTR) malloc(sizeof(BST_NODE));
            strcpy((*BsTree)->Name,ToBeInserted);
            (*BsTree)->Lchild = NULL;
            (*BsTree)->Rchild = NULL;
            success = 1;
        }
       else if (strcmp(ToBeInserted,(*BsTree)->Name) <0)
           success = InsertBsTree( &( (*BsTree)->Lchild),ToBeInserted);
       else if (strcmp(ToBeInserted,(*BsTree)->Name) >0)
           success = InsertBsTree( &( (*BsTree)->Rchild),ToBeInserted);
       else if(strcmp(ToBeInserted,(*BsTree)->Name) == 0)
          printf("\n-Insertion failed! %s already exist on the
    BST!!!\n",ToBeInserted);
    
       return success;
    }
    
    /************************************************************************/
    /* makefile */
    /************************************************************************/
    
    prog.exe:   solution.o avl.o bst.o main.o
    	gcc solution.o avl.o bst.o main.o -o prog.exe
    
    solution.o: solution.c header.h
    	gcc -c solution.c
    
    avl.o: avl.c header.h
    	gcc -c avl.c
    	
    bst.o: bst.c header.h
    	gcc -c bst.c
    
    main.o: main.c header.h
    	gcc -c main.c
    
    /************************************************************************/
    /* master.dat */
    /************************************************************************/
    
    earnhardt d
    wallace r
    labonte t
    jarrett d
    parsons b
    squier k
    punch j
    earnhardt d jr
    traxler-richardson boo billy bob roy tom bubba jimmy son eric wanda wichita
    raster
    trickle dick
    spencer j
    speed lake
    wallace m
    grissom s
    martin m
    burton j
    gordon j
    andretti j
    gordon r
    wallace k
    earnhardt k
    jarrett n
    bonnet n
    allison d
    yarborough c
    farmer r
    marcus d
    mcduffie jd
    stricklin hut
    jarret g
    bergrin d
    bodine g
    rudd r
    burton w
    elliott b
    marlin s
    waltrip m
    hamilton b
    musgrave t
    waltrip d
    benson j
    irvan e
    shepherd m
    mayfield j
    petty k
    bodine b
    skinner m
    petty r
    schrader k
    craven r
    mast r
    compe d
    little c
    nemechik j
    sacks g
    pressley r
    green d
    hillin b
    standridge b
    bradberry
    allen l
    bodine t
    parsons p
    dallenbach w
    blind b
    mexican o e
    intimidator
    lajoie r
    green j
    sawyer e
    jones b
    green m
    fedewa t
    sadler e
    mclaughlin m
    sadler h
    dillon m
    lepage k
    park s
    leslie t
    keller j
    fuller j
    reeves s
    allen g
    chapman j
    bessey
    bender t
    barfield r
    hall s
    setzer d
    steele t
    porter r
    reid d
    foster j
    purvis j
    heveron d
    spencer j
    barret s
    robertson j
    spencer e
    krogh m
    mcclure j
    krogh j
    amick l
    wilson r
    fischlein d
    hutto d
    olsen m
    christopehr t
    hillenburg a
    buttke n
    jarrett j
    payne brad
    bown j
    day m
    butler b
    mccarthy j
    taylor d
    miller b
    bickle r
    irwin k
    sauter j
    sprague j
    hensley j
    bliss m
    hornaday r
    rezendes r
    cavelli r
    crawford r
    ruttman j
    rizzo r
    compton s
    george d
    rush l
    roper t
    denton k
    press d
    butler t
    said b
    kirk tammy
    markham c
    reffiner b
    dokken m
    keseowski
    raines t
    allen k
    norick
    dotter b
    macdonald r
    hendrick k
    tolsma r
    cope m
    barfield r
    cook t
    clark tjj
    harwick k
    colabucci m
    bodine b
    cunningham b
    leavy j
    schacht b
    serrano c
    cohen m
    setzer d
    smith d
    hansen s
    brassfield d
    kimmel f
    matlowe g
    hooper l
    renfrow r
    dokken c
    brevak r
    alexander b
    hurlbett m
    tripp p
    belmont a
    buckley t
    kinser m
    genzman a
    richmond t
    kinser s
    briscoe k
    newman r
    glanville j
    spraker j
    mccarthy t
    davis j
    ogle b
    shane d
    spangler t
    giles f
    childress r
    yates r
    mcclure m
    mcreynolds l
    glover t
    pittman r
    gahari r
    sadler e
    roush j
    davis b
    hendrick r
    sabates f
    mccall b
    hedrick l
    bawel d
    gibbs j
    rypien m
    furr t
    hewitt d
    leslie l
    richeson d
    tyson p
    spspenzp p
    parrott b
    hussey c
    penberton r
    graves a
    noffsinger
    beam m
    evernham r
    johns s
    pressley c
    loomis robbie
    wooten t
    reno m
    parrott t
    makar j
    dehart g
    holly h
    brewer t
    fennig j
    kennon g
    andrews p
    ince j
    hillman m
    kennedy b
    fuge d
    long j
    baldwin t
    petree a
    mcswain m
    hamlin k
    buice j
    wingo d
    hayes b
    broome r
    martin g
    richert d
    penberton o
    hammond j
    wood l
    papke b
    amick b
    reiser r
    bessey j
    ruark m
    parker r
    baumgardner b
    geschickter t
    brewer c
    stegall d
    hutto j
    isenhower h
    keller j
    jones b
    labonte k
    baumdardner w
    mills j
    laughlin m
    enders b
    jones j
    reiser r
    hibbard s
    mcleod c
    mcdonald
    browder n
    caldwell k
    johnson d
    smith b
    plattenberger s
    ward w
    strunk k
    hutto j
    erwin j
    campbell k
    pearson r
    nacewicz b
    tutor m
    bodnar r
    tutor m
    mills j
    lauglin m
    bodnar r
    millet c
    hensley h
    walsh j
    hensley j
    walsh f
    neal r
    earnhardt t
    parsons m
    porter e
    finch j
    sadler b
    sutton a
    shoemaker d
    leslie b
    houston s
    mcleod c
    murphy t
    fury t
    nead g
    berry b
    birsch j
    jones s
    buckner j
    pardue e
    shaffer b
    
    
    /************************************************************************/
    /* search.dat */
    /************************************************************************/
    
    tutor m
    earnhardt k
    traxler i
    woofer t
    hensley h
    parsons b
    murph t
    earnhardt d
    wallace r
    labonte t
    jarrett d
    parsons b
    squier k
    punch j
    baker m
    birsch j
    jones s
    buckner j
    pardue e
    shaffer b
    coates h
    traxler-richardson boo billy bob roy tom bubba jimmy son eric wanda wichita
    raster
    java j
    brener n
    ogle b
    shane d
    spangler t
    giles f
    childress r
    yates r
    mcclure m
    kamath s
    ellison l
    stricklin hut
    jarret g
    bergrin d
    bodine g
    rudd r
    burton w
    elliott b
    hillenburg a
    buttke n
    jarrett j
    payne brad
    bown j
    day m
    butler b
    mccarthy j
    taylor d
    potter ml
    zganjar e
    bricker t
    alexander b
    hurlbett m
    tripp p
    belmont a
    buckley t
    kinser m
    genzman a
    richmond t
    kinser s
    briscoe k
    newman r
    
    
    
    
    
    



    [수정]

    GNU libavl | 답장: 3개 | 본문에 답장
    정렬 :  

    답장 쓰기
    글을 올리시려면 로그인 (사용자 등록) 하셔야 합니다.

    검색
    Google

    분류
    ·공지 (6)
    ·인터넷 (87)
    ·하드웨어 (260)
    ·C/C++ (65)
    ·어셈블리 (7)
    ·리눅스 (136)
    ·리눅스 커널 (67)
    ·윈도우즈 (25)
    ·데이터베이스 (20)
    ·보안 (16)
    ·.NET (25)
    ·그래픽 (13)
    ·책소개 (42)
    ·호기심 천국 (80)
    ·잡담 (111)
    ·사랑 (3)

    전체 본문수: 963
    전체 답장수: 525


    분류 : C/C++
    최근글
    최근글
    가장 많이 읽은 글
    ·Sorting Algorithm Animation (2)
    뜨거운 감자
    ·눈으로 보는 자료구조 (5)

    EzDoum투표
    이지도움 어때요?
    이게 뭐야. 다시 안올란다. --;
    아이 좋아라~ +_+;
    관심없다.
    먼가는 있는거 같은데 뭐하는 곳이지?
    기타 (자유게시판에 글로 남겨 주세요)
    [ 결과 | 투표 ]

    랜덤 링크
    http://kldp.net


     Home ^ BACK TO TOP ^ EzDoum - 도움이 필요하세요~??
     Powered by KorWeblog 1.5.8 Copyleft © 2001 EzDoum, 관리자: EzDoum