Tree 종류

트리란?

---

먼저 트리란 그래프의 일종으로 여러 노드가 한 노드를 가리킬 수 없는 구조입니다.

간단하게 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 합니다.

Tree의 노드는 부모노드와 자식노드로 되어있고 더 이상 자식 노드가 없으면 leaf 라고 부른다.

 

 

 

트리의 종류

---

Binary Tree(이진 트리), Binary Search Tree(이진 탐색 트리), Complete Binary Tree(완전 이진트리)

Full Binary Tree(정 이진 트리) , Perfect Binary Tree(포화 이진 트리)

 

트리가 균형이 맞으면 balanced 라고 하고 균형이 한쪽으로만 되어있는것을 unbalanced라고한다.

balanced가 맞는 트리로는 Red-Black Tree 와 AVL Tree가 있다.

 

 

 

이진 트리 (Binary Tree)

---

• 자식 노드가 최대 두 개인 노드들로 구성된 트리입니다. 
• 자식 노드를 각각 왼쪽 자식노드와 오른쪽 자식 노드라고 합니다.
• 왼쪽 노드는 작은수가 들어오고 오른쪽 노드에는 큰 수가 들어와야한다
• 3개 붙은 트리는 Ternary tree라고 한다.

 

 

 

 

이진 탐색 트리(Binary Serach Tree)

---

• 부모 노드로 부터 오른쪽으로는 큰 노드 왼쪽으로 작은 노드로 순서대로 나열해서 쉽게 찾는 트리입니다.
• 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드로 이루어져 있습니다.
• 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있습니다.

 

 

 

완전 이진 트리 (Complete Birary Tree)

---

• 이진트리중 왼쪽부터 채워지며 왼쪽이 비워져 있고 오른쪽이 채워져있으면 완전 이진 트리가 아니다
• 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리

 

 

 

 

전 이진 트리 (Full Birary Tree)

---

• 이진트리중 왼쪽 노드가 채워져 있고 오른쪽 노드는 텅 비어져 있는 상태를 말한다.

 

 

 

 

포화 이진 트리 (Perfect Birary Tree)

---

• 이진 트리중 양 노드가 가득 채워져 있는 노드를 포화 이진 트리라고한다.

 

 

Script

트리란?

• 하나의 루트 노드를 갖고, 0개 이상의 자식노드로 이루어져 있는 구조.
• 자식노드 또한 0개 이상의 자식노드를 가질 수 있다.

트리 종류

• Binary Tree(이진 트리)
• Binary Search Tree(이진 탐색 트리)
• Complete Binary Tree(완전 이진트리)
• Full Binary Tree(정 이진 트리)
• Perfect Binary Tree(포화 이진 트리)

 

이진 트리(Binary Tree)

• 자식 노드가 최대 두개인 노드들로 구성된 트리를 이진 트리라고 한다.
• 왼쪽 노드는 작은수가 들어오고 오른쪽 노드에는 큰 수가 들어온다. 

 

이진 탐색 트리(Binary Search Tree)

• 부모 노드로 부터 오른쪽으로는 큰 노드 왼쪽으로 작은 노드로 순서대로 나열해서 쉽게 찾는 트리이다.
• 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드로 이루어져 있다.
• 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.

완전 이진 트리(Complete Binary Tree)

• 이진트리중 왼쪽부터 채워지며 왼쪽이 비워져 있고 오른쪽이 채워져있으면 완전 이진 트리가 아니다
• 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리

정 이진 트리(Full Binary Tree)

• 이진트리중 왼쪽 노드가 채워져 있고 오른쪽 노드는 텅 비어져 있는 상태를 말한다.

조화 이진 트리(Perfect Binary Tree)

• 이진 트리중 양쪽 노드가 가득 채워져 있는 노드를 포화 이진 트리라고한다.

 

참고 자료

---

출처 : https://www.youtube.com/watch?v=LnxEBW29DOw 

출처 : https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/

출처:  https://nobilitycat.tistory.com/

출처 :https://ju-hy.tistory.com/86