이진 검색 트리는 뭘까?

 

22.1 도입

• 일정한 순서에 따라 정렬한 상태로 저장해준 검색 트리
  • 32비트 정수들을 작은 것부터 큰 것까지 정렬한 상태로 저장할 수도 있고, 문자열을 가나다순으로 정렬해서 저장할 수도 있다.
• 원소의 추가와 삭제만이 아니라 특정 원소의 존재 여부 확인 등을 할 수 있다.
• 대부분 표준 라이브러리에서 제공한다.

22.2 이진 검색 트리의 정의와 조작

• 이진 트리?
  • 각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리
  • 자식 노드의 배열 대신 두 개의 포인터 left와 right를 담는 객체로 구현된다.

이진 트리의 옳은 예

이진 트리의 잘못된 예

• 위의 트리는 왼쪽은 루트보다 작은 값, 오른쪽은 루트보다 큰 값으로 이뤄진 트리이다.
  • 그러나 잘못된 예처럼 루트인 16보다 작은 원소인 15가 루트보다 작은 값으로 올 수는 없다.

순회

• 크기 순서로 정렬된 원소의 목록을 얻을 수 있다.
• 현재 노드보다 작은 원소들은 모두 왼쪽 서브트리에 있고, 현재 노드보다 큰 원소들은 모두 오른쪽 서브트리에 있다.

 

자료의 검색

• 루트인 16만 봐도 15를 트리의 어느 쪽에서 찾아봐야 하는지 알 수 있다.

 

조작

• 이진 검색 트리의 진가는 집합에 원소를 추가하거나 삭제하는 조작 연산을 할 때이다.
• 선형 구조가 아니기 때문에 새 원소가 들어갈 자리를 찾고 노드를 추가하기만 하면 된다.
  • 트리 구조를 해치지 않는다. 새 잎이 추가 되는 현상만 있을 뿐이다.
• 삭제는 오히려 어렵다.
  • 합치기 연산으로 구현한다.
  • 삭제할 노드의 서브 트리를 합치고, 삭제할 노드의 루트를 새 루트로 교체한다.

ref

• 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략