트리 / 이진트리 / 완전이진트리 / 이진검색트리

1. 트리란?

- 구성하는 요소는 노드(node)와 가지(edge)로 이루어집니다.

- 데이터 사이의 계층 관계를 나타내는 자료구조

루트 : 트리의 가장 윗부분에 위치하는 노드

리프 : 물리적으로 가장 아랫부분에 위치하는 노드, 끝 노드(terminal node) 또는 바깥 노드(external node)라고도 한다.

안쪽노드 : 루트를 포함하여 리프를 제외한 노드를 안쪽 노드, 끝이 아닌 노드(non-terminal node)라고도 한다.

자식 : 어떤 노드로부터 가지로 연결된 아래쪽 노드를 자식(child)이라고 한다, 리프는 자식을 가질 수 없다.

부모 : 어떤 노드에서 가지로 연결된 위쪽 노드를 부모(parent)라고 한다, 루트는 부모를 가질 수 없다.

형제 : 같은 부모를 가지는 노드를 형제(sibling)

조상 : 어떤 노드에서 가지로 연결된 위쪽 노드 모두를 조상(ancestor)이라고 한다.

자손 : 어떤 노드에서 가지로 연결된 아래쪽 노드 모두를 자손(descendant)이라고 한다.

레벨 : 루트로부터 얼마나 떨어져 있는지에 대한 값을 레벨(level)이라고 한다.

차수 : 노드가 갖는 자식의 수를 차수(degree)이라고 한다, 모든 노드의 자식수가 2개 이하인경우는 특별히 이진트리라고 한다.

높이 : 루트로부터 가장 멀리 떨어진 리프까지의 거리(리프 레벨의 최댓값)을 높이(height)라고 한다.

서브트리 : 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리를 서브트리(subtree)라고 한다.

널트리 : 노드, 가지가 없는 트리를 널 트리(null tree)라고 한다.

순서트리(ordered tree)와 무순서 트리(unordered tree) : 현제 노드의 순서가 있는지 없는지에 따라 트리를 두 종류로 분류한다. 현제 노드의 순서를 따지면 순서트리, 따지지 않으면 무순서 트리

순서 트리 탐색 방법)

1. 너비 우선 탐색(breadth-first Search)

낮은 레벨에서 시작해 왼쪽에서 오른쪽방향을 ㅗ검색하고 한 레벨에서의 검색이 끝나면 다음레벨로 내려간다.

2. 깊이 우선 탐색(depth-first Search)

리프까지 내려가면서 검색하는것을 우선순위로 하는 탐색 방법

리프에 도달해 더 잇아 검색을 진행할 곳이 없는 경우에는 부모에게 돌아갑니다. 그런 다음 다시 자식 노드로 내려갑니다.

---

2. 이진트리

노드가 왼쪽자식과 오른쪽 자식을 갖는 트리를 이진트리(binary tree)라고 한다.

이때 각 노드의 자식은 2명 이하만 유지해야한다.

---

3. 완전 이진트리

루트부터 노드가 채워져있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져있는 이진트리를 완전이진트리(complete binary tree)라고 한다.

 1) 마지막 레벨을 제외한 레벨은 노드를 가득 채웁니다.

 2) 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 채우되 반드시 끝까지 채울 필요는 없습니다.

높이가 $k$인 완전 이진트리가 가질 수 있는 노드의 최댓값은 $2^{k+1}-1$개 입니다. 따라서 $n$개의 노드를 저장할 수 있는 완전이진트리의 높이는 $log n$입니다.

---

4.이진검색트리 만들기

조건)

 1) 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 한다.

 2) 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야한다.

 3) 같은 키 값을 갖는 노드는 없다.

- search 메서드 알고리즘 동작 방식)

 1) 루트부터 선택하여 검색을 진행. 여기서 선택하는 노드를 p라고 한다.

 2) p가 null이면 검색에 실패

 3) 검색하는 값 key와 선택한 노드 p의 키 값을 비교

  a. 값이 같으면 검색에 성공(검색 종료)

  b. key가 작으면 선택한 노드에 왼쪽 자식 노드를 대입(왼쪽으로 검색 진행)

  c. key가 크면 선택한 노드에 오른쪽 자식 노드를 대입(오른쪽으로 검색 진행)

 4) 2번 과정으로 되돌아감

search 메서드 코드 :

- 노드를 삽입하는 add 메서드 동작방식)

 1) 루트를 선택한다. 여기서 선택한 노드를 node로 한다.

 2) 삽입할 키 key와 선택 노드 node의 키 값을 비교한다. 값이 같다면 삽입에 실패(종료)

  a. 값이 같지 않은 경우 key값이 삽입할 값보다 작으면

   - 왼쪽 자식 노드가 없는경우에는 노드를 삽입(종료)

   - 왼쪽 자식 노드가 있는 경우에는 선택한 노드를 왼쪽 자식 노드로 옮김

  b. key값이 삽입할 값보다 크면

   - 오른쪽 자식 노드가 없는 경우에는 노드를 삽입(종료)

   - 오른쪽 자식 노드가 있는 경우에는 선택한 노드를 오른쪽 자식 노드로 옮김

 3) 2번으로 되돌아감

add 메서드 코드 :

- 노드를 삭제하는 remove 메서드)

 1) 자식 노드가 없는 노드를 삭제하는 경우

  - 삭제할 노드가 부모 노드의 왼쪽 자식이면 부모의 왼쪽 포인터를 null로 처리

  - 삭제할 노드가 부모 노드의 오른쪽 자식이면 부모의 오른쪽 포인터를 null로 처리

 2) 자식 노드가 1개인 노드를 삭제하는 경우

  - 삭제 대상 노드가 부모 노드의 왼쪽 자식이면 부모의 왼쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 한다.

  - 삭제 대상 노드가 부모 노드의 오른쪽 자식이면 부모의 오른쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 한다.

 3) 자식 노드가 2개인 노드를 삭제하는 경우

  - 삭제할 노드의 왼쪽 서브 트리에서 키 값이 가장 큰 노드를 검색

  - 검색한 노드를 삭제 위치로 옮긴다.(검색한 노드의 데이터를 삭제 대상 노드 위치로 복사)

  - 옮긴 노드를 삭제, 이때

   - 옮긴 노드에 자식이 없으면 : '자식 노드가 없는 노드의 삭제 순서'에 따라 노드를 삭제

   - 옮긴 노드에 자식이 1개만 있으면 : '자식 노드가 1개 있는 노드의 삭제 순서'에 따라 노드를 삭제

remove 메서드 코드 :

모든 노드를 출력하는 print 메서드 동작방식)

 1) 루트 왼쪽 첫번째 자식를 가리키는 왼쪽 포인터를 printSubTree 메서드에 전달하면서 재귀적으로 호출(재귀)

 2) 현재 노드의 데이터인 루트를 출력

 3) 루트 오른쪽 첫번째 자식을 가리키는 오른쪽 포인터를 printSubTree 메서드에 전달하면 재귀적으로 호출(재귀)

print 메서드 코드 :

풀코드) (출처 : 출판사 자료실)

- BinTree :

- BinTreeTester :