이진트리(Binary Tree) & 이진탐색트리(Binary Search Tree)

이진트리(Binary Tree) & 이진 탐색 트리(Binary Search Tree)

 

이진트리(Binary Tree)

• 모든 노드들이 둘 이하의 자식을 가진 트리이다.

이진트리 유형

전 이진트리(Full Binary Tree)

• 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.

완전 이진트리(Complete Binary Tree)

• 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리이다.
• 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
• 마지막 레벨 h에서 1 ~ 2h - 1개의 노드를 가질 수 있다.
• 완전 이진트리는 배열을 사용해 효율적으로 표현이 가능하다.

포화 이진트리(Perfect Binary Tree)

• 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖는다.
• 노드 개수가

  

  공식으로 계산된다.
  • 예) 높이가 3인 포화 이진트리는 노드 개수가

    

    이다.
• 이진 트리에는 번호를 부여할 수 있는데, 루트 노드 부터 왼쪽에서 오른쪽으로 번호를 부여한다.

균형 이진트리(Balanced Binary Tree)

• 왼쪽과 오른쪽 트리의 높이 차이가 모두 1만큼 나는 트리이다. (AVL, Red-Black 트리는 균형 이진트리이다.)

SMALL

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리는 이진트리이면서 아래와 같은 속성을 갖는 트리를 뜻한다.

• 각 노드에 중복되지 않는 키(key)가 있다.
• 루트 노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
• 루트노드의 오른쪽 서브트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
• 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.

이진 탐색 트리의 탐색

1. 루트 노드의 키와 찾고자 하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료한다.
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.
3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브트리로 탐색을 진행한다.

이진 탐색 트리의 삽입

1. 삽입할 값을 루트 노드와 비교해 같다면 오류를 발생한다. (중복 값 허용 X)
2. 삽입할 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리를 탐색해서 비어있다면 추가, 비어있지 않다면 다시 값을 비교한다.
3. 삽입할 값이 루트 노드의 키보다 크다면 오른쪽 서브트리를 탐색해서 비어있다면 추가, 비어있지 않다면 다시 값을 비교한다.

이진 탐색 트리의 삭제

1. 삭제하려는 노드가 단말 노드(leaf node) 일 경우
2. 삭제하려는 노드의 서브 트리가 하나인 경우(왼쪽 혹은 오른쪽 서브 트리)
3. 삭제하려는 노드의 서브 트리가 두 개인 경우