Tree

트리는 Stack 이나 Queue 와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 Node 과 Edge 로 이루어져있으며, 파일시스템이나 디렉터리 구조와 같은 계층적인 관계(Hierarchial Relationship)를 표현할 수 있다.

선형, 비선형 자료구조

노드 또는 원소들의 앞뒤 관계가 단방향이던 양방향이던 1:1 인 자료구조를 선형자료구조라고하며 대표적으로 배열, 스택, 큐, 연결리스트 가 있다. 하지만 비선형자료구조는 노드의 앞뒤 관계가 1:N 또는 N:N 인 관계이다. 하나의 노드가 다수의 하위 노드들을 참조할 수 있으며, 거꾸로 다수의 노드가 하나의 상위 노드를 참조할 수 있다.

Tree 의 성질

1. 트리는 모든 정점이 간선으로 연결되어 있으면서, 정점의 수가 N 개 일때 간선의 수가 N - 1 개가 된다.
2. 루트노드에서 특정 노드로 가는 경로 그리고 임의의 두 노드 간의 경로가 유일하다. (두 개의 노드 사이에 반드시 1 개의 경로만을 가진다)
3. 루트 노드를 제외한 모든 노드은 반드시 하나의 부모 노드를 가진다.
4. 트리는 사이클(Cycle)이 없는 하나의 연결 그래프(Connected Graph) 이자 방향 비순환 그래프 (DAG : Directed Acyclic Graph) 이다.
5. 모든 트리는 그래프이지만, 모든 그래프는 트리가 아니다.

Tree 의 용어

Tree 의 종류

1. 이진트리 (Binary Tree)
   1. 이진 탐색 트리 (Binary Search Tree : BST)
      1. AVL 트리
      2. 레드블랙 트리 (RB Tree)
2. 다진 트리 (n-ary Tree)
   1. 다진 검색 트리 (n-ary Tree)
      1. B-Tree
3. 신장 트리 (Spanning Tree)
   1. 최소비용 신장 트리 (Minimum Cost Spanning Tree : MST)

Binary Tree

Binary Tree (이진 트리) 는 모든 노드가 최대 2개의 Child 노드를 갖는 즉, 최대 차수(Degree) 가 2 를 넘지 않는 트리를 의미한다. Binary Tree (이진 트리) 는 노드의 값, 노드의 데이터 크기에 관계없이 구성 된다.

Binary Search Tree

Binary Search Tree (BST : 이진 탐색 트리) 정렬되어있는 이진트리이다. 따라서 왼쪽 자식노드의 값이 부모노드의 값보다 작아야하고, 오른쪽 자식노드의 값이 부모노드보다 커야한다.

AVL Tree

RedBlack Tree

B-Tree

Reference

코딩문 Tree Youtube

코딩 인터뷰 완전분석 - 트리(Tree)와 그래프(Graph)

힙, 트리, 그래프(Heap, Tree, Graph)

그래프와 트리

방향/무방향 그래프의 정리

DAG 알고리즘이란 무엇인가

트리의 개념과 용어정리

트리의 기초

트리는 방향 그래프인가? 무방향 그래프인가

Trees (트리 자료구조)

gyoogle

[JaeYeopHan][https://github.com/JaeYeopHan/Interview_Question_for_Beginner/blob/main/DataStructure/README.md#tree]

WeareSoft

jobhope

이진트리의 종류