비교 정책 결정
중복 값을 허용할지, 같으면 왼쪽/오른쪽 어디에 둘지 먼저 정합니다.
duplicate탐색 범위를 줄인다
현재 값보다 작으면 왼쪽, 크면 오른쪽으로 이동해 절반의 후보를 버립니다.
search삭제 케이스 분류
자식 0개, 1개, 2개일 때 처리가 다르며 2개는 successor/predecessor 교체가 필요합니다.
delete균형 문제 인식
정렬된 입력으로 삽입하면 높이가 N이 되어 BST가 linked list처럼 느려집니다.
height중복
정책 없이는 탐색과 삭제가 모호
카운트 필드를 두거나 한쪽 subtree로 보내는 규칙을
고정합니다.
policy
삭제
대체 노드가 subtree 범위를 지켜야 함
오른쪽 subtree의 최소값이나 왼쪽 subtree의 최대값을 주로
씁니다.
replace
편향
높이가 성능을 결정
평균 O(log N) 기대와 최악 O(N)을 구분해야 합니다.
complexity