GW LABS

앞서 포스팅한 이진 트리에서 특별한 속성을 갖고 있는 이진 탐색 트리는 어떤 값을 검색하는 데에 좋은 성능을 보여주는 자료구조이다. 직접 구현해보면서 어려웠던 점이 많았었는데 하나씩 모르던 부분을 알게 되는 기분이다. 그럼 이진 탐색 트리에 대해 자세히 알아보자. 1. Binary Search Tree 이진 탐색 트리는 루트 노드를 기준으로 왼쪽에는 작은 값을, 오른쪽에는 큰 값을 갖는 이진 트리의 한 종류이다. 모든 노드는 자신을 기준으로 왼쪽 자식값은 자신보다 작고, 오른쪽 자식값은 자신보다 큰 구조를 갖고 있다. 2. 검색, 삽입, 삭제 이진 탐색 트리에서 검색을 수행하는 방법은 지난 포스팅의 재귀적 탐색방법을 사용하면 되는데 로직이 하나 추가된다. 검색하고자 하는 값이 현재 노드보다 크다면 오른쪽..