[자료구조] 이진트리(Binary Tree)와 이진탐색트리(Binary Search Tree)

 

트리(Tree) 자료구조의 개념 및 사용용어

트리 자료구조와 비슷한 자료구조는 LinkedList가 있다 . 아래의 예시는 Singly LinkedList(단일 링크드리스트)의 구조인데, 노드의 value와 다음 노드를 가리키는 next(포인터)로 구성되어있다. 

해당 노드는 value가 5이고 포인터가 null을 가리키고 있기 때문에 next의 값은 null이 된다. LinkedList의 노드의 저장형식을 코드로 표현하면 아래와 같은 방식으로 저장되며 HashMap의 key-value 쌍과 비슷한 value-next 쌍으로 저장이 된다. 

트리 자료구조는 노드의 포인터가 left와 right으로 설계되있다. 

이를 코드로 표현하면 value-left-right으로 저장되는 것을 알 수 있다. 

left와 right에 노드를 추가하면 트리구조는 아래와 같은 구조로 변경된다.

이를 다시 코드로 표현하면 중첩된 형식으로 자료가 저장되는 것을 알수 있다.

 

위의 예시는 트리자료 구조 중 이진트리(Binary Tree)를 나타내며, 각 노드가 최대 두 개의 자식 노드(Child Node)를 가지는 구조이다. 

 

이진트리는 형태에 따라 부르는 이름이 다르다. 

 

1) Full Binary Tree

 

모든 노드의 child가 0개 혹은 2개의 자식 노드를 가진 형태이다. 즉 leaf node(자식이 없는 마지막 노드)가 아닌 노드는 자식노드를 반드시 두개 가져야 한다. 

 

반면에 아래는 값이 12인 노드가 한개의 노드만 가리키고 있기 때문에 Full Binary Tree가 아니다. 

 

2) Perfect Binary Tree

full binary tree +  모든 리프노드의 레벨이 같아야한다.  perfect binary tree에서는 가장 깊은 depth의 노드들은 자식노드가 없고, 다른 모든 노드들은 두개의 자식노드를 가진다. 

 

3) Complete Binary Tree

Complete Binary Tree의 depth가 d라고 할 떄 depth가 d-1까지는 perfect binary tree이면서 depth가 d인 노드(제일 아래층의 노드)는 왼쪽부터 오른쪽의 순서대로 채워져가는 트리를 말한다.  오른쪽의 트리는 값이 5인 노드가 왼쪽이 아니라 오른쪽으로 채워져있기 때문에 Complete Binary Tree가 아니다. 

 

여기까지가 이진트리의 형태이며, 트리는 레벨에따라 노드를 부르는 명칭도 다르다.

 

루트노드( Root Node ) : 트리의 가장 상위에 있는 노드로, 부모를 가지지 않는 최상위 노드이다.

부모노드( Parent Node ) : 어떤 노드의 상위에 위치한 노드를 가리킨다. 만약 상위에 부모 노드가 위치한다면 자식노드로 불릴 수 있다.

자식노드( Child Node ) : 어떤 노드의 하위에 위치한 노드를 가리킨다. 하나의 부모에서 나온 자식노드들은 siblings이라고도 불린다. 

리프노트 (Leaf Node) :  자식이 없는 노드 

 

이진탐색트리(BST, Binary Search Tree)

위의 예시는 이진트리(Binary Tree)에 대한 예시이며 이진탐색트리(Binary Search Tree)의 예시는 아니다. 이진트리는 각 노드가 순서가 정해지지 않고 추가되지만, 이진탐색트리는 각 노드가 특정 순서를 따르도록 정의된 구조이다.  

 

이진탐색트리의 노드 정렬은 다음과 같다. 

 

예를 들어 루트노드가 25인 트리에 76의 값을 가진 노드를 추가한다면, 추가하려는 노드가 루트노드보다 크기 때문에  오른쪽으로 정렬되게 된다. 

 

반대로 루트노드보다 작은 노드를 추가하게 된다면 왼쪽으로 정렬되게 된다.

 

노드를 하나씩 추가해보도록 하겠다. 아래와 같은 트리구조에 값이 30인 노드를 추가한다,

처음에는 값이 25인 루트노드와 비교를 할 것이다.

루트노드보다 추가하려는 노드 30의 값이 크기 떄문에 오른쪽으로 정렬이 될것이다. 하지만 위의 트리구조는 이미 오른쪽에 76이라는 노드가 있다. 이런 경우에는 76의 노드와 값을 한번 더 비교한다. 30이 76보다 작기 때문에 노드는 왼쪽으로 정렬될 것이다.

 

이런식으로 이진탐색트리는 추가하려는 노드를 루트노드부터 차례대로 비교한다. 비교하려는 노드보다 값이 크면 오른쪽으로 정렬되고 비교하려는 노드보다 값이 작으면 왼쪽으로 정렬된다. 

 

이진탐색트리의 전체적인 구조를 보면, 루트노드를 기준으로 왼쪽은 값이 다 작고, 오른쪽은 루트노드보다 값이 다 크다.

 

 

BIg-O와 이진탐색트리

이진탐색트리의 성능을 분석하기 전에 수학을 잠시 해보도록 하겠다.  만약 값이 47인 노드가 하나만 있는 트리가 있다고 해보자. 이 노드의 개수는 1로 표현할 수 있지만 (2¹ - 1)로 1을 표현할 수 있다. 

트리레벨이 2까지 있는 경우, 노드의 수는 2²-1로 3개가 표현된다. 

트리레벨이 3까지 있는 경우, 노드의 수는 2³-1 로 7개가 표현된다.

 

하지만 성능분석시에는 큰 수에 도달할 수록 1이라는 숫자는 큰 영향을 끼치지 않기 때문에 1을 빼고 분석한다

레벨이 2인 노드는 노드가 대략 2의 2승 정도 있다 이런식으로 분석한다.  즉 레벨1은 2의 1승(2¹) , 레벨 2는 2의 2승 (2²), 레벨3은 2의 3승 (2³)으로 표현할 수 있다.  

 

 

이제 각 노드의 이동이 얼마나 걸리는지를 확인해보자 

만약 트리에 값이 47인 루트노드만 있다면, 한 번에 바로 47을 얻을 수 있다.  

레벨을 한단계 추가해보자. 레벨2에 위치한 21에 가려면 값이 47인 노드를 거친 후 ,  값이 21인 노드에 도달할 수 있다. 즉 두 번의 과정이 소요된다.  

 레벨을 한단계 더  추가해보자. 27에 있는 노드에 도착하려면 값이 47인 노드-> 값이 21인 노드-> 마지막으로 값이 27인 노드에 도달 할 수 있다. 즉 세 번의 과정이 걸린다.

이 말은 즉, 값이 27인 노드를 삭제하려면 3번의 과정이 걸린다는 뜻이다. 왜냐하면 트리 자료구조에서는 항상 루트노드를 통해 노드에 접근하기 때문이다.  값이 27인 노드를 다시 추가를 하여도 루트노드부터 들어오기 때문에 3번의 과정이 걸린다.  

마지막으로 값이 27인 노드를 찾기 위해 루트노드의 오른쪽의 노드는 한번도 거치지 않는 것을 알 수 있다. 

 

 

위의 설명을 종합해보면 , 이진탐색트리의 시간복잡도는 O(log n)가 걸린다. 이진 검색 트리에서 특정 노드를 찾을 때, 모든 노드를 비교하는 것이 아니라 각 단계마다 현재 노드와 찾고자 하는 값과의 비교를 통해 어떤 방향으로 진행해야 할지 결정된다. 따라서  탐색 공간이 대략적으로 반으로 줄어들기 때문에, 트리의 높이에 따라서 탐색 시간이 O(log n)이 된다.

 

 

 

시간복잡도 그래프를 보면 O(log n)은 O(1) 상수시간과 매우 인접해 있으므로 시간복잡도 측면에서 매우 좋은 자료구조라고 볼 수 있다. 

 

(!!!) 

하지만 위의 시나리오는 이진탐색트리가 Perfect Binary Tree일 떄이며, 이는 가장 최상의 시나리오(Omega)이다.  아래 예시와 같은 시나리오들도 염두해두어야한다.

 

트리구조가 Perfect Binary Tree가 아니더라도 트리형식이 어느정도 갖추어져 있다면 완벽한 O(log n)은 아니지만 어느정도 O(log n) 성능으로 평가할 수 있다. 

가장 최악의 시나리오는 노드가 하나로만 이루어져 LinkedList와 같은 형태로 이루어져있을 때이다. 아래와 같은 이진트리를 편향 이진트리(degenerate binary tree)라고 한다.

위의 예시에서 노드의 값이 93인 노드를 찾아가려면 값이 47인 노드-> 값이 76인 노드 -> 값이 82인 노드-> 값이 93인 노드 이렇게 네 번의 과정을 거치게 된다. 즉 시간복잡도 측면에서 O(n)으로 평가할 수 있으며 n은 노드의 개수이다. 노드의 개수가 늘어날 수록 실행시간은 그 만큼 늘어나게 된다. 

 

이제 일반적인 이진탐색트리와 최악의 시나리오인 편향 이진트리를 비교해보자,

이진 탐색 트리의 메소드는 크게  lookup() 값을 찾아 반환, insert() 추가, remove() 삭제가 있다.  일반적인 이진탐색트리에서는 모든 메소드는 O(log n)으로 평가된다.  반면에 LinkedList형태로 되어있는 편향 이진트리를 살펴보자

 

 

lookup() :  93을 찾으려면 모든 노드를 순회해야한다. 시간복잡도는 O(n)으로 n은 노드의 개수를 나타낸다.

remove() : 93을 삭제하려면 모든 노드를 순회하여 93을 삭제해야한다. 시간복잡도는 O(n)으로 n은 노드의 개수를 나타낸다.

insert() : 넣고 싶은 앞의 노드의 포인터만 수정하면 값을 쉽게 넣을 수 있다. 배열과 달리 포인터로 연결된 LinkedList나 이진탐색트리는 메모리의 연속적인 공간을 필요로 하지 않는다. 이로인해 하나의 연결로만 되어있는 편향 이진트리는 특정 위치에 노드를 삽입할 떄 이전 노드의 포인터만 조정하면 되기 때문에 상수시간 O(1)이 소요된다. 반면에 균형잡힌 이진탐색트리에서는 각 노드의 값의 크기를 비교하면서 노드가 추가되기 때문에 O(log n)이 소요된다.

 

편향 이진트리(degenerate binary tree)	메소드	이진탐색트리
O(1)	insert()	O(log n)
O(n)	lookup()	O(log n)
O(n)	remove()	O(log n)

 

 

 

---

참고 

https://www.geeksforgeeks.org/introduction-to-degenerate-binary-tree/

Introduction to Degenerate Binary Tree - GeeksforGeeks

https://www.geeksforgeeks.org/binary-search-tree-data-structure/

https://medium.com/@nitikanadgar/why-is-the-big-o-of-a-bst-o-log-n-453ee6e08104

https://www.geeksforgeeks.org/complexity-different-operations-binary-tree-binary-search-tree-avl-tree/