binary search tree 특징

이진 탐색 트리 = 이진탐색 + 연결리스트 두 가지의 장점을 합쳐서 만든 것 이진탐색 시 O(logN), 삽입/삭제 불가능 연결리스트 삽입/삭제 시 O(1), 탐색 시 O(N) 각 노드의 자식이 2개 이하 왼쪽은 부모보다 작고, 오른쪽은 부모보다 큼 중복된 노드 X (검색 목적이므로 중복 존재로 느리게 만들 필요 X, 트리 삽입보다 노드가 count를 가지게 하는 것이 효율적) 순회 in-order 중위순회 방식으로 읽을 때 정렬된 순서대로 읽을 수 있음 연산 검색, 삽입, 삭제, 트리 생성, 트리 삭제 시간복잡도 균등 트리 : 노드 개수 N, O(logN) 편향 트리 : 노드 개수 N, O(N) (편향 트리를 바로잡도록 도와주는 개선된 tree가 AVL, RedBlack Tree) 삽입 Root 에서 ..