[알고리즘] 이진탐색트리(Binary Search Tree)

오늘의 포스팅 내용은 이진탐색트리(BST) 입니다!

 

우선 이진탐색트리에 대한 설명에 앞서 트리에 대해서 짧게 설명하고 지나가겠습니다.

 

" 트리 구조란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 

 

간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

 

트리에서 최상위 노드를 루트 노드(root node 뿌리 노드)라고 한다.

 

또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 

 

자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드)라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다. "

 

고 위키피디아에 나와있습니다.ㅎ

 

그리고 일반적으로 트리라고 하면 보통 이진트리(Binary tree)를 뜻하는 경우가 많습니다. 그렇다면 이진트리란 무엇일까요?

 

이진트리란 한 노드에 자식이 최대 2개까지만 올수 있는 트리입니다. 그리고 자식2개를 각각 왼쪽자식과 오른쪽자식이라고 부릅니다.

 

이진트리의 예입니다.

 

그렇다면 오늘의 포스팅 주제인 이진탐색트리란 무엇일까요!?

 

이진 트리의 속성을 가지면서 자식 노드의 크기가 왼쪽에서 오른쪽 순서로 연결되는 것이다. 

 

즉 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있고

 

노드의 오른쪽 서브트리에는 그 노드의 값보다 크거나 같은 값들을 지닌 노드들로 이루어져 있다.

 

이 이진트리의 장점중 하나는 룩업연산(LookUp, 트리에 있는 특정 노드의 위치를 알아내는 연산)을 빠르고 간단하게 

 

처리할수 있다는 점이 있습니다. 

 

이진탐색트리에서 룩업연산의 의사코드는 다음과 같습니다. 

 

 

룩업연산은 반복문이 한 번 돌 때마다 왼쪽서브트리와 오른쪽서브트리중 한쪽으로 넘어가고 

 

한 번에 절반씩의 노드를 검색 대상에서 제외할 수 있기 때문에 빠릅니다.

 

그에 따라 룩업연산의 실행시간은 입니다.

 

하지만 이는 균형이진검색트리에서의 실행시간 입니다!

 

이에 관해서는 이진탐색트리에서의 삽입, 삭제 까지 다룬후 설명하겠습니다. 

 

이진탐색트리에서의 삽입은 현재노드보다 작으면 왼쪽 크면 오른쪽에 위치시킨다는 기본원칙만 지키면 됩니다. 

 

이진탐색트리에서의 삭제는 다음과 같이 3개의 경우가 있습니다.

Case1. 삭제하고자 하는 노드가 리프노드 일경우 = 그냥 삭제한다!

                                                               ↓

Case2. 삭제하고자 하는 노드의 자식노드가 하나인 경우 = 삭제하고자 하는 노드(25)의 부모(28)가 삭제하고자 하는 노드(25)의 자식(26)을 가리키게 한다.

                                                        

                                                                 ↓

Case3. 삭제하고자 하는 노드의 자식노드가 두개인 경우 = 삭제하고자 하는 노드(28)의 오른쪽 자식노드(33)의 영역중 가장 작은노드(30)를 삭제하고자 하는 노드의 위치로 이동한다.

                                                                 ↓

이제 룩업연산, 삽입, 삭제를 학습했으니 이진탐색트리의 최악의 경우에 대해서 알아보겠습니다.

최악의 경우는 다음과 같을때 입니다.

이렇게 데이터가 한쪽으로 몰릴경우 연결리스트와 같아지면서 룩업연산의 속도는이 됩니다. 

이러한 문제를 해결하기위해 균형을 잡는 트리들을 사용하게 됩니다. 

누군가에게는 작은도움이 되었기를 바라면서 오늘의 포스팅 끝~​