BST Ordering Invariant | Data Structure | Pusan National University

부분 트리 전체조건은 부모와 자식 한 쌍이 아니라 그 노드 아래의 모든 키에 걸린다.

허용 범위루트에서 내려오며 지나온 노드들이 하한과 상한을 하나씩 좁힌다.

중복 키이 강의의 Map 방식은 같은 키를 다시 넣으면 기존 값을 갱신하므로 트리에 같은 키가 두 번 나오지 않는다.

중위 순회(inorder traversal)ordering invariant를 지키는 트리를 중위 순회로 읽으면 키가 오름차순으로 나온다.

부모보다 크기만 하면 되는 것이 아니라 조상 모두와의 대소가 맞아야 한다

3의 오른쪽 자식 노드 자리에 넣을 키를 바꾸면 부모 3과의 비교, 루트 8과의 비교, 그리고 그 자리에 허용되는 범위 안에 있는지가 함께 바뀐다.

3의 오른쪽 자식 노드 키 10

점선 영역은 루트 8의 왼쪽 부분 트리다. 초록 원이 바꾸는 자리이고, 빨간 원은 ordering invariant를 어긴 키다. 아래 수직선의 초록 띠는 그 자리에 올 수 있는 열린 범위이고 점이 현재 키다.

is_bst는 허용 범위를 내려보내며 노드마다 한 번씩 검사한다

트리를 고르고 호출 수를 옮기면 지금 검사하는 노드, 그 노드가 받은 (low, high) 범위, 코드에서 실행 중인 줄이 바뀐다. 두 트리 모두 부모와 자식 한 쌍씩만 보면 대소가 맞다.

트리

검사한 노드 수 0

초록 원이 지금 검사하는 노드, 옅은 파란 원이 통과한 노드, 빨간 원이 범위를 벗어난 노드, 점선 원이 검사하지 않은 노드다. 원 아래 괄호가 그 노드가 받은 (low, high)이고 원 위 수가 검사 순서다. 코드의 초록 줄은 방금 실행한 판정, 빨간 줄은 False를 돌려준 줄이다.

ordering invariant를 지키면 중위 순회의 출력이 오름차순이 된다

같은 두 트리를 중위 순회로 읽는다. 출력한 키 수를 옮기면 방문 순서와 출력 칸이 늘어나고, 앞 키보다 작은 키가 나오는 곳이 드러난다.

트리

출력한 키 수 6

원 위 수가 중위 순회의 방문 순서이고 초록 원이 마지막으로 출력한 노드다. 아래 칸은 왼쪽부터 출력 순서이며 빨간 칸은 바로 앞 키보다 작은 키다.