자료구조 - 트리의동작 Chapter 4. Trees

목차

1. Preliminaries
2. Binary Trees, The Search Tree ADT-Binary Search Trees
3. Insert, Delete, Make Empty, Find, FindMin, FindMax, Traverse
4. avl Trees
5. Splay Trees
6. B-Trees
7. Traversal

본문내용

4.1 Preliminaries
 Tree구조는 어떠한 조건을 만족하는 노드(Node), 링크(Link)의 집합
 노드는 어떤 정보를 담고 있으며, 링크는 노드 간의 연결을 나타낸다.

 Node는 Vertex라고도 하며, Link는 Edge라고 한다.
 트리는 N개의 노드와 N-1개의 링크를 갖는다.

 경로(Path)는 Tree내에서 링크에 연결된 일련의 노드 집합
 Tree제일 위의 노드를 Root노드라 하고, Root노드로부터 다른 노드에 이르는 경로는 오직 하나밖에 존재하지 않는다. (Tree와 Graph의 다른점)

 E, F, G, H, J, D 노드와 같이 자식이 없는 노드를 leaf Node, 혹은 Terminal Node, External Node라 부른다. A, B, C, I 노드와 같이 자식이 하나라도 있는 Nonterminal Node혹은 Internal Node라고 부른다.

 A는 B, C, D의 부모노드(혹은 선조)가 되고 B, C, D는 A노드의 자식노드가 된다.

 B, C, D를 형제노드라 부르며, A<->E, A<->F, A<->G, A<->H등과 같은 관계를 Grand Children또는 Grand Parents 라고 부른다.

 깊이는 A를 기준으로 0부터 시작하고 높이는 해당노드의 External노드를 기준으로 0부터 시작한다. 예를들어 C의 깊이는 1, 높이는 2. B의 깊이는 1, 높이는 1이 된다. 높이를 계산할 때는 해당노드의 External Node부터 계산하는 것을 유의해야 한다.

4.2 Binary Trees, 4.3 The Search Tree ADT-Binary Search Trees
 자식을 최대 2개를 갖는 트리
 부모보다 작은 값은 왼쪽 자식으로, 부모보다 큰 값은 오른쪽 자식으로 둔다
 이진트리가 충분히 균형이 잡혔을 때 log2N의 검색 시간을 갖는다
 완전한 이진 트리라면 노드수 N은 2d-1이 된다(단 d는 레벨)

참고 자료

없음