(13)부록_BST트리(이진탐색트리), AVL트리(균형탐색트리) 코드 구별 총정리//시발 더이상 못함

1_ BST의 삽입 메소드 //InsertBST()

//BST 삽입 메소드
void InsertBST(BNode** p, int data) 
{
    if ((*p) == NULL) {
        (*p) = (BNode*)malloc(sizeof(BNode));
        (*p)->data = data;
        (*p)->Left = NULL;
        (*p)->Right = NULL;
 
        return;
    }
 
    if ((*p)->data > data) 
    {
        InsertBST(&((*p)->Left), data);
 
    }
    else if ((*p)->data < data) 
    {
        InsertBST(&((*p)->Right), data);
    }
    else 
    {
        printf("%d가 이미 트리에 중복된 노드로 존재합니다.\n");
        return;
    }
 
}
 

2_ AVL_삽입메소드 //InsertAVL()메소드 :

①. BST 대비 AVL트리 구현부 차이점 :

• BST의 종료조건은 할당 후, return 종료를 하지만, AVL은 할당 후, 종료를 처리하면 안된다.
• BST와 다르게 , AVL은 마지막에 Rebalance(해당 노드 포인터)를 해야한다.

②. AVL_Insert()구현을 위해 필요한 준비물 (4가지 존나 많음) :

• 회전 메소드 : LL RR LR RL
• GetHeight()메소드 : 해당 노드에 대하여, Height를 구하는 메소드
• GetBF() 메소드 : 해당 노드에 대하여, BF를 구하는 메소드
• Rebalance 메소드 : 해당 노드의 BF 검사 후, 적절하게 회전 균형 해주는 메소드

//AVL삽입 메소드
 
//1_ 회전 메소드
BNode* LL(BNode* L1) 
{
    BNode* L2 = L1->Left;
    L1->Left = L2->Right;
    L2->Right = L1;
    return L2;
}
 
BNode* RR(BNode* R1) 
{
    BNode* R2 = R1->Right;
    R1->Right = R2->Left;
    R2->Left = R1;
    return R2;
}
 
BNode* LR(BNode* L1) 
{
    BNode* L2 = L1->Left;
    L1->Left = RR(L2);
    return LL(L1);
}
 
BNode* RL(BNode* R1) 
{
    BNode* R2 = R1->Right;
    R1->Right = LL(R2);
    return RR(R1);
}
 
//2_ getHeight 메소드
int GetHeight(BNode* p) 
{
    int height = 0;
    
    if (p == NULL) 
    {
        return height;
    }
 
    int L = GetHeight(p->Left);
    int R = GetHeight(p->Right);
 
    return (L > R) ? L + 1 : R + 1;
}
 
//3_ getBF()
int GetBF(BNode* p) 
{
    if (p == NULL) return 0;
 
    return GetHeight(p->Left) - GetHeight(p->Right);
}
 
//4_ rebalance
BNode* Rebalance(BNode** p) 
{
    int BF = GetBF((*p));
 
    if (BF > 1) 
    {
        int L2_BF = GetBF((*p)->Left);
 
        if (L2_BF > 0) {
            *p = LL(*p);
        }
        else if(L2_BF<0) 
        {
            *p = LR(*p);
        }
    }
    else if (BF<-1)
    {
        int R2_BF = GetBF((*p)->Right);
 
        if (R2_BF < 0) 
        {
            *p = RR((*p));
        }
        else if(R2_BF>0)
        {
            *p = RL(*p);
        }
    }
 
    return *p;
}
 
//5_ InsertAVL()
void InsertAVL(BNode** p, int data) 
{
    if ((*p) == NULL) 
    {
        *p = (BNode*)malloc(sizeof(BNode));
        (*p)->data = data;
        (*p)->Left = NULL;
        (*p)->Right = NULL;
 
        //return (x)
    }
    else if((*p)->data > data) 
    {
        InsertAVL(&((*p)->Left), data);
    }
    else if ((*p)->data < data) 
    {
        InsertAVL(&((*p)->Right), data);
    }
 
    if ((*p) != NULL) *p = Rebalance(p);
 
    return;
 
}

 

3_ BST의 삭제 메소드_DeleteBST() :

★AVL삽입 메소드와 다르게 종료조건에 return을 해야한다.

기억 해야할 요소 :

• 삭제 대상이 0차 1차일 때, 처리 부분 :

※ 주의 :

삭제 대상 노드 0차 1차 if 조건절을 "if((*p)->Left!=NULL) || if((*p)->Right!=NULL)"로 처리하면, 틀리게 된다.

• 삭제 대상이 2차 노드일 때, 후계자 계승 작업 주의

succ_parent로 케이스 분류 시

- succ_parent != (*p) // succ_parent->Right에 succ->Right를 계승

- succ_parent == (*p) // succ_parent->Left에 succ->Right를 계승

##전체코드 :

//DeleteBST
void DeleteBST(BNode** p , int data) 
{
    if ((*p) == NULL) 
    {
        printf("삭제할 data가 트리에 존재하지 않습니다.\n", data);
 
        return;
    }
 
    if ((*p)->data > data) 
    {
        DeleteBST(&((*p)->Left), data);
    }
    else if ((*p)->data < data) 
    {
        DeleteBST(&((*p)->Right), data);
    }
    else 
    {
        if ((*p)->Left == NULL) 
        {
            BNode* tmp = *p;
            (*p) = (*p)->Right;
            free(tmp);
        }
        else if ((*p)->Right == NULL) 
        {
            BNode* tmp = *p;
            (*p) = (*p)->Left;
            free(tmp);
        }
        else 
        {
 
            BNode* succ_parent = (*p);
            BNode* succ = (*p)->Right;
 
            while (succ->Left != NULL) {
                succ = succ_parent;
                succ = succ->Left;
            }
 
            //실수
            if (succ_parent != *p) 
            {
                succ_parent->Left = succ->Right;
            }
            else 
            {
                succ_parent->Right = succ->Right;
            }
 
            (*p)->data = succ->data;
 
            free(succ);
        }
    }
 
}

4_ AVL트리_삭제 메소드 //DeleteAVL() :

• BST트리_삭제메소드와 마찬가지로,  삭제 대상 0차,1차의 if절 조심
• AVL트리 삭제메소드 대비 차이점 :

①. 삭제 대상이 2차일 때,

BST_Delete() : succ + succ_parent ↘↙

AVL_Delete() :

1. FindMin()노드를 tmp보관
2. 삭제 대상 노드에 tmp->data 업데이트
3. Delete()를 삭제대상 Right에서 다시 재귀해서, tmp노드를 삭제

②. 마지막에 Rebalance처리(BST_Delete()에서는 안함)

//DeleteAVL메소드
 
//1_ FindMin()
BNode* FindMin(BNode* p) 
{
    BNode* tmp = p->Right;
 
    while (tmp->Left != NULL) tmp = tmp->Left;
 
    return tmp;
}
 
//2_ DeleteAVL()
void DeleteAVL(BNode** p , int data)
{
    if ((*p) == NULL) {
        printf("삭제할 data가 트리에 존재하지 않습니다.\n", data);
 
        return;
    }
 
    if ((*p)->data > data) 
    {
        DeleteAVL(&((*p)->Left), data);
    }
    else if ((*p)->data < data) {
        DeleteAVL(&((*p)->Right), data);
    }
    else 
    {
        if ((*p)->Left==NULL&&(*p)->Right==NULL)
        {
            free(*p);
            *p = NULL;
        }
        //실수 if 조건 (*p)!= NULL 또는 (*p)!=NULL로 처리하면, 틀리게됨
        else if ((*p)->Right == NULL)
        {
            BNode* tmp = *p;
            (*p) = (*p)->Right;
            free(tmp);
        }
        else if ((*p)->Left == NULL)
        {
            BNode* tmp = *p;
            (*p) = (*p)->Left;
            free(tmp);
        }
        else 
        {
            BNode* tmp = FindMin(*p);
            (*p)->data = tmp->data;
            //실수
            DeleteAVL(&((*p)->Right), tmp->data);
        }
 
    }
 
    if ((*p) != NULL) {
        (*p) = Rebalance(p);
    }
}