[C# 기초] #20. 트리(Tree), 이진트리, 이진 탐색 트리

---

1. 트리(Tree)란?

: 계층적인 자료를 표현하는 대표적인 자료구조. 검색 알고리즘을 위해 주로 사용됩니다.

가장 위에 하나의 루트(Root)로부터 출발하여 그 밑에 0개 이상의 여러 자식 노드들을 가지는 구조를 가지고 있습니다.

* 하나의 자식은 하나의 부모만 가질 수 있음.

 

---

2. 트리 구조에서 자주 사용되는 용어

* 루트(Root) : 트리의 가장 꼭대기 노드

* 간선(Edge) : 두 노드를 잇는 링크

* 브랜치(Branch) : 한 노드에서 갈라져 나온 자식 노드의 수

* 형제(Sibling) : 부모가 같은 자식 노드들

* 리프(Leaf) : 자식노드가 없는 하단의 노드

* 높이(Height) : 특정 노드에서 루트 사이의 길이

* 깊이(Depth) : 루트 노드에서 특정 노드까지의 길이

* 트리 높이(Tree Height) : 가장 먼 거리에 있는 Leaf 노드와 루트 사이의 길이

* 트리 깊이(Tree Depth) : 루트 노드에서 가장 먼 리프 노드까지의 길이

* 레벨(Level) : 루트 노드로부터의 깊이

* 노드의 차수(Node Degree) : 한 노드의 서브트리의 갯수(자식노드의 수)

* 트리의 차수(Tree Degree) : 트리 안 노드들의 차수 중 최대 차수

---

3. 이진 탐색 트리(Binary Search Tree)

* 이진 트리 : 노드의 최대 Branch가 2개인 트리.

* 이진 탐색 트리 : 노드에서 특정 조건을 가지고 그 조건에 충족하면 왼쪽, 그렇지 않으면 오른쪽으로 보내는 식으로 조건을 가짐. 아래 그림이 숫자를 크고 작음을 기준으로 나눈 이진 탐색 트리 예시입니다.

그림 출처 : https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node

 

 

아래 코드로 원하는 data를 가진 노드를 찾고, 삭제할 수 있게 이진 탐색 트리를 구현해봤습니다.

GitHub

---

4. 그래프와 트리의 차이

* 그래프 : 노드와 노드를 연결하는 간선으로 표현된 자료 구조

* 트리 : 그래프의 한 종류. 방향성이 있는 비순환 그래프

	그래프	트리
방향성	방향, 무방향 둘 다 존재	방향있음
사이클	가능	사이클x
루트	x	o
부모/자식 관계	x	o