Tree

본 문서는 2022년 1월 1일 에 작성되었습니다.

Tree 는 수많은 분야에서 사용되는 자료구조입니다.
도식화 상으로는 복잡하지만, 실제 파츠를 뜯어보면 Linked List 와 유사함을 알 수 있습니다. 둘 모두 Node 를 통해 객체들을 연결한다

차이점은, Tree 는 하나의 key에 붙은 Node 가 많다는 점 정도입니다.
이를 통해 좌<->우 및 부모<->자식의 관게등을 나타냅니다.

이에 따라 수많은 Tree 구조가 있습니다.

다양한 Tree

수많은 Tree 구조 중에서 다음의 내용을 다룰 생각이다.

1. Binary Tree
2. 제한없는 Root Tree
3. Binary Search Tree
4. Red Black Tree

Binary Tree 란?

Binary Tree 는 다음과 같은 특징을 가지고 있습니다.

1. 최상위 경계 원소 NIL 로 부터 시작된다.
2. 차상위 원소 A 는 3 개의 노드를 가진다.
   2.1. A.parent
   2.2. A.child=left
   2.3. A.child=right

제한없는 Root Tree 란?

제한없는 Root Tree 란 다음과 같은 특징을 가지고 있습니다.

1. 최상위 경계 원소 NIL 로 부터 시작된다.
2. 차상위 원소 A 는 1+k 개의 노드를 가진다.
   2.1. A.parent
   2.2. A.child-1
   2.3. A.child-2
   2.k. A.child-k

따라서 얼마 만큼의 Node 를 할당할 지 모른다면,
이 구조는 k 를 큰 상수로 할당해두어야 하고
이에 따라 메모리 낭비가 발생할 수 있다.