🔷트리 개념
-계층적인 구조를 표현
조직도 , 디렉토리 ..
-트리는 노드들과 링크로 구성됨
맨 위 대장 노드를 root라고 부름
-부모-자식 관계
-형제 관계: 루트노드를 제외한 트리의 모든 노드들은 유일한 부모노드를 가짐. 이때 부모가 동일한 노드들을 형제관례라고 부름
-리프(leaf) 노드: 자식이 없는 노드들 (cf. 리프노드가 아닌 노드는 내부(internal)노드라 부름)
-조상-자손 관계:
-부트리(subtree): 어떤 한 노드와 그 노드의 자손들로 이루어진 트리
-레벨: 트리의 레벨을 구별함
-높이: 트리의 높이가 있음
-node가 n개인 트리는 항상 n-1개의 link를 가진다.
-같은 노드를 두번이상 방문하지 않는 조건하게 , 트리 루트에서 어떤 노드로 가는 경로는 유일하다.
🔷 이진트리
각 노드가 최대 2개의 자식을 가짐
각각의 자식 노드는 자신이 부모의 왼쪽인지 오른쪽인지 지정됨 (자식이 한명이 경우에도)
예: (x+y)*((a+b)/c) 같이 연산 순서가 있는 경우 노드로 나타낼때
하프만 코드: 어떤데이터를 압축or 인코딩할 때 최종적으로 파일 길이가 최소가 되도록 압축하는 알고리즘
full binary tree
-모든 레벨에서 노드가 차있는
-높이가 h 인 full binary tree는 2^h-1 개의 노드를 가짐
complete binary tree
-마지막 레벨을 제외한 노드는 다 차있어야하고, 마지막 레벨에 노드가 비어있어야할 경우 오른쪽에서 부터 순차적으로 비어지게
노드가 n개인 full 혹은 complete 이진 트리의 높이는 O(logN)이다.(노드가 N개인 이진트리의 높이는 최악의 경우 N이 될 수도 있다.)
