부산대학교자료구조
Scientific Inference Lab

Keeping the Order

BST Height

탐색, 삽입, 삭제는 모두 루트에서 한 갈래를 따라 내려가므로 비용이 높이(height)에 달려 있다. 같은 키라도 넣는 순서가 높이를 정하며, 정렬된 순서로 넣으면 한쪽으로만 자란 편향 트리(skewed tree)가 되어 비용이 O(n)으로 커진다.

세 연산의 비용탐색은 찾았는지 답하고, 삽입은 단말 노드를 붙이고, 삭제는 경우에 따라 잇는다. 내려가는 길이는 모두 높이로 제한된다.
삽입 순서같은 키 집합이라도 먼저 넣은 키가 위에 자리 잡으므로 순서가 모양과 높이를 바꾼다.
편향 트리어느 노드에서도 갈림길이 없어 연결리스트처럼 한 줄이 된다.
순서가 필요한 연산해시테이블은 키 하나 찾기가 기대 O(1)이지만 순서대로 출력하거나 범위로 찾으려면 모든 키를 보아야 한다.

같은 일곱 키도 넣는 순서에 따라 높이가 2에서 6까지 달라진다

20부터 80까지 10 간격의 일곱 키를 넣는 순서를 고르고 넣은 키 수를 옮기면 트리 모양, 높이, 삽입 때 지나온 노드 수가 바뀐다.

삽입 순서와 BST 모양넣은 순서대로 만든 BST
가로 띠 하나가 깊이 하나다. 노드의 가로 위치는 키의 크기 순서로 고정했다. 초록 원이 방금 넣은 키이고, 초록 선이 그 키까지 내려온 길이다.

노드 수가 늘수록 편향 트리와 낮은 트리의 비용 차이는 벌어진다

노드 수 n을 바꾸면 두 모양에서 가장 깊은 노드까지 내려갈 때 방문하는 노드 수가 바뀐다. 탐색, 삽입, 삭제 모두 이 길이 안에서 내려간다.

노드 수와 최대 방문 노드 수편향 트리는 n, 가장 낮게 만든 트리는 log n에 따라 늘어난다
가로축은 노드 수 n, 세로축은 루트에서 가장 깊은 노드까지 방문하는 노드 수(높이 + 1)다. 파란 실선은 정렬된 순서로 넣은 편향 트리, 초록 점선은 같은 n으로 만들 수 있는 가장 낮은 BST이고 두 점이 현재 n이다.

범위로 찾을 때 BST는 범위와 겹치는 갈래만 내려간다

15개 키를 가진 높이 3의 BST에서 하한과 상한을 바꾸면 방문하는 노드와 출력되는 키가 바뀐다. 같은 키를 해시테이블에 담았다면 15개 키를 모두 확인한 뒤 정렬해야 한다.

BST의 범위 탐색범위와 겹치는 갈래만 방문
초록 원이 범위 안이라 출력한 키, 옅은 파란 원이 방문했지만 범위 밖인 키, 흐린 점선 원이 방문하지 않은 키이고 초록 선이 내려간 참조다. 아래 칸은 출력 순서다.