(10)실습7주차_AVL트리_Bh의 정의,4가지회전,Bh계산,트리회전메소드[문제2]_1

[문제2]의 PDF는 해당 링크로 이동하면 됩니다.

https://kojammin.tistory.com/64

(14)[Chapter6]AVL 트리_삽입 메소드

## 알아야 할 개념 (요약) :

• Bh의 정의 :
• LL,RR ,LR,RL회전 메소드
• 해당 노드에 대하여, Bh값 계산 반환 메소드

1_ Bh의 정의와 4가지 회전 메소드 원리, 코드 노트 정리 :

2_ 해당 노드에 대한 Height(높이)계산 메소드 노트 이론 :

이건 스스로 연습해보자

3_ 해당 노드에 대하여 BH를 계산해주는 메소드 노트 :

 

 

##요약_

• 해당 노드의 Height : Left의 Height vs Right의 Height 중 큰값의 +1

빈노드(NULL)의 Height = 0

단말노드(차수 : 0)의 Height = 1

• 해당 노드의 Bh : Height(Left) - Height(Right)

빈노드(NULL)의 Bh = 0

단말노드(차수 : 0)의 Bh = 0 //Left_Height = 0 - Right_Height =0 == 0

##코드 :

 

//회전 메소드
 
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);
}
 
int GetHeight(BNode* p) 
{
    //1_ 임시변수 height를 0으로 초기화
    int height = 0;
 
    //2_ Case1_ 빈자리일 때, => height 0
    if (p == NULL) {
        return height;
    }
    //3_ Case2_ 빈자리가 아닐 때, 
    //L,R 재귀호출
    int L = GetHeight(p->Left);
    int R = GetHeight(p->Right);
    //둘 중 큰값 + 1;
    return ((L > R) ? L : R) + 1;
}
 
int GetBh(BNode* p) {
    //1_빈자리일 때,
    if (p == NULL) return 0;
    //2_ 빈자리가 아닐 때,
    return GetHeight(p->Left) - GetHeight(p->Right);
}