이진 탐색 트리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

컴퓨터 과학에서 이진 탐색 트리(BST: binary search tree)는 다음과 같은 속성이 있는 이진 트리 자료 구조이다.

  • 각 노드에 값이 있다.
  • 각 노드의 키값은 모두 달라야 한다.
  • 값들은 완전 순서가 있다.
  • 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
  • 노드의 오른쪽 서브트리에는 그 노드의 값보다 크거나 같은 값들을 지닌 노드들로 이루어져 있다.
  • 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 함.
  • 중복된 노드가 없어야 함.

이진 탐색 트리 에서의 검색[편집]

  • 이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴한다.
  • 검색하고자 하는 값을 루트노드와 먼저 비교하고, 일치할경우 루트노드를 리턴한다.
    • 불일치하고 검색하고자 하는 값이 루트노드보다 작을 경우 왼쪽 서브트리의 값과 비교한다.
    • 불일치하고 검색하고자 하는 값이 루트노드보다 클 경우 오른쪽 서브트리의 값과 비교한다.

삽입[편집]

  • 삽입은 검색부터 시작.
  • 트리를 검색한 후 키와 맞는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입.

삭제[편집]

3가지 경우가 있음.

  • 리프노드(자식노드가 없는 노드) 삭제 : 리프를 삭제하면 됨.
  • 자식이 하나인 노드 삭제 : 해당 노드를 삭제하고 그 위치에 해당 노드의 자식노드를 집어넣음.
  • 자식이 2개인 노드 삭제 : 해당 노드의 왼쪽 자식노드에서 가장 큰값으로 대체하거나, 오른쪽 자식노드중 가장 작은 값으로 대체하고나서 선택된 노드를 삭제함.