Tree

Tree

-단방향 그래프의 한 구조, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태
-트리에는 사이클(cycle)이 존재할 수 없다

노드(Node) : 트리 구조를 이루는 모든 개별 데이터
루트(Root) : 트리 구조의 시작점이 되는 노드
부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

레벨(level): 루트 노드(level=0)부터 노드까지 연결된 간선 수의 합
높이(height): 가장 긴 루트 경로의 길이
서브 트리: 트리 구조를 갖춘 작은 트리

이진트리(Binary Tree)

-이진트리는 각 노드가 최대 두 개의 자식을 갖는다
-각 노드는 자식이 업거나 최대 2개까지 가지고 있을 수 있다

이진 탐색 트리(Binary Search Tree, BST)

이진 탐색 트리는 이진트리이면서 아래와 같은 속성을 갖는 트리를 뜻한다

-이진 탐색 트리의 노드에 저장된 키(key)는 유일하다
-부모의 키가 왼쪽 자식 노드의 키보다 크다
-부모의 키가 오른쪽 자식 노드의 키보다 작다
-왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다

이진 탐색 트리는 효율적인 탐색을 위해 고안된 트리이다