Array, LinkedList, Stack, Queue 는 라임처럼 생긴 그냥 일직선의 데이터의 형태이다.
하지만 Tree는 부모, 자식 형태을 가진 구조이며, 계층이고 그룹이다. 이것을 가능하게 하는건 노드가 하나의 데이터를 가지고 있어서 가능하다.
Tree는 부모가 자식을 알고 자식도 부모를 알고 있는 경우가 있다. 다른 경우로는 부모가 자식 노드를 알고 있지만 자식은 부모 노드를 모르는 경우도 있다. 그리고 자식 노드 에서 더 이상 노드가 없는경우 Leaf 라고 부른다.
Binary Tree (이진트리)
부모 노드가 자식 노드를 2개 를 가진걸 Binary Tree 라고 한다. 하지만 노드에 무조건 2개의 노드만 붙으라는 법은 없다.
만약 3개의 노드가 붙은게 있다면 그것을 ternary Tree 라고 불린다.
그 중에서도 우리가 가장 많이 사용하는건 Binay Tree 이며 이 중 Binay Serach Tree(이진 검색 트리)에 대해서 알아보자.
Binary Tree는 2개의 자식 노드만 가지고 있으면 되지만 Binary Search Tree는 왼쪽 노드부터 작은 데이터값이 들어가 있어야 한다. 부모 트리보다 큰 값을 찾고 싶으면 오른쪽 노드를 찾으면되고 낮은 값을 찾고 싶으면 왼쪽 노드를 찾으면 된다.
Balanced, unBalanced
Balanced 처럼 균형에 맞게 트리가 되어있는게 있고 unbalanced 처럼 균형이 안맞는 Tree 가 있다.
Balanced 에서 대표적인 Tree는 red-blackTree , AVL tree 2개가 있다.
Complete Binary Tree(완전 이진 트리), Full Binary Tree
위의 사진 처럼 Complete Binay Tree는 각 레벨이 맞으며넛 node가 왼쪽부터 차례대로 채워져있는걸 말한다.
Full Binary Tree는 왼쪽그림처럼 부모노드 아래 2개의 자식 노드가 있는 상태면 Full Binary Tree 라고 한다. 한마디로 자식의 노드를 무조건 2개를 가져야한다면 FullBinary Tree를 사용해야하고 1개의 자식노드도 가질수 있다면 COmplete Binary Tree를 사용하면 된다.
Perfect Binary Tree
자식노드가 왼쪽에 2개만 채워져 있으면 Full Binary Tree 라 하고 오른쪽 자식노드까지 2개가 채워져 있으면 Perfery Binary Tree 라고 한다.
총 정리
-----------------------------------------------------------------------------------------------
1. Array, LinkedList, Statk, Queue 는 일직선 형태의 데이터를 저장을 한다.
2. Tree 는 Binary Tree, Binary Search Tree, Balanced, unBalanced, Complete Tree, Full Binanry Tree, Perfert Binnary Tree 가 있다.
3. 공통점으로는 부모 노드 보다 작은 값은 왼쪽, 높은 값은 오른쪽에 있어야한다.
4. 왼쪽에 2개의 노드가 무조건 있어야하면 Full Binanry Tree, 오른쪽 노드에도 2개가 무조건 이어야 하면 Perfery Binnay Tree 이다.