[알고리즘] 트리 (Tree)의 종류

트리

• 부모 자식의 관계를 가짐
• 계층이 있고, 그룹이 있음
• 노드가 하나이상의 자식을 가지기 때문
• 더 이상 자식이 없는 노드를 leaf라고 부름

 

트리의 종류

🎄 삼항 트리, 이진트리

삼항 트리 (Ternary tree)

최대 세개의 자식을 같은 구조

 

이진트리 (Binary Tree)

최대 두 개의 자식을 같은 구조

---

🎄 이진트리, 이진 검색 트리

이진트리 (Binary Tree)

최대 두 개의 자식을 같은 구조

-> 12를 찾는다고 할 때 2 레벨에서 9가 더 커서 오른쪽으로 이동해도 찾을 수가 없다.

 

 

이진 검색 트리 (BST : Binary Search Tree)

• 최대 두 개의 자식을 가지는 구조
• 노드의 왼쪽 자식의 값이 반드시 자신의 값 이하이며, 오른쪽 자식의 값은 반드시 자신의 값 이상이다.
• 이진 검색 트리의 장점 가운데 하나로 룩업 연산(트리에 있는 특정 노드의 위치를 알아내는 연산)을 빠르고 간단하게 처리할 수 있다.
• 중복값은 제외한다.
• 한단계 올라갈때마다 절반이 줄어들기 때문에, 시간복잡도는 O(log n)이다.

 

 

이진검색 트리 삭제

 

 

 

 

 

-> 11을 찾을 때 2 레벨에서 6보다 10이 커서 오른쪽으로 가면 찾을 수 있다.

 

---

🎄 밸런스 (Blance)

왼쪽 오른쪽의 자식이 크게 치우지지 않고 균일한 구조

 

[추가]

편향이진트리

 

balanced의 대표적인 tree

1. red-black tree
2. AVL tree
3. 자가 균형트리

 

---

🎄 완전 이진트리 (Complete Binary Tree)

왼쪽은 왼쪽부터 채워져 있는게 아니기에, 완전 이진트리가 아니다.

모든 레벨의 자식이 왼쪽부터 채워지는 구조

 

---

🎄 Full Binary Tree, Perfet Binary Tree

Full Binary Tree

노드들이 자식 요소를 두 개를 가지거나, 한개도 가지지 않는 구조

 

Perfet Binary Tree

노드들의 자식요소를 모두 두개 가지고 있는 구조

레벨의 개수를 n이라고 가정하면 2^n-1개의 노드를 가진다.

-> 3개의 레벨을 가지니, 8-1 = 7개의 노드를 가진다.

 

 

 

출처

해당 게시글에 사용된 모든 이미지의 저작권은 유튜브 엔지니어 대한민국에 있습니다.

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