학교공부/자료구조
[자료구조] Binary Search Tree
오늘은 '이진 탐색 트리'에 대해서 공부해보았다. 우선 이진 탐색 트리에 대해 알기 전에 '트리'라는 개념을 먼저 살펴보자. 이진 트리(Binary Tree) 트리란 그래프의 일종으로, 노드들이 나뭇가지처럼 연결된 형태를 띄는 비선형 자료구조이다. 비선형 자료구조라는 것은 스택, 큐와 같이 하나의 자료 뒤에 하나의 자료가 연결되어 있는 선형 자료구조와 달리 하나의 자료 뒤에 여러 개의 자료가 연결될 수 있는 구조를 뜻한다. 위 그림은 트리의 일종인 이진 트리의 예시 중 하나이다. 이진 트리는 자식 노드를 최대 두 개 가지는 트리를 뜻한다. 여기서 노드(node)란 위 그림에서 사각형 박스를 의미하며 일반적으로 데이터가 그 안에 담긴다. 그리고 이 노드들을 이어주는 선을 엣지(edge)라고 부른다. 어떤 ..
