트리(2) | 이진탐색트리, AVL트리

출처 : book.naver.com/bookdb/book_detail.nhn?bid=10896666

C로 배우는 쉬운 자료구조

 

목차

​

01 트리에 대해

02 이진트리에 대해

03 이진트리의 구현과 순회

04 이진탐색트리, AVL 트리

05 히프

​

03. 이진트리의 구현과 순회

< 순차자료구조(배열) 이용해 이진트리 구현>

​

이진 트리의 노드번호 → 배열의 인덱스로 사용

※ 노드 번호는 1번부터 시작! 0번 비워놓기

​

▷ 노드 i의 부모노드 = ┗ i/2 ┘( i를 2로 나눴을 때 몫!! )

▷ 노드 i의 왼쪽 자식노드 = 2*i

▷ 노드 i의 오른쪽 자식노드= 2*i +1

노드번호와 인덱스의 번호가 4인 노드 9에대해

부모노드는 ┗ 4/2 ┘=2 번 인덱스를 갖는다.

왼쪽 자식노드는 4*2 = 8번 인덱스를, 오른쪽 자식노드는 4*2+1 = 9번 인덱스를 갖는다.

​

< 연결자료구조(포인터) 이용해 이진트리 구현 >

​

이진트리노드를 포인터로 나타내기 위해서는

데이터를 저장하는 데이터 필드,

왼쪽 자식노드를 연결하는 링크필드,

오른쪽 자식노드를 연결하는 링크필드

로 구성되어야한다.

(자식이 없을시 링크필드는 NULL을 가리킨다)

typedef struct Node{ int data; int Node *left; int Node *right; } Node;

​

순차자료구조로 표현한 이진트리를

연결자료구조로 표현해보면 다음과 같다.

​

​

◆ 이진트리순회 : 모든 원소를 빠트리거나 중복하지 않고 처리하는 연산

작업 D : 현재 노드 방문, 처리

작업 L : 현재 노드의 왼쪽 서브 트리로 이동

작업 R : 현재 노드의 오른쪽 서브 트리로 이동

(왼쪽 서브트리에 대한 순회 -> 오른쪽 서브트리에 대한 순회)

​

· 순회 종류

- DLR (전위 순회)

- LDR (중위 순회)

- LRD (후위순회)

​

각 순회를 예시를 들어 나타내보자!

이 식을 이진트리로 나타내면 다음과 같다

① 전위 표기법 - DLR순서

-*A+BC*DE

​

​

② 중위 표기법 - LDR순서

A*B+C-DE*

​

​

③ 후위 표기법 - LRD순서

ABC+*DE*-

​

​

​

04. 이진탐색트리, AVL 트리

◆ 이진탐색트리 : 이진트리를 탐색용 자료구조로 사용하기 위해

원소 크기에 따라 노드 위치를 정의한 것

​

- 모든 원소는 서로 다른 유일한 키를 가짐

- 왼쪽서브트리에 있는 원소들의 키 값 < 루트의 키 값

- 오른쪽서브트리에 있는 원소들의 키 값 > 루트의 키 값

- 왼쪽서브트리 & 오른쪽서브트리 또한 이진탐색트리

· 루트트리에 대해..

이진탐색트리 구조

​

왼쪽서브트리의 키값 (1, 3, 4) < 루트의 키값 (8) < 오른쪽서브트리의 키값 (10, 11, 14)

​

· 왼쪽서브트리에 대해..

왼쪽서브트리의 키값 (1) < 루트의 키값 (3) < 오른쪽서브트리의 키값 (4)

​

· 오른쪽서브트리에 대해..

왼쪽서브트리의 키값 (10) < 루트의 키값 (11) < 오른쪽서브트리의 키값 (14)

​

​

▷ 이진탐색트리의 탐색연산

① 루트에서 시작

② 탐색할 키값 x를 루트노드의 키값 y와 비교

x=y : 원하는 원소 찾음 , 탐색연산 성공

x<y : 루트노드의 왼쪽 서브트리에서 탐색연산 수행

x>y : 루트노드의 오른쪽 서브트리에서 탐색연산 수행

③ 서브트리에 대해서도 순환적으로 탐색연산 수행

→ 시간 복잡도 : O (log N)

​

▷ 이진탐색트리의 삽입연산

① 탐색연산 수행 : 삽입할 원소와 같은 원소 有→ 삽입 불가

② 탐색실패한 위치에 원소 삽입

​

▷ 이진탐색트리의 삭제연산

① 탐색연산 수행 : 삭제할 노드의 위치 알아냄

② 찾은 노드 삭제

③ 이진탐색트리 유지하기 위해 후속처리 필요 ( 이진탐색트리의 재구성 작업)

ⅰ) 삭제할 노드 = 단말노드인 경우 ( 차수=0 )

ⅱ) 삭제할 노드 = 자식노드 1개 가진 경우 ( 차수 = 1)

: 노드삭제시 자식노드=고아 → 후속처리(부모노드 자리를 자식노드에게 물려줌)

ⅲ) 삭제할 노드 = 자식노드 2개 가진 경우 ( 차수 = 2)

: 노드삭제시 자식노드들=고아 → 후속처리(부모노드 자리를 자손노드 中 선택한 후계자에게 물려줌)

​

④ 후계자노드의 원래자리 → 자식노드에게 물려주기

​

※후계자 선택 방법

① inorder predecessor - 왼쪽 서브트리에서 가장 큰 자손 선택

② inorder succesor - 오른쪽 서브트리에서 가장 작은 자손 선택

​

◆ AVL 트리 : 대표적인 균형이진탐색트리, 각 노드에서 | hL(왼쪽 서브트리의 높이) - hR(오른쪽 서브트리의 높이)| =< 1 인 트리

- 왼쪽 서브트리< 부모노드 < 오른쪽 서브트리

- 균형인수(BF,Balance Factor) = hL - hR = { -1, 0, 1 }

AVL 트리

 

▷ AVL 트리의 불균형

ⅰ) LL유형 : 왼쪽으로 치우침

- LL회전 : 오른쪽으로 회전

​

ⅱ) RR유형 : 오른쪽으로 치우침

- RR회전 : 왼쪽으로 회전

​

ⅲ) LR유형 : 왼쪽 서브트리가 치우침

- LR 회전 : LL 유형으로 변환 → LL 회전

​

ⅳ) RL유형 : 오른쪽 서브트리가 치우침

- RL 회전 : RR 유형으로 변환 → RR 회전

​

​

​