트리는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용하기도 한다.
그 중 이진 트리(binary tree)와 이진 탐색 트리(binary search tree)를 알아보자.
자식 노드가 최대 두 개인 노드들로 구성된 트리이다.
이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다.
이진 트리이면서, 특정 조건에 맞는 순서를 갖는 트리이다.
이진 탐색 트리의 모든 왼쪽 자식들은 루트나 부모보다 작은 값이고, 모든 오른쪽 자식들은 루트나 부모보다 큰 값을 가진다.
이진 탐색 트리는 균형 잡힌 트리가 아닐 때 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 가능성이 있기 때문에 삽입과 삭제마다 트리의 구조를 재조정하는 균형 이진 탐색 트리라는 개념이 등장했고, 균형을 잡기 위한 알고리즘을 도입할 수 있다.
@균형 이진 탐색 트리 참조 블로그
https://jackpot53.tistory.com/17.
특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다.
전위 순회
제일 처음 루트를 방문하고, 루트 기준 왼쪽 노드들을 둘러본 뒤, 왼쪽 노드 탐색이 끝나면 오른쪽 노드 탐색을 한다.
중위 순회
루트를 가운데 두고, 제일 왼쪽 끝에 있는 노드부트 순회하면다. 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동해 탐색한다.