Jeonghun (James) Lee

10/22/2016

Tree (data structure)

1. Tree의 일반적인개념

Tree 구성

Tree의 기본구성은 Parent node에 child node로 연결된 추상적인 자료구조로
Tree의 element는 Node이며 Tree의 선을 branch라고 말한다.
그리고, 마지막 Node , 즉 Child node가 없는 leaf node , end-node 라고 부른다.

좀 더 자세히 설명을 하게되면, Graph와 동일하게 표시도 가능하겠지만,
Tree는 방향성과 계층의 속성을 가지고 있기에 이를 분리하여 표시한다.

Tree의 종류

Tree는 종류 다중 Tree와 2진 Tree로 구분 할 수 있겠다.
일반적으로 2진 트리, Binary Tree를 많이 사용한다.

Tree의 재귀(Recursion)

Tree에서 Recursion (재귀)는 자주 사용이되며, 이는 탐색 (Traversal) 에 용이하다.

https://en.wikipedia.org/wiki/Tree_(data_structure)
https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

1.1 Trie 트라이, MultiTree (다중 트리) 소개

쉽게 생각하면 탐색기에서 사용하고 있는 디렉토리가 다중 트리이며,
데이타베이스에서 주로 사용이 된다.
이 곳에서는 다루지는 않겠다.

트라이 (Trie)
  https://en.wikipedia.org/wiki/Trie

https://en.wikipedia.org/wiki/Multitree

B Tree or B+ Tree
  https://en.wikipedia.org/wiki/B%2B_tree
  https://ko.wikipedia.org/wiki/B_%ED%8A%B8%EB%A6%AC
  https://ko.wikipedia.org/wiki/B%2B_%ED%8A%B8%EB%A6%AC

1.2 Binary Tree 소개

Child Node를 2개로 한정지어 Tree를 구성하도록 하는 트리를 말하며, 일반적으로
많이 사용이 되어진다.

Node 기준 left child 와 right child 존재하며, 상위 처음 Node 를 Root라고 말한다.

구현방법은 Tree 구조체를 이용하는 방법도 있겠지만, Array로도 구현이 가능하다.

2. Binary Tree 구현방법

2.1 Tree 구조체 사용하여 동적구현

장점: 유지보수 및 삭제의 용이성 , 동적으로 추가 ,삭제가 쉽다.
단점: 구현이 새로운 구조체와 여러 함수를 필요하다보니 좀 복잡하다.

struct Node {
int data ; // void * data;
.... // 다른 Data
struct Node *left;
struct Node *right;
}

struct Tree {
int size;
struct Node *root; // 전체 root
struct Node *prenode; //searching 할때, 현재 node의 root
.... // 이밖에 필요한 정보 및 함수 포인터도 삽입가능
}

2.2 Data Array 정적 구현

이 부분 추후 Heap sort 와 우선 순위 Queue에서 다시 사용하겠다.

장점: Data Array 가장 쉽게 구현이 가능하다.
단점: Node의 삭제가 어렵고, Array Size로 인하여 이미 지속적인 유지보수가 힘들다.

0은 Root 이며, Level 0
1,2 Root의 left , right Level 1
3,4 1의 left, right Level 2
5,6 2의 left, right Level 2

그래서 총 3층의 2진트리로 구성이 가능하며, 이는 구성이 Breath-First Search 개념 유사하다.
다만,

아래 그림은 Array 0부터 시작을 했고, Level도 0부터 시작을 했다

Node 의 수가 Data 존재여부가 아닌 계층(Level)이 많아 질 수록 더 많은 Array를 요구되어진다.

전체 Node 갯수를 구하는 방법은 다음과 같다.

Level 0 1 2 3 4 5
Num 1 , 2 , 4, 8 , 16, 32

이곳에 간단한 규칙이 존재하고 있으며, 예를 Level 4의 Node는 16 이고, 그 이전 Node 합은 (1+2+4+8)=15,
즉 현재 Node -1 은 이전 Node의 합과 동일하다. 그러므로 다음 Node -1하게 되면 된다.

i = Node의 Level

Number of Node = 2^(i+1) -1 , N 은 Tree의 Level의 수
Left Node = 2i+1
Right Node = 2i+2
Parent Node = (i-1)/2

https://en.wikipedia.org/wiki/Binary_tree
https://en.wikipedia.org/wiki/Binary_search_algorithm

3. Binary Tree 일반기능

Searching

key 값이 동일하면, 현재 Node ,
key < 현재 node.key 작을 경우, left 진입
key > 현재 node.key 클 경우 right 진입

Insertion

Node가 Empty일 경우, 마지막 Node일 경우, 삽입
key < 현재 node.key 작을 경우 , left 진입
key > 현재 node.key 클 경우 , right 진입

Search와 동일하지만, 삽입기능만 추가.

Deletion

기본은 위의 Searching 으로 동일하게 삭제할 Node를 찾는다.
Node를 삭제 할경우 세가지 사항을 고려한다.
one child는 left node or right node를 말하며, sub-left-tree or sub-right-tree도 가능

1. 삭제할 node가 단말 , no child 일 경우
1. Searching 통하여 삭제할 Node Data 찾음
2. 문제없이 삭제 가능

2. 삭제할 node가 one child 일 경우
1. Searching 통하여 삭제할 node를 data 찾음
2. 삭제할 node의 삭제이전 node를 저장
3. 삭제할 node는 link를 끊고 삭제
4. 삭제이전 node에 child node 연결

3. 삭제할 node가 two child 일 경우
1. Searching 통하여 삭제할 node를 data 찾음
2. 삭제할 node의 삭제이전 node를 저장
3. 삭제할 node 값과 유사한 값을 찾음 (둘 중 선택 A or B)
A. left-sub tree에서 가장 큰 값의 node 를 찾아 선택
B. right-sub tree에서 가장 작은 값의 node 를 찾아 선택

4.1 위의 선택된 node가 last node 일 경우 (no child)
A. 삭제이전 node에 선택된 node 연결
B. 선택된 node에 삭제할 node left,right 연결
C. 삭제할 node 삭제 .

4.2 위의 선택된 node가 sub-tree 일 경우 (sub-tree root)
A. 삭제이전 node에 선택된 node를 연결
B. 삭제할 node를 삭제
이 경우는 one child sub-tree 구조이기에 상위 2번째 방법과 동일 **

**주석
Binary Search Tree 구조상 아래의 구조밖에 될 수 밖에 없다.
A에서 가장 큰 값은 sub-tree node일 경우 right child 없다.
B에서 가장 작은 값은 sub-tree node 일 경우 left child 없다.

아래의 그림을 참조 이해하기 쉽다.
http://www.algolist.net/Data_structures/Binary_search_tree/Removal
http://stackoverflow.com/questions/8292661/how-to-delete-a-node-with-2-children-nodes-in-a-binary-search-tree