[자료구조] 트리, 이진트리, 이진탐색트리 (개념)

Tree

트리는 데이터를 계층적으로 표현하기 위한 자료 구조이다. 

(tmi : 트리의 모양이 뒤집어 놓은 나무와 같다고 해서 붙여진 이름이라고 한다.)

 

노드와 간선을 이용해서 사이클을 이루지 않도록 구성한 데이터 구조이다. 

 

#트리의 특징 

비선형 자료구조, 무방향 비순환 그래프, 계층형 자료구조 

 

#노드

노드란? 내 데이터 + 다음 데이터의 주소값을 갖고 있는 형태이다.

 

연결 리스트에서 노드의 형태는 아래와 같다.

단방향일 경우에는 next만 갖고 있고, 양방향일 경우에는 prev, next 모두 갖고 있다.

 

 

#트리의 형태

트리의 형태도 비슷하다.

트리 역시 내 데이터 + 다음 데이터의 주소값을 갖는 형태이지만 위의 연결 리스트와 비교했을 때 연결 고리의 모양이 조금 다르다.

 

위와 같이 노드들이 계층을 갖고 구성된 모습을 말한다.

 

따라서 연결 리스트의 prev, next와 같은 선형 구조(순차적으로 나열된 구조)가 아니라 

부모 노드라고 불리는 최상위 노드(40)을 기준으로 노드들이 왼쪽, 오른쪽에서 자식으로 배치되는 비선형 구조이다.

 

그러므로 트리에서는 다음 주소값이 자식 노드의 주소값을 가리키고 있다는 것을 알 수 있다.

 

🍋 이 때, 브랜치는 아래 방향으로만 뻗기 때문에 아래처럼 트리의 간선(= branch)이 삼각형이 될 일은 없다.

🍋 즉, 트리의 정의로 보아 노드들이 사이클을 이루는 일이 없다는 것이다. 

#용어 정리

트리를 공부할 때 많이 나오는 용어를 먼저 정리하자.

• Node : 트리에서 데이터를 구성하고 있는 각 요소 (데이터 및 branch 정보 포함)
• Root Node : 트리의 최상위에 있는 노드 
• Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 
• Child Node : 어떤 노드의 이전 레벨에 연결된 노드 
• Leaf Node (Terminal Node) : 자식 노드가 하나도 없는 노드, 가장 끝에 위치한 노드
• Depth : 트리에서 노드가 가질 수 있는 최대 level (위의 이미지에서는 3을 의미)

 

 

이진 트리 VS 이진 탐색 트리

트리를 구성하는 노드의 branch 개수는 0부터 ... 무한으로 여러개가 될 수 있다.

위의 이미지처럼 자식 노드가 아예 없는 경우도 있고, 2개일 수도, 3개일 수도 있다.

 

 

#이진트리

이 때 이진 트리는 트리 구조의 모든 노드에 대해서 branch가 최대 2개인 노드로만 구성된 트리를 의미한다.

단 하나의 노드라도 3개 이상인 노드가 있다면, 그 트리는 이진트리라고 할 수 없다.

 

이렇게 branch의 개수가 0개, 1개, 2개인 노드로만 구성된 트리를 의미한다.

 

 

#이진 탐색 트리 

이진 탐색 트리는 이진 트리에 조건이 붙은 것이다.

 

모든 노드에 대해서 

✅ 자신의 왼쪽 자식 노드에는 자신보다 작은 값이

✅ 자신의 오른쪽 자식 노드에는 자신보다 큰 값이 들어있는

노드로 구성된 이진트리를 말한다. 

 

또한,

✅ 노드의 데이터 값은 중복되지 않는 유일한 값이며

✅ 노드의 데이터는 nil이 아니라, 항상 존재하는 값이다.

 

라는 조건/규칙을 만족하는 이진 트리이다.

 

위의 gif를 통해서 보면 좀 더 잘 이해할 수 있다.

 

 

이런 이진 탐색 트리를 Binary Search Tree라고 하는데 약어로 줄여서 BST라고 한다.

 

이진 트리란? branch가 최대 2개인 노드로만 구성된 트리를 말하고
이진 탐색 트리란? 특정 조건을 만족하는 트리를 이진 탐색 트리라고 한다.