알고리즘 공부 <7> - 이진 탐색 트리 , AVL 트리

이번에는 지난번에 본 이진 트리를 이어서 이진 탐색 트리를 공부해 보겠습니다.

1. 트리와 이진 트리

트리는 사이클이 없는 그래프를 말하며 트리와 이진트리의 속성은 그림과 같습니다.

2. 트리 검색 

트리 검색을 공부하는데 있어 공부할 내용과 미리 알아야 할 내용들이 있습니다. 

트리에 있어 각 오퍼레이션과 앞서 본 트리들의 빅오 입니다. 그리고 트리의 타입을 보면

트리의 타입별 이러한 속성을 지니고 있다는것을 알수 있습니다 그리고 각각 

Degenerate는 빅오 n 

Balanced 는 빅오 lgn

Complete 는 빅오 lgn 인것을 알수 있습니다.

이진 탐색 트리의 속성을 보면 

이러한 속성을 가지고 있습니다

참고로 X와 Y가 같은 경우는 어느쪽에 오든 프로그램의 특성이므로 상관 없습니다.

3. 노드의 진행 과정

노드의 진행과정에는 3가지가 있다. 조금 헷갈리 수 있으니 한 번 집중해서 보자

자 하나씩 살펴보자

Preorder는 루트의 값을 찍는것 즉 값을 읽는 과정은 왼쪽과 오른쪽의 값들을 읽기 전에 루트를 먼저 읽고 그리고 왼쪽과 오른쪽을 읽게 된다. 이는 모든 서브트리에 해당된다  따라서 순서는 위 그림과 같다

Inorder는 루트의 값을 찍는 과정은 왼쪽값을 읽는 과정과 오른쪽값을 읽는 과정 사이에 있다 즉 ( 왼쪽 값 , 루트 , 오른쪽 값 ) 이러한 형태로 있게된다. 이는 모든 서브트리에 해당된다 즉 ( 왼쪽 서브트리 , 루트 , 오른쪽 서브트리 ) 이렇게 읽게 된다.

postorder는 루트의 값을 찍는 과정은 왼쪽값과 오른쪽값을 모두 읽은 후에 읽혀진다. 즉 ( 왼쪽 값 , 루트 , 오른쪽 값 )이 된다 이는 모든 서브트리에도 해당 된다.

4. 탐색

탐색 과정은 쉬우므로 의사코드만 보고넘어가자 

루트가 x 인 서브트리에 대해서 노드 k의 위치를 찾는 과정이다 빅오 n에서 빅오 lgn 이 된다.

또 이렇게 정렬된 이진 트리는 최소값과 최대값을 찾기 굉장히 쉽다.

또 탐색과정 중 하나로 Successor를 찾는 과정이 있다. 굉장히 중요한 과정이다. 

x의 값보다 큰값중에서 가장 작은 값이 successor 가 된다.

이를 트리 구조로 보면

노드 x 의 오른쪽 서브트리에서 가장 왼쪽에 있는 값이 successor가 된다. 

이를 의사코드로 보면

아마 1 ~ 2번 코드는 이해가 될것이다.  

3~6 번 과정이 보통 이해가 안되는데 만약 이진탐색 트리의 구조를 잘 따라 왔다면 이해가 될것이다. 

그림으로 한번 보자

그림에서  값이 4인 노드를 보면  이러한 형태를 띄게된다.   3 <  4   < 6  즉 4에게 있어 successor는 6이다. 이를 찾는 과정을 바로 3~ 6번 과정이라고 보면 되겠다 그래도 이해가 안간다면 다시 공부하는것을 추천한다.

또 이번엔 17을 보자 17은 1~2번과정과 3~6번과정을 거치지 않게 된다. 즉 바로 18이 successor가 된다.

5. 삽입

이진탐색트리의 속성을 알았으니 이번엔 바로 의사코드를 보자

루트부터 해당 위치를 찾을 때까지 아래로 내려가게 된다.  즉 리프노드까지 내려가게 된다. 

이후 x가 널이 되면 리프노드까지 왔다는 소리이다. 그리고 y는 x의 부모 즉 리프노드를 가리키는 포인터가 될것이다.

1.

위 그림에서 보면 x가 21일떄  쭉 내려가게되면 y는 20을 가리키고 x 는 아래로 내려가서 널을 가리키케 된다

이후 11~13 과정에서는 y의 위치를 찾았으니 y를 기준으로 왼쪽과 오른쪽을 넣게 된다.

2.

9~ 11 과정은 그냥 트리가 비워진 상태를 의미한다.

6. 삭제

트리 T에서 z노드를 삭제하려는 의사 코드이다.

삭제는 몇가지 경우를 먼저 생각해줘야한다.

1. 자식이 있는가?  1개? 2개?

2. 자식이 없는가?   0개

이 2가지를 생각해줘야 한다.

하나씩 천천히 보자 그림과 비교해서보자

1.

여기서 7을 삭제하는 경우로 보면

1~3번 라인은 자식이 0 개 이거나 1개 일때 true가 된다.

 4~6번 과정에서 y의 왼쪽 또는 오른쪽 자식의 값을 x에 넣게된다.

이후 7~8번 과정 x의 부모 값에 y의 부모값을 넣어준다. 즉 13의 부모값을 6을 가리키게한다고 보면된다.

그리고 9~ 11 번과정 y의 부모가 널인인지 체크한 널인경우 y가 루트인 경우이다. 이떄는 x가 루트가 된다.

널이 아닌경우 다시 11 ~ 13번 과정에서 현재 y가 부모의 왼쪽 자식인 오른쪽 자식인지를 구별한다. 구별후 y의 부모의 해당위치 자식으로 x를 넣는다

위 과정을 통해 6 번과 13번은 이어졌다 이제 7번을 삭제하면된다.

2.

자식이 0개 일때는 위과정을 전부 거치지 않고ㅓ그냥 y의 해당 위치 자식값은 11 ~ 13 과정에서 null 이 들어가게 되므로 바로 삭제가된다.

3.

자식이 2개 일때는 조금 까다롭다.

z는 18 되는 경우를 보자 

먼저 

z는 18

1 ~ 3 : 자식이 2개이므로 successor 과정을 거치게 된다. y는 20을 가리키게된다.

4~ 6 : y의 왼쪽 또는 오른쪽 자식의 값을 x에 넣게된다. x는 null 이돈다.

7 ~8 : x는 null이므로 스킵

9 ~11: y의 부모는 null아니므로 스킵

11~13: y의 부모에 왼쪽 또는 오른쪽에  x 값을 넣는다. 

14~17: y는 20 z는 18이므로 다르다  따라서 y의값을 z에 넣게 되므로 z는 20이 된다. 이후 18은 제거 된다.

---

1. AVL 트리

AVL트리는 밸런스가 맞춰진 이진탐색 트리라고 할 수 있다. 즉 각 서브트리의 높이의 차의 절대값이 1이하여야 한다.

한번 예를 살펴 보자

위 그림을 보면 불균형 상태일 때 4가지 타입이 있는 것을 알 수 있다.

먼저 싱글 로테이션의 경우를 보면

한번의 로테이션으로 해결이 가능한것을 알 수 있다.

하지만 저런식으로 +2  -> -1  이렇게 부호가 변경되는 것은 2번의 로테이션을 돌아야한다.

B와 A가 로테이션이 일어나고 이후 B와 A가 로테이션이 일어나게된다.

DLR  =  SRR at C  +  SLR at A

이렇게 변경 하게 되면 이후는 이진탐색 트리 와 같은 구조를 같게 된다.

오늘은 이진탐색트리와 간단하게 AVL 트리 구조를 알아 보았다.  

다음 공부는 아마 그래프 일것 같다.