[자료구조] 12강 이진 탐색 트리, 선택 트리, 포리스트, 이진 트리의 개수 계산

* 이진 탐색 트리

 

1.소개

이진 탐색 트리는 임의의 키를 가진 원소를 삽입, 삭제, 검색하는데 효율적인 자료구조로 모든 연산은 킷값을 기초로 실행된다.

이진 탐색 트리는 이진 트리이며 공백이 아니면 모든 원소는 상이한 키를 갖는다.

왼쪽 서브 트리 원소들의 키가 루트의 키보다 작고 오른쪽 서브 트리 원소들의 키는 루트의 키보다 큰 값들을 가진다.

 

2.이진 탐색 트리의 탐색

이진 탐색 트리에서 킷값이 X인 원소를 탐색하는 방법은 루트 노드를 시작으로 탐색

이진 탐색 트리가 공백이면 탐색은 종료

탐색하는 노드가 탐색키와 동일한 경우에는 탐색이 성공하고 해당되는 포인터 값을 반환, 반면에 킷값이 동일하지 않으면 현재 노드의 킷값과 탐색 킷값을 비교하여 탐색키가 크면 오른쪽 서브 트리를 탐색하고 탐색키가 작으면 왼쪽 서브 트리를 탐색

 

3.이진 탐색 트리에 대한 삽입

이진 탐색 트리에서 킷값이 X인 새로운 원소를 삽입하는 방법은 가장 먼저 X를 킷값으로 가진 원소가 있는가를 탐색하고 탐색이 실패하면 탐색이 종료된 위치에 원소를 삽입

 

4.이진 탐색 트리에서의 삭제

이진 탐색 트리에서의 원소의 삭제는 킷값을 가진 원소를 탐색하고 원소를 찾으면 삭제 연산을 수행한다.

삭제 연산은 삭제 노드의 자식 수에 따라 세 가지 연산으로 나눌 수 있다. (자식이 없는 단말 노드인 경우, 자식이 하나인 노드의 삭제, 자식이 둘인 노드의 삭제로 각각 구분)

자식이 하나인 노드의 삭제는 삭제되는 노드 자리에 그 자식 노드를 위치시키는 연산 과정

 

5.이진 탐색 트리의 높이

n개의 원소를 갖는 이진 탐색 트리의 높이는 최악의 경우 n이 될 수 있다. 초기 공백인 이진 탐색 트리에 킷값을 순서대로 삽입하는 경우에는 높이가 최악인 경우

이전 탐색 트리의 평균적인 높이는 O(log2n)이 될수록 구성한 탐색 트리를 균형 탐색 트리 (Balanced Search Tree)라고 한다.

 

* 선택트리

 

선택 트리는 승자 트리와 패자 트리로 구분

K개의 런에 나누어진 n개의 원소들을 하나의 순서 순차로 합병하는 것

런이란 원소들이 정렬되어 있는 순차 배열 값이고 각 런의 킷값에 따라 원소들을 오름차순으로 정렬

K개의 런 중에서 가장 작은 킷값을 가진 원소를 순서 순차로 출력

 

* 포리스트

 

1.포리스트의 이진 트리 변환

포리스트란 n>=0개의 분리 트리들의 집합을 의미

포리스트를 이진 트리로 변환하기 위해서는 먼저 각 트리들을 이진 트리로 변환하고 루트 노드들을 형제로 취급하여 sibling필드로 연결

 

2.포리스트 순회

포리스트의 순회는 이진 트리의 순회와 동일

포리스트의 전위 순회는 첫 번째 트리의 루트를 방문하고 첫 번째 트리의 서브 트리들을 포리스트 전위로 순회한 후 나머지 트리들을 포리스트 전위로 순회

포리스트 중위 순회는 첫 번째 트리의 서브 트리들을 포리스트 중위로 순회하고 첫 번째 트리의 루트를 방문한 후 나머지 트리들을 포리스트 중위로 순회

포리스트 후위 순회는 첫 번째 트리의 서브 트리들을 포리스트 후위로 순회하고 나머지 트리들을 포리스트 후위로 순회한 후 첫 번째 트리의 루트를 방문

 

* 이진 트리의 개수 계산

 

상이한 이진 트리

이진 트리에서 원소의 개수 n=0이거나 n=1이면 표현 가능한 트리는 오직 하나뿐이다. n이 2이상이면 표현 가능한 트리의 가짓수는 달라진다.

 

2. 스택 순열

중위 순열 개념을 이용하여 1부터 n까지의 수를 스택에 넣었다가 가능한 모든 방법으로 삭제하여 생성할 수 있는 상이한 순열의 수가 n개의 노들르 가진 상이한 이진 트리의 수와 같다.