(11)실습7주차_AVL트리_Rebalance메소드,삽입메소드[문제2]_2

#문제 PDF파일은 아래에 링크 :

https://kojammin.tistory.com/107

(9)실습7주차_이진탐색트리_전위순회,삽입,삭제_이론+코드[문제1]

#알아야 할 개념 :

• Rebalance메소드 :
• ★InsertAVL메소드 :

1. InsertAVL() 코드 논리 순서 (InsertBST()와 비교하기)
2. InsertAVL() 의 중요한 부분

• 빈자리 도달할때 : 메모리 할당, 함수 종료 (다시 루트노드로 재균형조정해야 하기 때문)
• 탐색부분에  재귀InsertAVL + Rebalance()조정 
• 중복된 키가 있을 때, 구현부 작성X (함수 종료도 X)

#ReValance 노트 :

 

#InsertAVL메소드 이론 노트 :

#InsertAVL()메소드 코드 :

#전체 코드 [문제2]:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning (disable : 4996)
 
typedef struct _AVLBTree {
 
    int data;
    struct _AVLBTree* Left;
    struct _AVLBTree* Right;
 
}BNode;
 
//회전 메소드
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(R1);
    return RR(R1);
}
 
//해당 노드에 대한 높이 구하는 메소드
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;
}
 
//해당 노드에 대한 Bh를 구하는 메소드
int GetBH(BNode* p) 
{
    if (p == NULL) return 0;
 
    return GetHeight(p->Left) - GetHeight(p->Right);
}
 
BNode* rebalance(BNode** p) 
{
    int BH = GetBH(*p);
 
    if (BH > 1) {//LL LR
 
        int L2_BH = GetBH((*p)->Left);
 
        if (L2_BH > 0) //L
        {
            *p = LL(*p);
        }
        else if(L2_BH <0)
        {
            *p = LR(*p);
        }
 
    }
    else if (BH<-1) //RR RL
    {
        int R2_BH = GetBH(*p);
 
        if (R2_BH<0) //RR
        {
            *p = RR(*p);
        }
        else if(R2_BH < 0)
        {
            *p = RL(*p);
        }
    }
 
    return *p;
}
 
BNode* SearchBSTree(BNode* tree, int data)
{
    if (tree == NULL) return NULL;
 
    if (tree->data > data)
    {
        return SearchBSTree(tree->Left, data);
    }
    else if (tree->data < data)
    {
        return SearchBSTree(tree->Right, data);
    }
    else return tree;
 
}
 
//삽입 메소드
BNode* InsertAVL(BNode** p, int data) {
    if ((*p) == NULL) {
        (*p) = (BNode*)malloc(sizeof(BNode));
        (*p)->data = data;
        (*p)->Left = NULL;
        (*p)->Right = NULL;
    }
    else if ((*p)->data > data) {
        (*p)->Left = InsertAVL(&((*p)->Left), data);
    }
    else if ((*p)->data < data) {
        (*p)->Right = InsertAVL(&((*p)->Right), data);
    }
    else {
        printf("data가 이미 트리안에 존재합니다.\n");
        return *p;
    }
 
    // 삽입 후, 균형을 맞춘 후 결과를 반환해야 함
    return rebalance(p);
}
 
 

##참고 : InsertAVL() void 반환형 코드 :

//InsertAVL()메소드
void InsertAVL(BNode** p, int data) 
{
    //1_빈자리 도달 시, 할당 삽입 => 함수종료(x)
    if ((*p) == NULL) 
    {
        (*p) = (BNode*)malloc(sizeof(BNode));
        (*p)->data = data;
        (*p)->Left = NULL;
        (*p)->Right = NULL;
    }
    else 
    {
        //2_탐색 : 재귀
        if ((*p)->data > data) 
        {
            InsertAVL(&((*p)->Left), data);
 
        }
        else if ((*p)->data<data) 
        {
            InsertAVL(&((*p)->Right), data);
        }
        //이거 한번 실험 해보자(중복된 키가 있을 시 처리)
    }
    //3_ 거슬러 올라오면서, Rebalance로 균형조정
    if ((*p) != NULL) 
    {
        (*p) = Rebalance(p);
    }
 
    return;
}