자료구조 트리 이론 진짜 조금 (히프, 이진트리, 이진 탐색은 어렵네 등)

트리 (tree)

원소들 간에 1:다 관계와 계층관계를 가지는 비선형이자 계층형 자료구조 형태

자식, 부모, 조상, 자손 등의 개념을 가지고 있음

 

노드(node) - 트리의 원소

루트 노드 - 트리의 시작 노드

간선 - 노드를 연결 하는 선, 부모 - 자식 연결

형제 노드 - 같은 부모 노드의 자식 노드들

조상 노드 - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들

서브 트리 - 자식 노드와 연결된 간선을 끊었을 때 생성되는 트리

(각 노드는 자식 노드의 개수 만큼 서브 트리를 가짐) -> 이 것들의 집합 : 포리스트

자손 노드(후손) - 서브 트리에 있는 하위 레벨의 모든 노드들 

 

차수

- 노드의 차수 : 노드에 연결된 자식 노드의 수

- 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값

- 단말 노드 : 차수가 0인 노드, 자식 없는 노드 

 

높이

- 노드의 높이 : 노드의 레벨, 루트에서 노드에 이르는 간선의 수

- 트리의 높이 : 노드의 높이 중에서 가장 큰 값

 

이진트리

최대 2개의 자식

-> 관리가 수월함

똑같은 구조로 처리 가능, 하나의 처리 방법으로 트리 전체 처리 가능

N개의 노드의 이진트리는 항상 (N-1)개의 간선

높이가 h인 이진 트리의 노드의 최소 개수 (h+1), 최대 개수 2의 h+1 제곱 -1

 

포화 이진트리

모든 레벨에 노드가 포화상태로 차 있는 이진트리 (최대 노드 개수 -  2의 h+1 제곱 -1의 노드를 가짐)

 

완전 이진트리

다 2개씩 포화된 상태는 아님

자녀들이 놓여진 순서만 잘 지키면 됨

 

편향 이진트리

최소 개수의 노드를 가지면서 한 방향으로만 이루어짐

 

순차 자료구조 이용한 이진트리 

포화 이진트리의 노드번호를 배열의 인덱스로 사용

인덱스 0은 비어둠

-> 계산의 편의성, 레벨0의 노드의 개수가 2의 0제곱 1이기에 인덱스 1번부터 루트를 저장하여 시작

단점 : 공간 낭비, 배열의 크기 변경 어려움

 

 

 

연결 자료구조를 이용한 이진트리 

단순 연결 리스트를 사용 (모양은 이중연결리스트 같 - 왼쪽과 오른쪽 자식 노드가 있기에)

 

순회

계층적 구조로 저장되어 있는 트리의 모든 노드를 방문하여 데이터를 처리 / 서브트리로 분할되어 컨트롤 가능

왼쪽 서브트리에 대한 순회를 오른쪽 서브트리 보다 먼저 수행 

(전위 순회, 중위 순회, 후위 순회)

 

실습 코드표 확인하기

 

이진탐색트리

모든 원소는 서로 다른 유일한 키를 갖는다

왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 작다

오른쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 크다

왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색트리이다

 

삽입 (탐색 연산 -> 탐색 실패 위치에 해당 원소 삽입)

삭제 (탐색 연산 -> 찾은 노드 삭제 -> 후속처리 / 단말 / 자식1명 / 자식 2명)

 

이것도 실습 코드랑 예제 사진들 확인하기

 

히프

완전 이진트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조

- 완전 이진트리 구조여야함

- 부모와 자식간의 크기 관계를 잘 성립해야 함.