Binary Search Tree, BST (Data Structure)

본 글은 #draft 상태입니다.

• 내용 보강하기
• 그림 추가하기

BST §

• 트리 생성 규칙은 다음과 같다.
  • Node 는 어떤 값 (Key 라고 부르기도 한다) 을 담고 있다.
  • Node 의 자식은 최대 2개이다.
  • Node 의 왼쪽 자식의 값은 본인의 값보다 작고, 오른쪽 자식의 값은 본인의 값보다 커야 한다.
• 이름에 “Search” 가 들어가는 이유는 특정 값을 찾기에 유용한 자료구조이기 때문이다.
  • 간단히 설명하면, 어떤 값 x 를 찾기 위해서는
    1. Root node 부터 시작해
    2. x 가 node 의 key 보다 작으면, 왼쪽 node 로, 크면 오른쪽 node 로 내려가는 작업을
    3. x 를 찾을 때 까지 반복하면 된다.