BST (이진탐색트리) - 개념

이번 글에서는 자료구조를 공부할 때 볼 수 있는 이진트리 구조에 대해서 알아보도록 하겠습니다.

자료구조뿐 아니라 알고리즘을 공부할 때도 많이 볼 수 있죠?

Tree

노드와 브랜치를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조입니다.

 

노드

데이터 + 다음 데이터의 주소 값을 갖고 있는 형태

연결 리스트의 구조로 이루어져 있을 때 볼 수 있는 데이터의 형태

*단방향일 경우 데이터의 주소 값이 next만 / 양방향일 경우 prev, next 모두 갖고 있습니다.

 

트리

>> 트리도 이런 노드를 사용한 데이터 구조이기 때문에 트리 또한, 데이터와 다음 데이터의 주소 값을 갖고 있는 형태입니다.

그러나 노드와 다른점은? 데이터들 간의 연결 고리 모양이 다릅니다.

 

위에서 아래로 내려오는 구조를 갖고 있으며 브랜치가 2가지 갈래로 갈라집니다.

따라서 연결 리스트의 prev, next와 같은 선형구조(=순차적으로 나열된 구조)가 아닌, 최상위 노드를 기준으로 노드들이 왼쪽/오른쪽에 자식으로 배치되는 비선형 구조입니다.

-> 이 모양이 마치 나무처럼 보이기 때문에 이름이 트리입니다.

 

상위 노드에서 아래의 자식 노드를 가리키는 선이 바로 branch(or edge)입니다. 트리에서는 상위 노드가 자식 노드를 가리키고 있기 때문에 해당 노드의 주소 값을 가리키고 있다는 것을 알 수 있습니다.

 

⚠️ 이 때 주의할 것은 트리 구조에서 브랜치는 아래로만 뻗기 때문에 (동일 계층에 대한 브랜치는 없음, 자식 계층 간의 브랜치는 없음) 트리 브랜치가 삼각형 모양이 되지 않습니다.

>> 그러므로 순환될 일이 없기 때문에 트리가 사이클을 이루지 않도록 구성한다고 하는 것입니다. 

 

트리에서 사용하는 용어

트리 구조에서 각 구성요소를 나타내는 용어에 대해 알아보겠습니다. 

- Node

트리에서 데이터를 구성하고 있는 요소 (데이터+브랜치 정보를 포함)

*간선 = edge

노드를 연결하는 선을 의미, link/ branch 라고도 부름

 

- Root

트리의 최상위에 있는 노드

 

- Parent Node

어떤 노드의 이전 레벨에 연결된 노드

 

- Child Node

어떤 노드의 다음 레벨에 연결된 노드

 

- Leaf Node (단말 노드)

Child Node가 하나도 없는 노드 (가장 마지막에 위치한 노드)

 

- Level

트리의 특정 깊이를 갖고 있는 노드의 집합 

 

- Depth

루트 노드에서 어떤 노드까지의 간선의 수

루트 노드 -> 특정 노드까지의 간선의 수

 

- Height

어떤 노드에서 리프 노드까지 가장 긴 경로의 간선의 수 

특정 노드에서 -> 리프 노드까지 가장 긴 경로의 간선의 수

 

>> Depth VS Height

트리의 깊이와 높이는 위의 그림을 통해서 차이를 확인할 수 있습니다.

가장 처음 예시 이미지를 통해 깊이와 높이의 차이를 알아보자면,

- D 노드의 깊이 : 2

- A 노드의 높이 : 3

 

- Size

자신을 포함한 모든 자손 노드의 개수

 

- Degree of Tree (트리의 차수)

트리의 최대 차수

 

이진 트리

위의 이미지에서 볼 수 있는 것과 같이 트리는 부모 노드로부터 브랜치를 통해 자식 노드를 갖고 있을 수 있습니다. 이때, 자식 노드가 아예 없을 수도 있고 2개, 3개 .. n개가 될 수 있습니다.

이 때, 이진트리는 브랜치의 최대 노드의 개수가 2개인 트리 구조를 의미합니다. (= 각 노드의 차수, 자식 노드가 2 이하인 트리를 말합니다.

(하나의 트리 구조 안 특정 노드의 브랜치가 3개 이상인 노드가 하나라도 있다면, 그 트리는 이진트리가 아닙니다.)

 

이진 탐색 트리 

이진 트리 구조 중 순서화된 이진 트리 구조를 말합니다. 

>> 이진 트리 구조에 조건이 붙은 것입니다.

 

아래 3개의 조건을 만족하는 이진 트리 구조를 말합니다. 

- 부모 노드에 대해 왼쪽/오른쪽 노드를 갖고 있는데, 왼쪽 노드는 부모 노드보다 작은 값을 가져야 하며, 오른쪽 노드는 부모 노드보다 큰 값을 가져야 합니다. 

>> 모든 노드에 대해 위의 규칙을 만족해야 합니다.

>> 왼쪽/오른쪽 서브 트리도 이진 탐색 트리입니다. 즉 순환적으로 정의되었다는 의미입니다. (하나의 노드에 대해서 왼쪽 서브 트리는 모두 루트 노드의 값보다 작은 값들만 모아져 있고, 오른쪽 서브 트리는 큰 값들만 모아져 있습니다.

- 노드의 데이터 값은 유일합니다. (=중복되지 않는 값)

- 노드의 데이터 값은 항상 존재합니다.