파이썬과 함께하는 자료 4장 트리구조

- 리스트의 경우 삽입, 삭제 후에도 정렬 상태를 유지해야 하므로 O(N)시간이 소요

- 이러한 문제점을 보완한 자료구조가 트리 구조

- 트리는 일반적 트리, 이진트리로 구분

- 이진트리는 탐색트리, heap자료구조, 구문트리(syntax Tree)로 구분

- 트리의 용어는 Root, child, Degree(count of child), parent, leaf(no child), Sibling, Ancestor, Descendant, Subtree, Level, Height, Key로 구성

- leaf의 경우 Terminal or External 이라 불리며 leaf가 아닌 노드를 internal or Non-Terminal 라고 불린다.

- 용어에 대한 확실한 이해가 없으면 차후 공부할때 많이 힘들므로 용어는 꼭 외우는 것이 좋다

- 최대 차수가 k인 트리에 n개의 노드가 있다면 none 레퍼런스 수는 nk - (n-1) = n(k-1) + 1 이다

- 즉 아이들이 최대 k개인 노드가 있다면 

- 일반적인 이진트리는 왼쪽 자식, 오른쪽 형제 순으로 key를 구성한다.

- 이진트리의 정의는 각 노드의 자식수가 2 이하인 트리이다. 즉 자식이 2, 1 또는 없을수도(이때의 경우는 leaf) 이다

- 이진트리는 널리 활용된다.

- 이진트리의 경우 포화이진트리, 완전 이진트리, 두가지가 있다.

- 포화이진트리란 모든 이파리의 깊이가 같고 각 내부노드가 2개의 자식노드를 가지는 트리이다

- 완전이진트리란 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리이다.

(레벨은 곧 높이, 즉 4레벨의 트리라면 3레벨까지는 포화이진트리로 구성되어있고 마지막 4레벨의 노드들의 경우 왼쪽부터 채워진 트리)

- 레벨 k에 있는 최대 노드 수는 2^(K-1) 이다.( 3레벨의 경우 최대 4개의 노드가 있을 수 있다)

- 레벨 k인 이진트리의 최대 노드 수는 2^H -1 이다