BST(Binary Search Tree) - 이진검색트리
이번 포스팅에서는 이진검색트리(BST)의 개념과 삽입, 삭제의 과정에 대해 살펴보려한다.
이진검색트리(Binary Search Tree)란 ?
트리구조의 형태로 두 개의 자식노드를 갖는다.
자식노드는 부모노드 보다 작다면 left, 부모노드 보다 크다면 right
노드에 위치하게 된다.
이러한 자료구조를 이진검색트리라고 한다.
BST는 Linked List와 같이 여러 노드로 이루어진 자료구조라고 할 수 있다. 이 노드들은 null(비어있거나) 이거나 다른 노드로 향하는 refernce(참조값) 을 갖는다. 여기서 말하는 다른 노드는 left node, right node 인 자식노드를 가지고 있다. 그리고 노드들은 값을 갖는다. 이 값들은 BST 내에서 어떤 노드에 위치할지를 결정한다.
BST는 Linked List 와 유사한 형태를 갖지만, Linked List는 오직 하나의 다른 노드만을 참조하고, BST 두 개의 자식 노드를 참조할 수 있다는 점이 차이라고 할 수 있다.
BST의 특징은 아래와 같다.
left node는 부모노드보다 항상 작다.right node는 부모노드보다 항상 크다.- balanced 하다고 볼 수 있다. (Perfect BST)
- 값이 순차적으로 정렬된다고 가정했을 때,
- BST의 모든 트리 레벨은 마지막(트리의 최하단) 레벨만을 제외한 모든 레벨에서 좌, 우 균형을 유지한다.
- 트리의 마지막 레벨에서는 좌측에서 우측으로 노드가 채워진다.
[참고]
이진트리(Binary Tree)
- 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리
완전이진트리(Complete Binary Tree)
- 루트노드부터 노드가 채워져있으며, 같은 레벨에서 왼쪽,오른쪽 노드가 채워져있는 트리
이진 검색 트리를 왜 사용할까?
그렇다면, 이진 검색 트리를 왜 사용하는걸까?
보통, 이진검색트리는 검색, 게임 로직, autocomplete tasks 등에 사용된다고 한다. 그 이유는 바로 속도 때문이다. 앞서, 이야기 했듯이 BST는 정렬된 자료구조이다. 새로운 노드 값이 삽입되는 순간 모든 노드들은 질서정연하게(부모노드 보다 작으면 left node, 부모노드보다 크다면 right node) 정렬이 된다. 그렇기 때문에 특정 값을 검색할 때, 매번 탐색해야하는 경우의 수가 절반으로 줄어들어 검색 속도 측면에서 이점이있다.
또한, BST는 Array와 다르게 데이터가 참조에 의해 정렬된다. 만약, 새로운 값을 BST에 넣고자한다면, 그저 새로운 노드를 생성하고, 링크를 걸어주기만 하면 된다. 이 작업은 Array가 새로운 공간을 만들어, 값을 넣는 작업보다 훨씬 빠르다.
이 원리에 따라, BST는 삽입, 삭제, 검색 모든 부분에서 효율이 뛰어난 자료구조라고 할 수 있다.
삽입 과정
이진 검색 트리에서 삽입 과정은 간단하다. 삽입할 노드를 찾고, 노드를 연결해주기만 하면된다.
위 BST에 6 을 넣어보자.
BST의 특성에 따라 (1) -> (2) -> (3) 을 거쳐 5 노드의 right 에 위치하게 된다.
삭제 과정
1) 자식 노드가 없는 경우
자식 노드가 없는 2를 삭제해보자.
자식 노드가 없는 노드를 삭제하는 경우에는 부모노드와 연결되어있는 링크를 끊어주면된다. Java에서는 Garbage Collector에 의해 Unreachable Node는 메모리 해제 대상이므로 자동으로 해당 메모리를 해제해준다. 다른 c나 c++ 등 Garbage Collector 가 없는 언어의 경우에는 직접 메모리를 해제해줘야한다.
2) 자식 노드가 한 개 인경우
자식 노드가 한 개인 5를 삭제해보자.
자식 노드가 한 개인 경우, 삭제 하는 노드와 연결되어있는 링크를 전부 삭제해주고, 삭제하는 노드의 부모노드와 자식노드를 link로 연결해주면된다. 이때도 마찬가지로 Java는 Garbage Collector에 의해 링크 연결만 해제해주면, 자동으로 메모리가 해제된다.
3) 자식 노드가 두 개 인경우
자식 노드가 2개인 12를 삭제해보자.
우선, 노드의 값을 제거해준다. 그런데 자식 노드가 한 개인 경우와 다르게 부모노드인 8과 어떤 자식노드를 연결시켜줘야할지에 대한 기준이 애매하다. 따라서, 두 개의 자식노드를 삭제하는 경우에는 새롭게 링크를 연결하는 것이 아니라 삭제한 노드에 위치할 값을 BST를 탐색하며 찾아줘야한다.
한번 생각을 해보자. 삭제한 노드는 9보다 크고 14보다 작아야한다. 그리고 이 조건을 만족하는 값들 중 가작 작은 값이어야한다. 그렇기 때문에 right 노드에서 시작해서 left 노드를 파고들며 자식노드가 없을 때까지 탐색해줘야 조건을 만족하는 가장 작은 값을 찾을 수 있다. 따라서, 11이 찾고자 하는 값이 된다.
따라서, 12를 삭제한 후 정렬을 완료한 BST의 구조는 위와 같다.
시간복잡도
그렇다면, BST의 삽입, 삭제, 검색 시간복잡도(Time Complexity)는 어떻게 될까? 매번 서치하는 경우가 절반으로 줄어들기 때문에 삽입, 삭제, 검색의 시간복잡도는 O(log n)이 된다. 삽입, 삭제는 삽입, 삭제하고자 하는 노드만 찾아 작업해주면 되기때문에 검색 시간복잡도와 동일하다.
1) 삽입 : O(log n) - insert 할 노드를 서치하는 시간
2) 삭제 : O(log n) - delete 할 노드를 서치하는 시간
4) 검색 : O(log n) - 서치 시간
vs Heap
BST를 조사하면서 사실 Heap이랑 비슷하지않을까 라는 생각이들었다. 사실 두 자료구조는 비슷해보여도 명확한 차이가 있다. min-heap 을 기준으로 두 자료구조를 비교하면 아래와 같다.
| Heap | BST | |
|---|---|---|
| 정렬 기준 | 상위노드의 값이 하위 노드의 값보다 작다는 것만을 보장한다. | Heap과 다르게 순서(Order)를 보장한다. |
| 시간복잡도 | (일반)검색, 삽입, 삭제 = O(log n) | 검색, 삽입, 삭제 = O(log n) |
| 최대/최소값 검색 시간복잡도 | O(1) | O(log n) |
결론은, 최대, 최소값만을 찾고자 한다면 Heap을 사용하고, 모든 값을 정렬하고 싶다면 BST를 사용하면된다.
Leave a comment