[파이썬 알고리즘] 이진트리 기초 개념(1)

트리

- 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조이다.

- 비선형 구조이다

 

선형구조 vs 비선형구조

- 앞서 보인 큐(Queue), 스택(Stack)은 자료구조에서 선형 구조라고 한다.

- 선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미한다

- 비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어 있다.

- 선형구조와 비선형구조의 차이점은 형태뿐만 아니라 용도에서도 차이점이 많다.

- 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다.

 

 

* 아래 폴더 구조가 대표적인 트리의 형태다.

 

트리에서 나오는 용어

Node: 트리에서 데이터를 저장하는 기본 요소

Root Node: 트리 맨 위에 있는 노드

Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄

Parent Node: 어떤 노드의 상위 레벨에 연결된 노드

Child Node: 어떤 노드의 하위 레벨에 연결된 노드

Leaf Node(Terminal Node): Child Node가 하나도 없는 노드

Sibling: 동일한 Parent Node를 가진 노드

Depth: 트리에서 Node가 가질 수 있는 최대 Level

Graph vs Tree 

트리는 순환 구조를 갖지 않는, 루트가 하나인 그래프

 

트리의 종류

- 트리는 이진트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등 다양한 트리가 있다.

- 이진트리의 특징은 바로 각 노드가 최대 두 개의 자식을 가진다는 것이다.

- 완전 이진 트리의 특징은 바로 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다.

 

완전 이진 트리를 배열로 표현

- 트리 구조를 표현하는 방법은 직접 클래스를 구현해서 사용하는 방법이 있고, 배열로 표현하는 방법이 있다.

- 완전 이진 트리를 쓰는 경우에 사용할 수 있다.

- 완전 이진 트리는 왼쪽부터 데이터가 쌓이게 되는데, 이를 순서대로 배열에 쌓으면서 표현할 수 있다.

 

완전 이진 트리의 높이

- 트리의 높이(Height)는, 루트 노드부터 가장 아래 리프 노드까지의 길이다.

 

- 노드가 꽉 차있으면 최대 몇 개가 있는지 생각해보자.

- 레벨을 k라고 한다면 각 레벨에 최대로 들어갈 수 있는 노드의 개수는 2^k 개수 임을 알수 있다.

 

- 만약 높이가 h인데 모든 노드가 꽉 차 있는 완전 이진 트리라면 모든 노드의 개수는 몇 개 일까?

- 그러면 이 때 최대 노드의 개수가 N이라면 , h는 뭘까?

 

N = 2^(h+1) - 1

->

h = log_2(N+1)-1

 

- 이진 트리의 높이는 최대로 해봤자 0(log(N)) 이다!