Tree Definition : 하나 이상의 노드로 이루어진 유한집합
하나의 root node
나머지 노드들은 n개의 분리 집합 T1, T2, … Tn으로 분할
특징 :
원소들 간에 1:n 관계를 가지는 비선형 자료구조
원소들 간에 계층 관계를 가지는 계층형 자료구조
구성요소 : node, edge
<이진 트리>
모든 노드가 최대 2개의 서브트리를 갖는 트리
재귀적 구성
<완전 이진 트리>
레벨 1부터 k-1까지 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리
* n개의 노드를 가진 완전 이진트리의 높이 = log(n+1)
이진트리의 표현
1. 배열
2. 연결리스트
이진트리의 순회
1. 중위순회(inorder traversal) -> 중위표기식 구할 수 있음
왼쪽 서브트리 방문, 루트 노드 방문, 오른쪽 서브트리 방문
2. 전위순회(preorder traversal) -> 전위표기식 구할 수 있음
루트 노드 방문, 왼쪽 서브트리 방문, 오른쪽 서브트리 방문
3. 후위순회(postorder traversal)-> 후위표기식 구할 수 있음
왼쪽 서브트리 방문, 오른쪽 서브트리 방문, 루트노드 방문
*일반트리를 이진트리로 변환
첫 번째 자식 노드 간선만 남기고 나머지 간선 제거 -> 형제 노드를 간선으로 연결
<ex: 수식트리 구현>
<<Priority Queue>>
우선수위를 근거로 dequeue 연산이 진행
구현방법 1. 배열 2. 연결리스트 3. 힙(Heap)
Heap을 이용할 시 O(logN)으로 삽입삭제 시간이 줄어듬
<Heap>
완전이진트리로 우선순위 개념을 큐에 도입한 자료구조
우선 순위가 높은 데이터가 먼저 나간다.
1. Max Heap
2. Min Heap
부모와 자식의 데이터 값 같은 경우 허용
<이진 탐색 트리>
탐색을 효율적으로 하기 위한 자료구조
특징 : 이진트리이며 모든 원소는 다른 유일한 key를 가짐
왼쪽 서브트리의 key < 루트의 key < 오른쪽 서브트리의 key
삽입 : 탐색실패한 위치의 왼쪽 or 오른쪽에 삽입
삭제 : 삭제 노드 차수 0, 1, 2에 따라 case나눔
<일반 트리>
자식의 개수에 제한이 없는 트리