[트리] Binary Search Tree
개념
트리(Tree)는 노드(Node)와 간선(Edge)의 집합으로 이루어진다. 간선은 노드들의 부모-자식 관계를 정의하며 트리의 첫 번째 노드를 루트(Root) 노드, 자식 노드가 없는 노드를 단말(Leaf) 노드라고 한다.
다음은 트리를 기술하는데 사용하는 기본적인 용어들이다.
- 레벨(Level) : 루트 노드로부터의 거리(루트노드의 레벨은 1)
- 높이(Height) : 노드가 가질 수 있는 최대 레벨 = 깊이(Depth)
- 차수(Degree) : 한 노드가 가지는 자식 노드의 개수
- 서브트리(Subtree) : 트리에 속한 노드들의 부분집합
- 포레스트(Forest) : 트리의 집합
- 이진트리 : 자식 노드의 개수가 최대 2개인 트리
이진탐색트리(Binary Search Tree)
이진 탐색 트리는 기존의 이진 트리에서 몇 가지 제약사항이 추가된 트리를 말하며, 자료의 검색이 주된 기능이다.
Data Structure |
Worst Case |
Expected |
Binary Search Tree |
O(n) |
O(log n) |
Balanced Binary Search Tree |
O(log n) |
O(log n) |
Hash Table |
O(n) |
O(1) |
다음 특성을 만족하는 트리를 이진 탐색 트리라고 한다.
- 이진트리이다.
- 트리의 모든 노드는 유일한 키를 가진다.(각 노드는 (key, value)쌍을 가진다.)
- 왼쪽 서브트리에 있는 모든 노드의 키는 루트의 키보다 작다.
- 오른쪽 서브트리에 있는 모든 노드의 키는 루트의 키보다 크다.
- 왼쪽 서브트리와 오른쪽 서브트리도 모두 이진 탐색 트리이다.
이진 탐색 트리의 예
검색 연산(Get())
이진 탐색 트리에서의 검색 방법은 이진 탐색 트리의 특성을 이해하면 쉽게 도출할 수 있다. 검색 연산은 이진 탐색 트리의 루트노드에서 시작하며, 단계마다 다음 3가지 경우에 따라 연산을 이어간다.
- '입력 키' == '현재 노드의 키' : 검색 종료(성공)
- '입력 키' < '현재 노드의 키' : 왼쪽 서브트리로 이동
- '입력 키' > '현재 노드의 키' : 오른쪽 서브트리로 이동
삽입 연산(Insert())
삽입 연산은 위 검색 연산과 유사하다. 삽입할 키 값을 검색 연산과 같은 조건으로 연산을 이어가는데, '입력 키' 와 '현재 노드의 키'가 같은 조건일 경우 이진 탐색 트리의 조건을 만족하지 않으므로 삽입에 실패하며 더 이상 이동할 서브트리가 없을 때 그 이동할 위치에 '입력 키'를 삽입하면 된다. 즉, 삽입 위치는 항상 단말 노드가 된다. 아래는 18, 35, 45의 키 값을 삽입한 결과이다.
삭제 연산(Delete())
삭제 연산은 다음 네 가지의 경우를 나누어 생각해야한다.
- 삭제하려는 키 값이 없는 경우
- 삭제하려는 노드가 단말 노드인 경우
- 삭제하려는 노드의 차수가 1인 경우
- 삭제하려는 노드의 차수가 2인 경우
삭제하려는 키 값이 없는 경우 : 선수로 행해지는 검색연산을 통해 알 수 있으며 알맞은 출력을 해주면 된다.
삭제하려는 노드가 단말 노드인 경우 : 가장 간단한 경우로 부모 노드와의 연결만 제거하면 된다.
아래 예시는 Delete(35)와 Delete(45)을 순차적으로 수행한 것이다.
삭제하려는 노드의 차수가 1인 경우 : 검색 된 노드(삭제할 노드)와 그 부모 노드의 연결을 제거하고, 검색된 노드의 자식(이 경우 차수가 1이므로 1개 존재)과 부모 노드를 연결한다.
Delete(40)을 수행한 예시
삭제하려는 노드의 차수가 2인 경우 : 검색 된 노드(삭제할 노드)를 왼쪽 서브트리의 가장 큰 키 값으로 대체한다. 이 경우 오른쪽 서브트리의 가장 작은 값으로 대체해도 되며 두 방법 중 한 가지로 수행한다. 이 때 삭제 후의 이진 탐색 트리 구성이 두 방법에 따라 달라질 수 있다. 다시 대체한 노드(왼쪽 서브트리에서 가장 큰 키 값을 가지는 노드)는 왼쪽 자식을 가지거나 자식이 없는 두 가지 경우로 나뉠 수 있는데 전자의 경우 왼쪽 자식을 자신의 위치로 이동시키면 되고, 후자의 경우는 자식이 없으므로 삭제 연산을 종료하면 된다.
Delete(10)을 수행한 예시
