자료구조 - Tree

Tree 개념

tree : 1 개이상의 노드들이 링크로 연결된 모임
subtree : 각 노드 자신을 root로 보고, 그 자신 밑에 형성된 트리
parent, sibling, children, ancestor => 부모, 형제, 자식, 조상
degree of tree : 노드들 중 가장 큰 차수의 값
degree of node : 그 노드의 서브트리의 개수
leaf or terminal : zero degree (즉, 자식 노드가 없다.)
level : root node가 level1
height or depth : tree에서 가장 큰 레벨의 값

Binary tree : degree가 2인 트리
Complete Binary tree : 바이너리 트리중에서 terminal을 제외한 모든 노드들은 자신의 child노드들을 중간에 빠짐없이 모두 가지고 있는 트리
Full Binary tree : terminal을 제외한 모든 노드들은 2개의 child노드들을
                        가지고 있는 트리

바이너리 트리가 트리 데이터 Structurer에서 유용한 이유
==> 이진 검색 트리를 이용해서 배열보다 어떤 뭔가를 검색할 때
      좀 더 빠르게 할 수 있다.

장점
--> 하나의 자식노드가 주어졌을 때 이의 부모 노드가 즉시 결정된다.
      포화이진트리 형태의 운형은 배열 표현이 가장 효율적이다.

단점
--> 부분적으로 기억장소를 낭비하는 문제가 발생한다.
      노드의 삽입삭제 조작이 자주 발생하면 자료를 배열의
      위, 아래로 이동해야 하므로 많은 처리시간이 요구된다.