- Tree 구성
Tree의 element는 Node이며 Tree의 선을 branch라고 말한다.
그리고, 마지막 Node , 즉 Child node가 없는 leaf node , end-node 라고 부른다.
좀 더 자세히 설명을 하게되면, Graph와 동일하게 표시도 가능하겠지만,
Tree는 방향성과 계층의 속성을 가지고 있기에 이를 분리하여 표시한다.
- Tree의 종류
일반적으로 2진 트리, Binary Tree를 많이 사용한다.
- Tree의 재귀(Recursion)
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 소개
많이 사용이 되어진다.
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 정적 구현
- 장점: 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 진입
- Deletion
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
- Traversal
어떻게 정하는지를 결정한다.
1. Depth-first Search (DFS, 깊이 우선 탐색)
- pre-order : 처음에 방문하면 pre-order
- in-order : 중간에 방문하면 in-order : BST Tree에서 사용
- post-order : 나중에 방문하면 post-order
A. Pre-order
- Visit current Node and Get Data
- Traverse the left subtree by recursively
- Traverse the right subtree by recursively
B. In-order
일반적인 Binary Search Tree에서 많이 사용한다.
왜냐하면, 최소값 부터 정렬이 가능하다.
- Traverse the left subtree by recursively
- Visit current Node and Get Data
- Traverse the right subtree by recursively
- Traverse the left subtree by recursively
- Traverse the right subtree by recursively
- Visit current Node and Get Data
https://en.wikipedia.org/wiki/Depth-first_search
2. Breadth-first search (BFS, 너비 우선 탐색)
- Level order
- Queue에 방문할 Node를 넣는다.
- 방문할 Node를 Queue에서 얻는다.
- Left 방문하고 Child Node가 있을 경우 이를 Queue에 삽입.
- Right 방문하고 Child Node가 있을 경우 이를 Queue에 삽입.
- Queue Empty가 될때까지 2번을 반복
Binary Traversal
https://en.wikipedia.org/wiki/Tree_traversal
https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C **
https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C **
Binary Search Tree
https://en.wikipedia.org/wiki/Binary_search_tree
http://robodream.tistory.com/181
http://web.skhu.ac.kr/~cyberci/program/view/view_13.htm
댓글 없음 :
댓글 쓰기