오늘 배운 것

자료 구조

1. Tree

트리는 노드로 구성된 계층적 자료구조.

트리에는 루트(최상위 노드)가 존재하고, 루트에서부터 시작해서 자식노드들이 아래로 뻗어나가게 된다.

• A는 트리 구조의 최상위에 위치한 노드로서, Root라고 부른다. 트리는 오직 하나의 루트 노드를 갖는다.
• A, B, C는 트리의 구성요소인 노드(Node).
• 깊이(Depth)는 Root 0을 기준으로, 루트에서부터 어떤 노드에 접근하기 위한 거리를 의미한다. 노드 D의 Depth는 2이다.
• 같은 Depth에 존재하는 노드들은 형제(Sibiling) 관계에 있다.
• 높이(Height)는 루트에서부터 마지막 노드까지 도달하는데 필요한 간선(Edge)의 수이다. 위 트리에서 높이는 4이다.
• B는 A의 자식(Child)이자 D와 E의 부모(Parent)이고, E는 B의 자식(Child)이자 J의 부모(Parent)이다.
• H, I, F와 같이 자식이 없는 노드는 말단 노드(Leaf Node)라고 부른다.
• 트리는 방향성이 있는 비순환 그래프의 한 종류이다.
• 모든 자식노드들은 한 개의 부모만을 가진다.
• 루트에서 어떤 노드로 가는 경로는 유일하다. 임의의 두 노드 간의 경로도 유일하다.
• 트리에는 이진 트리, 이진 탐색 트리, 균형 트리, 이진 힙 등이 있다.

2. Binary Serach Tree

이진 탐색 트리(Binary Search Tree)는 최대 2개의 자식만을 갖는 트리이다.

노드의 왼쪽 자식 노드에는 노드의 값보다 작은 값이 위치하고, 오른쪽 자식 노드에는 노드의 값보다 크거나 같은 값이 위치한다.