트리(Tree)

트리(Tree)

데이터의 검색과 탐색에 아주 널리 이용되는 자료 구조.
트리란, 뿌리(루트; root)노드에서 간선(edge)들이 마치 나무에서 뿌리로부터 잔가지로 뻗어나가듯이 가지치기된 구조를 말한다.
딱딱하게 말하면, 순환하는 길이 없는 그래프(graph)로 정의
트리에 대한 학습의 바탕을 마련하기 위해, 아래와 같은 용어들이 무슨 뜻인지를 배운다.

• 노드(nodes) : 트리에서 각각 원소들을 의미한다.
• 간선(edges) : 노드들을 이어주는 것
• 루트 노드(root node) : 최상위 노드
• 리프 노드(leaf nodes) : 더이상 가지를 치지 않는 노드
• 내부 노드(internal nodes) : 루트 노드와 리프 노드 사이에 있는 노드들
• 부모(parent)노드와 자식(child)노드
• 노드의 수준(level) : 루트 노드의 층 0을 기준으로 한층마다 증가하는 것, 루트 노드로부터 간선의 개수가 얼마만큼 떨어져 있냐를 보여줌
• 노드의 차수(degree) : 자식(서브 트리)의 수(즉, 자식으로 연결되는 간선의 개수)
• 트리의 높이(height) - 또는, 깊이(depth) : 말 그대로 몇 층까지 구성되어있는 가, 최대 수준(level)+1
• 부분 트리(서브 트리;subtrees) : 트리에서 어느 한 노드를 기준으로 잘라내어 표현한 것
• 이진트리(binary trees) : 모든 노드의 차수가 2 이하인 트리
• 포화 이진트리(full binary trees) : 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리

• 완전 이진트리(complete binary trees) :

이진트리(Binary Tree)

위에서 정의했다시피 트리에 포함되는 모든 노드의 차수가 2 이하인 트리를 말한다.
트리를 순회하는 순서를 크게 2가지로 나눌 수 있는데 깊이 우선 순회(depth first traversal)와 넓이 우선 순회(breadth first traversal)가 있다.
이는 많은 알고리즘들이 트리 또는 그래프의 순회를 이용하여 주어진 문제를 해결하기에 중요하다.
우선 깊이 우선 순회에도, 특히 이진트리를 대상으로 하는 경우에 3가지의 서로 다른 순서를 정의할 수 있다.

• 깊이 우선 순회(depth first traversal)
  • 중위 순회(in-order-traversal)
    • (1) Left subtree
    • (2) 자기 자신
    • (3) Right subtree
  • 전위 순회(pre-order-traversal)
    
    • (1) 자기 자신
    • (2) Left subtree
    • (3) Right subtree
  • 후위 순회(post-order-traversal)
    
    • (1) Left subtree
    • (2) Right subtree
    • (3) 자기 자신

다음으로는 넓이 우선 순회이다. "나중에 다시 방문하기로 하고 그 순서를 기억해 두자" 이것은 큐(queue)가 바로 그것이다.
이러한 선입선출(FIFO; First-in First-out)의 성질을 가지고 있기에 적합하다. 이를 응용해 넓이 우선 순회를 설계한다.

이진 탐색 트리(Binary Search Tree)

삭제가 조금 복잡하다.

• 해당 노드가 루트인 경우
• 자식이 하나인 경우
• 자식이 둘 인 경우

이렇게 나누어서 생각해 봐야 한다.

---

본 문서는 프로그래머스 어서와! 자료구조와 알고리즘 강의를 수강하고 정리했습니다.

출처 : 프로그래머스 : 어서와! 자료구조와 알고리즘은 처음이지?