이진탐색트리의 목적은?
이진탐색 + 연결리스트
이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN), but 삽입, 삭제가 불가능
연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), but 탐색하는 시간복잡도가 O(N)
이 두가지를 합하여 장점을 모두 얻는 것이 ‘이진탐색트리’
즉, 효율적인 탐색 능력을 가지고, 자료의 삽입 삭제도 가능하게 만들자
중복이 없어야하는 이유는?
검색 목적 자료구조인데, 굳이 중복이 많은 경우에 트리를 사용하여 검색 속도를 느리게 할 필요가 없음(트리에 삽입하는 것보다, 노드에 count값을 가지게 하여 처리하는 것이 훨씬 효율적)
이진탐색트리의 순회는 ‘중위순회(in-order)’방식(왼쪽-루트-오른쪽)
중위 순회로 정렬된 순서를 읽을 수 있음