[자료구조] 트리 (Tree)

트리 (Tree)

트리(Tree)는 계층적 관계를 나타내는 자료구조로 노드(Node)와 간선(Edge)로 구성되어잇으며 가장 상위 노드인 루트(Root)가있다. 각 노드는 다른 노드와 연결되어 부모.자식 관계를 형성하며 노드들은 자식 노드를 가질 수 있습니다.

• 노드(Node) : 트리의 각 요소. 데이터를 표현하는데 사용한다.
• 간선(Edge) : 두 노드를 연결, 관계를 나타낸다.
• 루트(Root) : 트리의 최상위 노드. 부모가 없는 노드
• 부모(Parent) : 다른 노드를 자식으로 가지는 노드
• 자식(Child) : 부모 노드에 의해 연결되는 노드
• 리프(Leaf) : 자식 노드가 없는 노드

 

특징 및 종류

• 트리는 계층적으로 구성되어 있으며, 루트노드를 시작으로 여러 자식 노드들이 존재 할 수 있다.
• 노드는 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
• 두 노드간의 경로는 유일하다.
  • 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
• 트리는 이진트리, 이진탐색트리(BST), 균형트리(AVL, RBT), 이진 힙(최대힙, 최소힙) 등이 있다.

 

이진트리(Binary Tree)

• 각 노드가 최대 두개의 자식을 갖는 트리
• 모든 트리가 이진 트리는 아니다
• 기본적인 트리 구조로, 이진 검색트리, 힙(Heap) 트리 등에 사용된다.

 

이진탐색트리 (Binary Search Tree)

이진 탐색 트리 - https://dream-and-develop.tistory.com/146?pidx=0

• 이진 트리의 형태, 각 노드는 키 값이 왼쪽 서브 트리의 모든 값보다 크고, 오른쪽 서브트리의 모든 값보다 작다.
• 삽입, 삭제, 검색 등이 평균적으로 O(log n)의 시간 복잡도를 가지고 있다.
• 트리가 불균형시 최악의 경우 O(n)의 시간복잡도를 가진다.
• AVL Tree : 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이차이가 1인 이진 탐색 트리
  • 삽입,삭제시 회전(Rotate)하며 트리구조의 균형을 유지한다.
• RB Tree : 각 노드에 색깔(Red,Black)을 부여하여 균형을 맞추는 이진 탐색 트리
  • AVL과 같이 노드간의 균형을 유지하지만, 더 적은 회전을 하며 정렬한다.

 

힙(Heap)

• 각 부모 노드의 값이 자식 노드의 값보다 우선순위가 높은 구조
• 최대 힙과 최소 힙이 있다.
• 최대 힙 : 부모 노드의 값이 자식 노드의 값보다 크거나 같다.
• 최소 힙 : 부모 노드의 값이 자식 노드의 값보다 작거나 같다.
• 완전 이진 트리 형태를 가지며, 삽입,삭제 시 O(log n)의 시간복잡도를 가진다.

 

그래프 VS 트리

https://medium.com/@bnnj86/data-structure-tree-binary-tree-binary-searching-tree-d9daa3f69e67