트리(Tree)란?
트리는 노드와 간선으로 이루어진 계층적 관계를 표현하는 자료구조이다.
스택이나 큐와 같이 선형 구조가 아닌 비선형 구조이다.
그림과 같이 나무를 거꾸로 뒤집어 놓은 듯한 형태를 볼 수 있다.
트리 용어
노드(Node) : 트리의 구성요소에 해당하는 요소(A,B,C,D...)
간선(Edge) : 노드와 노드를 연결하는 연결선
루트(root) : 부모가 없는 노드(A)
내부노드(internal node): 적어도 한 개의 자식을 가진 노드(A,B,C ...)
리프노드(leaf node) : 자식이 없는 노드(H, I, J ...)
형제(siblings): 같은 부모를 가진 노드들(F,G)
부모(parent) : 노드의 바로 윗 노드(H의 부모는 I)
자식(child) : 노드의 바로 아래 노드(B의 자식은 D,E)
깊이(depth): 루트로부터 노드에 이르는 유일한 경로의 길이
높이(height): 노드로부터 외부노드에 이르는 가장 긴 경로의 길이
이진트리(Binary Tree)
트리 자료구조에서 가장 많이 사용되는 트리는
이진트리이다.
이진트리는 트리의 각 내부노드가 두 개의 자식(left, right)을 가진다.
위 그림은 이진트리이다. 그림을 보면 모든 노드가 2개의 서브트리를 가지고 있다. 이 때 서브트리는 공백을 가질 수 있다.
포화 이진트리
leaf노드를 제외한 모든 노드가 정확히 2개의 자식 노드를 갖는다. 또한 모든 leaf노드는 레벨이 같고 모든 노드가 채워져야 한다.
즉 노드의 개수 N = 2^(높이) - 1이다.
완전 이진트리
높이가 h인 이진트리를 노드의 레벨 순에 따라 노드 번호를 붙일 때 각 노드의 번호 위치가 포화 이진트리 번호 1에서 n까지 모두 일치하는 트리이다.
위 트리는 레벨 순으로 노드가 순서대로 구성되어 있다고 볼 수 있다.
편향 이진트리
편향 이진트리란 트리가 한 쪽으로 치우쳐져 있는 트리를 말한다.
좌측 트리의 경우 트리가 왼쪽으로 편향되어 있어 우측 트리의 경우 트리가 오른쪽으로 편향되어 있다.
