트리와 이진 트리(Binary Tree)

 

트리 구조란

그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 그리고 부모 노드와 자식 노드로 이루어진 구조이다.

간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.(ko.wikipedia.org/wiki/트리_구조)

이진트리란 (Binary Tree)

컴퓨터에서 쓰이는 이진트리는 수학과 다르다.

컴퓨터에서 이진트리는 부모 노드가 최대 두 개의 자식 노드를 가지는 트리 구조이다.

 

이진 트리의 조건들

한 부모 노드에 자식 노드는 최소 0부터 최대 2개의  자식 노드를 가질 수 있다.

부모보다 작으면 왼쪽 자식 부모보다 크면 오른쪽 자식으로 보내야 한다.

이진트리를 순회하는 방식은 4가지가 있다. 1. 전위 순회 2. 중위 순회 3. 후위 순회 4. 레벨 순회편향 이진트리란 (Skewed binary tree)

자식 노드들이 한쪽으로 편향되어있는 트리구조

연결 리스트로 구현하지 않고 배열(인덱스)로 구현한다면 낭비되는 공간이 많다.

정 이진트리란 (Full binary tree)

각 부모 노드의 자식 노드는 짝수 개만 가능하다.

완전 이진트리란 (Complete binary tree)

완전 이진트리

완전 이진트리 X

 

자식 노드가 항상 왼쪽부터 차근차근 1~n까지 채워나가며 만들어지는 트리구조이다.

완전 이진 트리의 장점은 트리를 배열로 쉽게 구현이 가능하며 부모 노드와 자식 노드 간에 관계를 수식화 할 수 있다.

 

노드에 있는 값을 index 값으로 가정하면

• 부모 노드 index 값 - 자식 노드 index 값 / 2
• 왼쪽 자식 노드 index 값 - 부모 노드 index* 2
• 오른쪽 자식 노드 index 값 - 부모 노드 index * 2 + 1

포화 이진트리란 (Perfect binary tree)

모든 부모 노드에 자식 노드가 2개씩 있는 트리구조이다.