Search Tree

Younji Kim / October 2022

트리(Tree)

계층적인 구조를 표현한 것으로, 실생활에서 흔히 볼 수 있는 조직도나 가계도가 트리의 형태를 이루고 있다. 트리는 데이터 요소를 가리키는 노드(node)와 노드들을 연결하는 링크(link 또는 edge, branch)로 구성되어 있다. 트리의 개념 중 헷갈리기 쉬운 개념들을 아래 불렛 리스트로 정리하겠다.

• leaf 노드 : 자식이 없는 노드들
• 노드가 N개인 트리는 항상 N-1개의 링크를 가진다.
• 루트 노드에서 어떤 노드로 가는 경로는 단 하나뿐이다. 같은 노드를 두 번 이상 방문하지 않기 때문.

이진 트리(binary tree)

이진 트리란 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리를 말한다. 각 자식 노드는 자식 노드가 하나일 경우일지라도 자신이 왼쪽 자식인지 오른쪽 자식인지 지정된다. 컴퓨터에서 쓰이는 이진 트리의 예는 연산 우선순위가 정해져있는 수식이나 허프만 코드 등이 있다. 이진 트리 중에서도 특이한 트리들이 있다.

• 정이진트리(full binary tree) :
• 완전이진트리(complete binary tree) :

이진 탐색 트리 (binary-search tree)

이진 탐색: 연결 리스트: