SEB Section 2 BST

BST(Binary Search Tree)

트리 구조는 효율적인 탐색을 위해 사용하기도 한다. 트리 구조는 여러 가지 형태로 나누어져 있는데 알아보겠다.

• 이진 트리(Binary tree)

  자식 노드가 최대 두 개인 노드들로 구성된 트리이다. 이 두개의 자식 노드는 왼쪽과 오른쪽으로 나눌 수 있다.

이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나눈다.

• 정 이진 트리(Full binary tree)

  각 노드가 0개 혹은 2 개의 자식 노드를 갖는다.

• 완전 이진 트리(Complete binary tree)

  정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.

• 포화 이진 트리(Perfect binary tree)

  마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.

이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.