[자료구조]CH7. 트리(균형 이진 탐색 트리)

참조 : C로 배우는 쉬운 자료구조 (이지영 저)

공부날짜 : 21.02.20

 

<Section6> 균형 이진 탐색 트리

 

1. 균형 이진 탐색 트리의 개념

 

 높이에 대한 균형 조건을 추가하여 정의한 트리를 균형 이진 탐색 트리 또는 균형 트리라고 한다.

대표적인 예가 AVL트리이다.

 

2. AVL트리의 개념과 유형

 

 각 노드에서 왼쪽 서브 트리의 높이 hL과 오른쪽 서브 트리의 높이 hR의 차이가 1이하인 트리이다. 

* 왼쪽 서브 트리 < 부모 노드 < 오른쪽 서브 트리의 크기 관계

* 각 노드의 서브 트리의 높이의 차이(hL-hR)를 노드의 균형 인수(Balance Factor)라 한다. 

* 각 노드의 균형 인수는 {-1,0,1}의 값만 가지게 하여 균형을 유지한다.

 

균형인수가 양수(+)이면 왼쪽 서브 트리에, 음수(-)이면 오른쪽 서브 트리에 문제가 있는 비AVL트리이다. 

 

3. AVL 트리의 회전 연산

  

 1) LL(Left-Left) 회전 연산

 

  LL 유형 : 불균형 발생 노드의 왼쪽 자식 노드와 자식의 왼쪽 자식 노드에 의해 왼쪽으로 치우침

  LL 회전 : 문제 구간 중 상위 구간을 오른쪽으로 회전시킴

 

 LL_rotate(parent) {

    child=parent->left;

    parent->left=child->right; //왼쪽 자식 노드의 오른쪽 자식 노드를 부모 노드의 왼쪽 자식 노드로 옮김  

    child->right=parent; //부모 노드를 왼쪽 자식 노드의 오른쪽 자식 노드로 옮긴다. 

    return child;

 } 

 end LL_rotate()

 

 2) RR(Right-Right) 회전 연산

 

  RR 유형 : 불균형 발생 노드의 오른쪽 자식 노드와 자식의 오른쪽 자식 노드에 의해 오른쪽으로 치우침

  RR 회전 : 문제 구간 중 상위 구간을 왼쪽으로 회전시킴

 

 RR_rotate(parent) {

    child=parent->right;

    parent->right=child->left; //오른쪽 자식 노드의 왼쪽 자식 노드를 부모 노드의 오른쪽 자식 노드로 옮김  

    child->left=parent; //부모 노드를 오른쪽 자식 노드의 왼쪽 자식 노드로 옮긴다. 

    return child;

 }

 end LL_rotate()

  

3) LR 회전 연산

 

 LR 유형 : 불균형 발생 노드의 왼쪽 자식 노드와 자식의 오른쪽 자식 노드에 의해 왼쪽 서브 트리가 치우침

 LR 회전 : 문제 구간 중 하위 구간을 왼쪽으로 1차 회전시켜 LL 유형으로 변환한 후 LL회전을 적용함

 

LR_rotate(parent) {

   child=parent->left; 

   parent->left = RR_rotate(child); //하위 구간에 RR 회전을 하고 반환된 노드를 부모 노드의 왼쪽 자식 노드로 만든다.

   return LL_rotate(parent); // 상위 구간에 LL 회전 연산을 한다.

 

3) RL 회전 연산

 

 RL 유형 : 불균형 발생 노드의 오른쪽 자식 노드와 자식의 왼쪽 자식 노드에 의해 오른쪽 서브 트리가 치우침

 RL 회전 : 문제 구간 중 하위 구간을 오른쪽으로 1차 회전시켜 RR 유형으로 변환한 후 RR회전을 적용함

 

RL_rotate(parent) {

   child=parent->right; 

   parent->right = LL_rotate(child); //하위 구간에 LL회전을 하고 반환된 노드를 부모노드의 오른쪽 자식 노드로 만든다.

   return RR_rotate(parent); // 상위 구간에 RR 회전 연산을 한다.