Tree Data Structure(트리 자료구조)

1. 트리(Tree) 란?

트리는 비선형, 계층적 관계를 표현하는 자료구조이다.
또한 명확한 부모와 자식 관계의 자료구조이다.

 

구성요소
노드 : 자료, 객체, 각 항목
Path(간선 or edge) : 노드와 노드를 연결하는 선
Root Node : 구조의 최상위 노드
Terminal Node(or leaf Node) : 자식노드를 가지고 있지 않은 노드
Internal Node : 터미널 노드를 제외한 모든 노드(루트 노드 포함)

 

트리 구조의 종류

General Tree

레벨 0 에 있는 노드는 항상 루트노드다. 같은 레벨에 존재하는 노드는 동일한 관계이고 다른 레벨에 존재하는 노드는 부모-자식의 관계이다. 어떤 노드든 갯수에 관계없이 자식노드를 가질 수 있다.

Forests

만약 루트노드를 삭제하면 루트노드의 자식인 다음 레벨 1 에 있는 각 노드가 각각의 최상위 노드(루트노드)가 되고 이를 포레스트라 부른다.
Binary Tree

루트 노드를 중심으로 모든 노드는 최대 두개의 자식 노드로 나뉘어진다. 자식 노드가 없는 노드는 리프 노드 또는 터미널 노드라 불린다.
Binary Search Tree

정렬된 바이너리 트리구조다. 루트 노드의 왼쪽 자식 노드는 항상 작은 범위의 노드이고, 오른쪽 자식 노드는 루트 노드와 동일한 값이거나 큰 범위의 노드이다.(searching, sorting, etc)
Expression Tree

일반적으로 바이너리 트리의 구조를 갖고 있다. 수학적인 계산 구조를 나타낼때 활용된다. 예를 들어, (a + b) / (a * b - c) + d
Tournament Tree

선택 트리 또는 위너 트리라고도 불리는 트리구조이다. 토너먼트를 통해 최종 승리한 플레이어가 루트 노드에 존재한다. 

 

2. 트리의 활용

• 파일 시스템

 

3. 구현을 위한 의사코드(Pseudo Code)

1. 루트 노드를 가진 객체를 생성한다.
2. appendChild(data) : 루트 노드에 자식 노드의 갯수가 두개가 안되면 새로운 객체를 생성해 루트 노드에 담는다.
3. 루트 노드의 자식 노드 또한 최대 두개의 자식 객체를 담는다.
  3-1. 만약 자리가 없으면 동일한 레벨의 다음 노드로 이동한다.
  3-2. 동일한 레벨의 노드에 자리가 없으면 왼쪽 끝의 자식 노드로 가서 다시 자리가 있는지 확인 후 객체를 추가한다.
4. removeNode(data) : 삭제하고자 하는 데이터가 왼쪽 자식 노드와 오른쪽 자식 노드와 비교해 작은지 또는 크거나 같은지 확인 후 결과에 따라 첫번째 방향을 정한다.
  4-1. 방향이 정해진 후 해당 노드의 자식 노드와 삭제할 데이터를 비교해 같은지 먼저 비교한다.
  4-2. 만약 같으면 해당 노드를 삭제하고, 만약 그렇지 않다면 다음 자식 노드를 확인 한다.
  4-3. 마지막 까지 없다면 에러를 반환한다.
5. nodeList(data) : 해당 노드가 가지고 있는 전체 자식 노드 리스트를 가져온다.
  5-1. 해당 노드를 검색하고 각 자식 노드를 새로운 배열에 담아 반환한다.
6. changeNode(currentDate, newDate) : currentDate를 검색해 해당 노드를 newDate로 재할당 한다.

 

 

4. 참고자료(References)

https://k39335.tistory.com/16?category=653559
https://yeolco.tistory.com/66