트리 (Tree), 이진 트리 (Binary Tree)

트리란

트리는 부모-자식 관계의 노드들로 이루어져있으며, 계층적인 구조를 나타내는 자료구조

노드가 N개인 트리는 항상 N-1개의 간선을 가짐

https://suyeon96.tistory.com/29

트리 용어

노드(node): 트리를 구성하는 기본 원소

루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점

부모 노드(parent node): 상위 레벨로 직접 연결된 노드

자식 노드(child node): 하위 레벨로 직접 연결된 노드

형제 노드(siblings node): 같은 부모 노드를 갖는 노드들

리프 노드(leaf (node))/단말 노드(terminal node): 자식이 없는 노드

간선(edge): 노드간의 연결선

레벨(level): 깊이가 같은 노드끼리의 집합

높이(height): 가장 긴 루트 경로의 길이

차수(degree): 각 노드의 자식의 개수

트리의 차수(degree of tree): 트리의 최대 차수 = max[deg1, deg2, ..., degn]

경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서

길이(length): 출발 노드에서 도착 노드까지 거치는 노드의 개수

깊이(depth): 루트 노드부터 노드까지 연결된 간선 수의 합

크기(size): 노드의 개수

너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기

트리 구현의 문제점

만약 하나의 노드가 여러개의 자식노드를 가지는 불규칙한 트리의 경우 node를 구현하기가 상당히 복잡해진다.
이러한 이유로 실제로는 하나의 노드가 2개의 자식노드만 가지는 이진트리가 많이 사용된다.

 

이진 트리 (binary tree)

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 형태

https://kingpodo.tistory.com/27

https://kingpodo.tistory.com/27

 

편향 이진 트리(skewed binary tree)

편향 이진 트리란 모든 노드가 부모의 왼쪽 또는 오른쪽으로  편향 되어 있는 트리

https://kingpodo.tistory.com/27

 

포화 이진 트리 (full binary tree)

이진 트리가 보유 할 수 있는 최대 노드를 가지고 있는 형태의 트리

높이가 h인 이진 트리에서 있을 수 있는 최대 노드 수 => 2^h-1

https://kingpodo.tistory.com/27

 

완전 이진 트리 (complete binary tree)

노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 이진 트리