Tree

나무에는 수많은 가지가 존재한다. 그리고 가지처럼 뻗어나간다는 말은 다양한 갈래로 갈 수 있다는 말이고

오늘은 이 나무를 뒤집은 Tree라는 추상 자료형에 대해 알아보자.

 

자료 구조를 분류하기 위해선 데이터를 저장하는 방식에 대한 부분이 있지만 그거보다 더 큰 범주에는 선형인지

비선형인지가 있다. 즉, 데이터가 구성되고 탐색되는 방식에 sequence와 order가 있는지 여부이다.

배열이나 링크드 리스트 같은 선형 데이터 구조에서 데이터는 순서가 지정되고 순서가 매우 중요하다.

순차적으로만 순회할 수 있기 때문이다. 그러나 비선형 데이터 구조도 있다. 까다롭고 다루기 어려울 수 있지만

선형 데이터 구조를 이해했다면 무리가 없을 것이다.

 

비선형 자료 구조는 실제로 순서를 따르지 않는다. 순서대로가 아니다. 비순차적으로 순회한다.

그 중 유명한 구조는 트리이다.  트리는 노드와 링크로 구성된다. 실제 나무도 뿌리가 있어야 나무가 자란다.

이것처럼 트리 구조에도 루트가 무조건 존재해야한다. 그리고 루트는 하나이다. 루트로부터 여러 링크가 뻗는다.

여기서 선형 구조와 차이가 있다. 선형 구조는 하나의 인덱스에서 다음 인덱스로만 길이 하나가 있다. 하지만

트리에서는 여러 개의 갈래가 존재한다. 즉, 트리는 다양한 모양과 방식으로 뻗어나갈 수 있다.

 

트리에 대해서 알아두면 좋은 몇 가지 용어이다.

- root : 연결되는 링크나 엣지가 없는 최상위 노드

- link/edge : 부모 노드에서 자식 노드를 가리키는 참조 포인터

- child : 연결된 부모 노드가 있는 모든 노드

- parent : 다른 노드로의 링크가 있는 모든 노드

- sibling : 부모 노드가 같은 노드

- internal :  자식 노드가 있는 모든 노드 ( 기본적으로 모든 부모 노드 )

- leaf : 자식 노드가 없는 노드

트리의 데이터는 계층적이다는 것을 기억해두자.

 

 트리의 법칙

트리에는 자명한 법칙이 존재한다.

- 트리의 노드가 N개가 있는 경우 링크/엣지는 N-1개이다.

이 이유가 뭘까? 트리의 루트로의 edge가 존재하지 않기 때문이다.

즉, cycle이 존재하지 않기 때문이다. 

- 트리는 재귀적이다.

이 뜻은 큰 트리 구조를 쪼갈라서 보면 내부에는 더 작은 트리들로 구성되어 있다는 것이다.

이런 트리의 중첩때문에 재귀적 탐색 알고리즘을 작성할 수 있다. 

 

트리의 분류 방법

트리는 다양한 모양과 방식으로 뻗어나갈 수 있다고 앞서 말했었다. 그렇기 때문에 트리의 유형과 해당 데이터의

모양을 식별하고 이해할 수 있는 것이 매우 중요하다. 이를 위해 어떤 유형의 트리를 처리하고 해당 트리에서 데이터

가 있는 위치에 대해 이야기해야 할 가장 중요한 두 가지 속성이 있다.

바로 노드의 깊이 와 노드의 높이이다. 

노드의 깊이는 간단하게 노드가 트리의 루트로부터 얼마나 떨어져 있는지 생각하는 것이다. 현재로썬 트리의 탐색에

대해서 말하지 않았기에 루트 노드에서 링크/엣지를 따라 가면 얼마나 떨어져 있는지 알 수 있을 것이다.

따라서 루트 노드에서 해당 노드에 도달하는데 걸리는 엣지의 수를 계산하면 알 수 있을 것이다.

노드의 높이는 루트로부터 가장멀리 떨어진 노드를 찾으면 될 것이다. 가장 먼 leaf 노드를 찾고 엣지의 수를 계산하면

노드의 높이를 알 수 있다. 이를 알면 트리에서 가장 긴 경로를 알고 있다는 것을 의미한다.

깊이와 높이가 중요한 이유는 트리가 어떻게 생겼는지 바로 알 수 있기 때문이다. 트리는 다양한 모양이 있을 수 있기 때문에 양방향으로 쭉 뻗은 트리도 있을 수 있지만 한 방향으로만 쭉 뻗은 트리도 있을 수 있다. 이를 균형 잡힌 트리와 불균형 트리라고 말하겠다. 두 sibling 노드의 깊이가 두개의 엣지 이상 차이 나면 불균형 상태이고 그렇지 않으면 균형 상태이다.

이것이 중요한 경우는 순회하는 경우이다. 균형잡힌 트리는 트리를 탐색하고 작업 수를 절반으로 줄일 수 있어 더 나은 성능의 구조를 갖게 된다. 하지만 한 쪽으로 불균형하게 쭉 뻗은 나무는 결국 선형 구조와 비슷해질 수 있다.

 

이진 탐색 트리 ( Binary Search Tree)

이진 트리는 구조화 방식때문에 이런 이름이 붙여졌다. 이진 트리는 노드로부터 다른 노드로 연결되는 엣지의 개수가 2개까지만 생길 수 있다. 즉, 부모 노드는 두 개의 자식 노드만 가질 수 있다. 앞서 트리는 계층적이고 재귀적 특성이 있다고 말했다. 즉, 왼쪽 하위 트리, 오른쪽 하위 트리만으로 구분될 수 있다. 이런 BST의 재귀적 측면은 트리를 매우 강력하게 만드는 부분이다. 하나의 단일 BST가 분할될 수 있고 그 안의 미니 트리로 균등하게 분할될 수 있다는 사실은 트리를 탐색할 때 유용할 것이다.

이진 탐색 트리는 가장 중요한 특성이 있다. 노드가 특정 방식으로 정렬된다는 것이다. 이런 정렬방식으로 인해 비선형 구조에서의 검색이 가능해진다. 어떤 노드의 왼쪽에 있는 모든 노드는 해당 노드보다 작아야하고 오른쪽에 있는 모든 노드는 커야한다. 이렇게 되면 왼쪽 서브 트리의 노드들은 오른쪽 서브 트리의 노드들보다 작다는 패턴이 생긴다.

즉, 각 노드에 두 개의 자식 노드만 있는 경우 모든 트리는 이진 트리가 될 수 있다. 이진 트리를 검색 가능하게 만드는 것은 노드의 순서이며, 확장하여 이 트리를 강력하게 만드는 요소이다. 이것은 트리에서 수행하려는 모든 기본 작업에도 적용된다. 예를 들어, 값을 가져와 트리의 올바른 위치에 삽입하는 insert 작업을 수행한다고 가정했을때 루트 노드부터 삽입하려하는 값이 루트 노드보다 큰지 작은지를 비교 하고 작다면 왼쪽 크다면 오른쪽 이것을 반복하다가 leaf 노드에 도달해서 마지막 비교를 마치고 해당 위치에 삽입하면 끝이다.

이진 탐색 알고리즘의 힘을 활용할 수 있기 때문에 BST는 굉장히 유용하다. 하지만 모든 이진 트리가 이진 탐색 트리인 것은 아니다라는 것을 알았으면 한다. 이진 탐색이란 것은 정렬된 배열에서도 사용할 수 있다. 그것을 트리 구조를 이용하여 쉽게 구현한 것이다. 이진 탐색은 검색해야할 요소의 수를 굉장히 많이 줄인다. 검색 세트와 검색 공간의 절반을 제거해나간다. 탐색이란 기능을 구현할때 가장 빠른 알고리즘이다. 

 

참조 - 참조 링크엔 이미지가 있어 이해하기 더 쉽습니다.

- https://medium.com/basecs/how-to-not-be-stumped-by-trees-5f36208f68a7

How To Not Be Stumped By Trees

- https://medium.com/basecs/leaf-it-up-to-binary-trees-11001aaf746d

Leaf It Up To Binary Trees