이진탐색+연결리스트
이진탐색: 탐색 시 O(logN) but 삽입, 삭제 불가능
연결리스트: 삽입, 삭제 시 O(1) but 탐색 시 O(N)
두 가지를 합해서 장점을 얻은 것이 이진 탐색 트리이다.
1. 이진탐색트리란?
- 각 노드의 자식이 2개 이하이다.
- 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다.
- 중복 허용 X
- BST는 검색 목적 자료구조인데, 중복이 많은 경우 트리를 사용하면 검색 속도가 더 느려진다.
- 이 경우에는 노드에 해당 값의 count를 갖게 하여 처리하는 것이 더 효율적이다.
- 중위순회로 정렬된 순서를 읽을 수 있다.
2. 삭제
① 리프 노드 삭제 시: 그냥 삭제
② 자식 1개인 노드 삭제 시: 지워진 위치에 자식 노드 올리기
③ 자식 2개인 노드 삭제 시: 오른쪽 자식 중 가장 왼쪽 or 왼쪽 자식 중 가장 오른쪽에 있는 노드 올리기
편향될 경우 탐색 시 O(N)의 시간이 걸린다.
이를 보완한 것이 AVL트리, RB트리이다.
