[자료구조]트리

Tree

• 그래프의 일종
• 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프
• 루트(root) 노드: 최상위 노드가
• 리프(leaf) 노드: 자식 노드가 없는 노드
• 내부(interior) 노드: 루트 노드도, 리프 노드도 아닌 노드
• 상위 노드와 하위 노드를 각각 부모(parent) 노드와 자식(child) 노드라고 함
• 같은 부모 노드를 둔 자식 노드들끼리를 형제(sibling) 노드라고 함

Types of Tree Data Structures

• Binary Tree
  • Binary Search Tree, Heap, Trie
  • Red-Black Tree
• Height-Balanced Binary Tree
  • AVL Tree, T-Tree
• n-Way Tree
  • m-Way Trie
  • 2-3 Tree
• Height-Balanced m-Way Tree
• Spatial Tree

Tree Traversal

• Breadth-First
  • 모든 노드를 level 순서로 방문
  • root에서 시작하여 다음 높이의 모든 노드를 방문한 뒤 다음 높으로 넘어감
• Depth-First
  • root에서 시작
  • 가능한 멀리까지 탐색하고 돌아옴
  • Inorder Traversal
    • Left Subtree -> Root -> Right Subtree
  • Postorder Traversal
    • Left Subtree -> Right Subtree -> Root
  • Preorder Traversal
    • Root -> Left Subtree -> Right Subtree
• Example
  
  • Breadth-First: Level order Traversal
    • 100 -> 75 -> 150 -> 50 -> 90 -> 120 -> 490 -> 160
  • Inorder Traversal
    • 50 -> 75 -> 90 -> 100 -> 120 -> 150 -> 160 -> 490
  • Preorder Traversal
    • 100 -> 75 -> 50 -> 90 -> 150 -> 120 -> 490 -> 160
  • Postorder Traversal
    • 50 -> 90 -> 75 -> 120 -> 160 -> 490 -> 150 -> 100