BINARY SEARCH TREE
삽입·탐색·삭제는 같은 불변식을 지키는 작업이다
매 노드에서 왼쪽은 작고 오른쪽은 커야 합니다. 삭제는 이 규칙을 깨뜨리기 쉬우므로 자식 수로 먼저 분기합니다.
left < node < right중위 순회 결과가 오름차순이면 트리의 순서 약속이 유지된
것입니다.
삽입키를 비교해 작으면 왼쪽, 크면 오른쪽으로 내려갑니다. 빈 위치에만
새 노드를 둡니다.single path
탐색비교 결과가 한쪽 서브트리를 통째로 버리게 해 줍니다. 균형이
좋을수록 빨라집니다.compare
삭제자식 0개는 제거, 1개는 승격, 2개는 후속자나 선행자로
치환합니다.0 / 1 / 2 child
검증2자식 삭제 뒤에는 치환에 사용한 원래 노드까지 삭제했는지 중복을
확인합니다.inorder
핵심: 삭제 구현이 맞는지는 모양보다 순서로 판단합니다. `1, 6,
8, 10`처럼 정렬되고 중복이 없어야 합니다.