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

트리(Tree)의 종류

 

트리구조(하위에 자식이 추가되는 구조)에서 이진트리는 하위에 2개까지 붙을 수 있는 트리를 이진트리(Binary Tree)라고 한다.

그 외 하위에 여러 가지 붙는 변형 형태의 트리도 많다.

그중에서 많이 쓰이고 대표적인 트리에 대해서 알아보자.

 

 

이진 탐색트리는 이진트리 + 정렬의 개념이 추가된 형태로 

탐색하는 과정에서 많이 사용하는 탐색 구조이다.

 

트리에서 밸런스(Balance)에 대한 표현이 나오는데 이는 지나치게 치우치게 되면 탐색하는 과정(비용)이 많이 들기 때문에 트리를 구성하는 과정에서 밸런스에 대한 처리도 고려를 해야 한다.

밸런스가 고려된 트리의 종류는 다음과 같다.

Red-Black Tree

AVL Tree 

완전 이진트리(Complete Binary Tree) - 서브 레벨의 트리가 왼쪽부터 채워지는 트리이다.

Full Binary Tree - 모든 하위 노드가 End 인 트리

Perfect Binary Tree - 모든 노드의 레벨과 트리가 End 인 트리(완벽한 피라미드)

 

여러가지 변형 트리가 있을수 있는데 개념에 대해서만 어느정도 알면 응용해서 사용이 가능하다.

★★☆☆☆