728x90

Q. 주어진 Node가 이진 탐색 트리(Binary Search Tree)로서 유효한지 확인하는 function을 작성하라.
(left node는 node.data보다 작으며, right node는 node.data보다 크다는 것을 명심)

문제 이해를 위한 이진 탐색 트리 이미지화

🎈 현재 node의 왼쪽 node현재 node보다 작으며, 오른쪽 node현재 node보다 큰 것BST다.

해당 node를 기준으로 작은가? 큰가?를 파악해주면 된다.
그러기 위해서는 기준을 잡아줄 max 또는 min을 설정해주면 비교하기가 더욱 쉬워 진다.

max, min을 비교하여 BST를 검사하는 트리 구조 이미지화

🧨 function의 argument로 min, max를 넣어주면 편할 것이고,
max보다 크거나, min보다 작으면 false를 반환해줄 조건문이 있어야할 것이다.
또한, 트리를 탐색하며 검색하므로 재귀를 써주면 효율적일 것이다.
라는 생각을 하면서 문제 풀이를 시작해주면 된다.

Validate 정답 코드

🔮 argument로 minmaxdefault null을 설정해주고 시작하자.

우선, 17-23번째 코드가 가장 먼저 떠올리기 쉽다.
root부터 탐색을 시작할 때, 왼쪽 노드가 있고 && 왼쪽 노드 값이 지금 노드의 값보다 크지 않으면 true다.
만약 커서 false를 return받으면, false를 계속 반환하여 처음 재귀를 호출한 조건문에 가서 끝낸다.
더 이상 탐색할 이유가 없기 때문이다.
만약 false 조건에 걸리지 않으면 이렇게 BST를 끝까지 내려가며 validate이 재귀로 작동한다.
이와 마찬가지로 오른쪽 노드도 생각해주면 된다.

재귀로 실행되며 max와 min을 확인하는 조건문을 살펴보자(9-15번째 코드)
왼쪽 노드는 무조건 상위 노드보다 크면 안되며, 오른쪽 노드는 무조건 상위 노드보다 작으면 안된다고 반복해왔다.
따라서, 왼쪽 노드를 검사할 때는 상위 노드를 max로 잡고, max보다 크면 false를 return해주면 된다.
또한, 오른쪽은 상위 기준으로 min보다 작으면 false를 return해준다.

예외 사항을 파악하기 위한 BST Validate 이미지

예외 사항이 있다. 위 그림을 통해 예외 사항을 살펴보자.
왼쪽에 노드가 있으며 상위 노드보다 작거나, 오른쪽에 노드가 있으며 상위 노드보다 크지만
애초에 들어와서는 안 될 값을 체크해줘야 한다. '15'를 보자.
이 경우, -1노드의 오른쪽에 있으며 -1보다 큰 값을 갖고 있다. BST의 정의에 따르면 위치가 맞긴 하다.

하지만, 애초에 '10'노드를 기준으로 오른쪽에 삽입되었어야 할 노드다.
이런 경우는 17-23번째 코드에서 작성한 validate 재귀로 해결된다.

왼쪽 노드를 검사할 때, max는 상위 노드 기준으로 입력되지만,
오른쪽 노드를 검사할 때는 max는 '-1'기준 상위 노드 값(0)이 유지되며,
min값은 '15'로 노드가 위치하면서 그 상위 노드 값인 '-1'이 들어가기 때문이다.
따라서 '15'는 max(0)보다는 크지만, min(-1)보다는 작기 때문에 false를 return한다.
이렇게 유효성 검사를 마무리해 줄 수 있다.

이렇게 반복해서 false를 확인해주고, false가 하나도 발생하지 않는다면 올바른 BST이므로 true를 반환해주면 된다.

📌 if(max && node.data >) 이런식으로 'max가 있을 때'로 전제하여 코드를 작성해주면 안 된다.
만약 -1값이 들어오면 -1은 false이기 때문에 해당 조건문을 실행하지 않기 때문이다.
또한, ture or false값을 최종적으로 받아야하기 때문에 return이 필요한 곳에 return은 잘 넣어주는 게 중요하다.

👏 이해하기 상당히 어려운 알고리즘이다. 계속 디버깅을 하면서 값의 이동과 재귀의 흐름을 파악해주는게 이해의 지름길이다!

+ Recent posts