[JS] 이진 탐색 트리

1. 이진 탐색 트리란? 이진 탐색 트리란 이진트리를 사용하기 위해서 저장할 데이터의 크기에 따라 노드의 위치를 정의한 것을 말한다. 이진 탐색 트리의 특징은 다음과 같다. 모든 원소는 서로 다른 유일한 키를 갖는다. 왼쪽 서브트리에 있는 원소의 크기는 그 루트의 키보다 작다. 오른쪽 서브트리에 있는 원소의 키는 그 루트의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 탐색 트리다. 이번 포스팅에서 다룰 것은 이진 탐색 트리에 대한 간략한 정의, 탐색, 삽입, 삭제 연산이다. 이진 트리의 순회에 대해서는 이전에 포스팅을 했으니 참고하길 바란다. 2. 탐색 연산 탐색은 항상 루트에서 시작된다. 따라서 먼저 키값과 루트 노드의 키값을 비교한다. 비교 결과는 다음의 세 가지 중 하나가 될 것이다. (키값 x =..

2020.06.12