tree

Binary Tree (이진 트리)

• 레코드 (record)

  개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위
  예) 사람의 레코드: 이름, 휴대폰 번호, 주민번호 등의 정보 포함

• 필드 (field)

  레코드에서 각각의 정보를 나타내는 부분
  예) 위 사람의 레코드에서 각각의 정보를 나타내는 부분 (주민번호, 이름 ...)

• 검색키 (search key) 또는 키 (key)

  다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드
  키는 하나의 필드로 이루어질 수도 있고, 두 개 이상의 필드로 이루어질 수도 있다.

• 검색 트리 (search tree)

  각 노드가 규칙에 맞도록 하나씩의 키를 갖고 있다.
  이를 통해 해당 레코드가 저장된 위치를 알 수 있다.

• 루트 노드 (root node)

  트리의 제일 위 부모 노드를 루트 노드라고 한다.

• 리프 노드 (leaf node)

  트리의 제일 아래 자식 노드들을 리프 노드라고 한다.

---

Binary Search Tree (이진 탐색 트리) 개념

• 각 노드는 하나씩의 키 값을 갖는다. (각 노드의 키 값은 다르다.)
• 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식을 갖는다.
• 임의의 노드의 키 값은 자신의 왼쪽 자식 노드의 키 값보다 크고, 오른쪽 자식의 키 값보다 작다.

BST 의 예

서브 트리(sub tree)의 예

BST 성능

• 최선의 경우 (완전히 균형잡힌 트리)

  root node 의 값과 찾을 값을 한 번 비교하면, 찾을 대상이 left 서브 트리나 right 서브 트리로 좁혀진다. 최선의 경우 이진 트리 search, add, remove 수행시간은 O(log N)이다.
  
  평균의 경우도 수행시간은 O(log N)이다.

• 최악의 경우(한쪽으로 치우친 트리)

  root node 의 값과 찾을 값을 한 번 비교하면, 찾을 대상의 크기가 n - 1 로 줄어든다.
  최악의 경우 이진트리 검색 수행시간은 O(n)이다.