Tree

tree는 부모-자식 관계를 가지는 구조로 계층이 있고, 그룹이 있다. 이 것을 가능하게 한 것이 노드가 하나 이상의 자식 노드를 가지기 때문이다. 트리의 노드 중에는 부모를 아는 경우도 있고, 자식만 아는 경우도 있고, 데이터가 잘 정렬된 것도 있고, 섞여있는 것도 있다.

 

그리고 트리중에서 자식 노드가 최대 2개 까지만 붙는 경우를 이진 트리라고 한다. 그리고 그 이상의 3개씩 자식이 붙는 경우를 ternary tree라고 한다. 

 

그럼 이 중에서 가장 중요한 이진 트리를 알아보자. 

Binary Tree는 이진 트리다. 즉, 자식 노드가 최대 2개인 트리이다. 여기서 Binary Search Tree는 왼쪽 자식에는 현재 루트 값보다 작은 값이 들어가고, 오른쪽 자식에는 현재 루트 값보다 큰 값이 들어가는 경우를 말한다.

 

트리에서 Balance란 무엇일까? 트리에서 발란스를 말하면, 왼쪽 자식 노드의 개수와 오른쪽 자식 노드의 개수가 정확히 일치해야 하는 것을 말하는 것은 아니다. 그저 너무 한 쪽으로만 치우쳐저 있지만 않다면, Balanced Tree라고 칭한다.

그리고 Balance가 맞는 대표적인 트리로는 red-black tree, AVL tree가 있다.

 

Complete Binary Tree. 즉, 다음과 같이 완전 이진 트리란 모든 노드들이 레벨별로 왼쪽부터 채워져있고, 마지막 레벨이 맞으면 완전 이진 트리라고 한다.

 

  그리고 여기서 Full Binary Tree가 되려면, 그 안에 노드들이 자식을 0개 또는 2개를 가진 트리를 말한다.

마지막 Perfect Binary Tree는 양쪽으로 모든 노드들이 레벨에 맞게 2개의 자식을 가진 완벽한 피라미드 구조를 가지는 상태의 트리이다. 즉, 레벨이 n인 트리에서 2^n - 1개의 노드를 가지는 트리를 Perfect Binary Tree라고 한다.