컴퓨터알고리즘#12

LeeMir, 05 May 2021

탐색트리

이진탐색트리

내부노드에 (키, 원소) 쌍을 저장하며 다음의 성질을 만족하는 이진트리
- 왼쪽 서브트리 키 값이 기준 값보다 작으면서 오른쪽 서브트리 키 값이 기준 값보다 크거나 같음
- 보통 중복 키를 허용하지 않음
- 항상 왼쪽이 오른쪽보다는 먼저 탐색됨
- 이진탐색트리를 중위순회하면 키가 증가하는 순서(오름차순)로 방문
탐색
- 키 k를 찾기 위해 루트에서 출발하는 하향 경로를 추적
- 다음에 방문할 노드는 k와 현재 노드의 키 값을 비교한 결과에 따라 결정
- 외부 노드에 다다르면, 키 k가 발견되지 않은 것이므로 NoSuchKey를 반환
삽입
- 삽입할 키 k를 탐색(중복 유무 검사)
- k가 트리에 존재하지 않을 경우, 탐색은 외부 노드에 도착
- 외부 노드에 k를 삽입한 후 그 노드를 내부 노드로 확장(두 개의 외부 노드를 연결)
삭제
- 삭제할 키 k를 탐색
- k가 있는 노드에 도착
- 노드를 삭제하고나서는 빈 자리를 채워야하는데, 여러 경우 존재
  - 자식 노드가 모두 외부 노드일 경우에는 그냥 삭제
  - 자식 노드 중 하나는 외부 노드 하나는 내부 노드일 경우에는 내부 노드를 삭제하려는 노드의 부모와 연결
  - 자식 노드가 모두 내부 노드일 경우에는 오른쪽 자식 노드에서 왼쪽으로 계속 타고 들어가 그 위치의 노드(중위 계승자)를 삭제하려는 노드의 자리에 위치

AVL 트리

트리의 모든 내부 노드 v에 대해 v의 자식들의 좌우 높이 차이가 1을 넘지 않는 이진탐색트리
- 높이 균형을 맞춘 트리(한 칸 차이까지 가능)
- AVL 트리의 서브트리 역시 AVL 트리
- 삽입 삭제는 이진탐색트리와 유사하거나 동일
  - 삽입 삭제 결과 높이 균형 속성이 파괴될 수 있음
  - 따라서 작업 후에는 혹시 생겼을지도 모를 불균형을 찾아서 수리해야 함