• 트리의 대표적인 사례 : 검색 트리
• 검색 트리 중 흔하게 사용되는 것 : 이진 검색 트리

이진 트리란?

각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리 따라서 자식 노드들의 배열 대신 두 개의 포인터 left, right를 담는 객체로 구현됨 각 노드의 왼쪽 서브 트리에는 해당 노드보다 작은 원소, 오른쪽 서브트리에는 해당 노드보다 큰 원소

순회

이진 검색 트리를 “중위 순회”하면 크니 순서로 정렬된 원소의 목록을 얻을 수 있음 집합에 포함된 “최대 원소나 최소 원소”를 쉽게 얻을 수 있음 왼쪽 맨 밑에 최소, 오른쪽 맨 밑이 최대

자료의 검색

간단하게 특정 원소가 존재하는 지 확인 가능 한 번의 비교로 어디쪽에서 찾아야하는 전체에서 절반을 줄일 수 있으므로 이진탐색과 비슷한 속도

조작

이진 검색 트리가 진가를 드러내는 곳은 집합에 원소를 추가 혹은 삭제하는 연산을 할 때임 새 원소가 들어갈 위치를 찾고 거기에 노드를 추가하기만 하면 됨 가장 까다로운 것은 원소를 삭제하는 것 합치기 연산으로 구현 노드t를 지운다면, t의 두 서브트리를 합친 새로운 트리를 만든 뒤, 바꿔치기함

시간복잡도

루트에서부터 한 단계씩 트리를 내려가며 재귀 호출을 통해 수행되므로 최대 재귀 호출횟수는 트리의 높이 h와 같음 o(h) 이진 검색 트리의 높이는 자료들이 어떤 순서로 추가되고 삭제되느냐에 따라 크게 달라짐 트리는 가급적 가로로 넓게 퍼지고 평평한 트리가 좋음 -> o(logN) 단점을 개선한 변종 : 균형잡힌 이진 검색트리(트리의 구조에 추가적인 제약을 정함)