Tree

tree는 자료를 찾기 쉽게 만든 계층형 구조입니다.
tree는 노드들이 서로 연결된 집합이며 노드 간에는 계층적 구조를 가집니다.
가장 위에 있는 노드를 root라고 부르며 노드 아래에 있는 노드들을 자식 노드라고 부릅니다.
각각의 노드들은 여러개의 자식 노드를 가질 수 있습니다. 또한 이런 자식 노드들도 그들의 자식노드들을 가질 수 있는 재귀적 구조를 가집니다.

Tree 관련 용어

• Parent Node
  다른 노드를 직접적으로 포함하는 노드를 말합니다.

• Child Node
  다른 노드에 포함되는 노드를 말합니다.

• Root Node
  트리의 가장 위에 있는 노드입니다.

• Leaf Node or External Node
  자식을 가지고 있지 않은 노드입니다.

• Ancestor of a Node
  해당 노드로부터 루트 노드까지의 경로 상에 있는 모든 노드입니다.

• Descendant
  특정 노드로부터 시작해서 하위에 연결된 모든 노드입니다.

• Sibling
  자신과 같은 부모노드를 가지고 있는 다른 노드입니다.

• Level of a node
  루트노드로부터 해당 노드의 경로까지에 있는 edge의 개수를 Level이라고 부릅니다.

• Internal Node
  최소 하나의 자식 노드를 가지고 있는 노드를 말합니다.

• Neighbor of a Node
  해당 노드의 부모 노드나 자식 노드를 말합니다.

• Subtree
  descendant를 포함한 특정 노드의 트리를 말합니다.
  

Tree의 유형

• Binary tree
  Binary tree는 각각의 노드가 최대 2개의 자식노드를 가질 수 있는 tree를 말합니다.
  Binary tree는 세부적으로 full binary tree, complete binary tree, balanced binary tree, degenerate tree가 있습니다.

• Ternary tree
  Ternary tree는 각각의 노드가 최대 3개의 자식 노드를 가질 수 있는 tree를 말합니다. 각각 left, mid, right로 나뉩니다.

• N-ary Tree or Generic Tree
  Generic tree는 레코드나 자식들의 주소를 가지는 리스트로 이루어진 노드들의 집합입니다.

Tree의 Operation

1. Create
   tree 자료구조를 생성합니다.

2. Insert
   tree에 자료를 넣습니다.

3. Search
   특정 데이터를 지닌 노드가 있는지 없는지 찾습니다.

4. Traversal
   깊이 우선 순회와 넓이 우선 순회가 있습니다.

Tree의 이점

• 트리를 통해 효율적인 검색이 가능합니다. AVL같은 균형잡힌이진트리의 경우 O(log n)의 시간복잡도에 원하는 값을 찾을 수 있습니다.
• 자료들의 계층적 구조를 표현하게 해줍니다. 이는 매우 많은 양의 정보들을 조직적으로 만들고 표현하게 해줍니다.
• Tree는 재귀적인 구조를 지니고 있기 때문에 재귀알고리즘을 통해 쉽게 순회하고 조작가능합니다.

Tree의 단점

• Tree가 균형잡히지 않았다면, 더 최악으로 한쪽으로 편향되었다면 매우 비효율적인 구조가 됩니다.
• Tree는 다른 자료구조에 비해 더 많은 메모리 공간을 요구합니다.
• Tree의 구현과 조작은 복잡합니다. 그리고 Tree에 대한 깊은 이해를 필요로 합니다.