[Hackerrank] Binary Tree Nodes

https://www.hackerrank.com/challenges/binary-search-tree-1/problem?isFullScreen=true 

Binary Tree Nodes | HackerRank

 

<풀이 과정>

 

1. 재귀 CTE 문 이용하기

WITH RECURSIVE TMP AS(
    SELECT N, P, 1 AS DEPT FROM BST WHERE P IS null
    UNION ALL
    SELECT BST.N, BST.P, TMP.DEPT+1 AS DEPT
    FROM TMP INNER JOIN BST ON TMP.N = BST.P)

SELECT N, CASE WHEN DEPT = (SELECT MIN(DEPT) FROM TMP) THEN "Root"
            WHEN DEPT = (SELECT MAX(DEPT) FROM TMP) THEN "Leaf"
            ELSE "Inner" end as node FROM TMP ORDER BY N ;

 데이터가 트리 구조를 띠고 있기 때문에 재귀 CTE문을 사용해서 풀고 싶었다. (CTE문 공부할 겸 풀긴 했는데 성능은 다른 방식이 더 좋다고 한다) 반복문을 통해 노드의 뎁스를 구하고, 가장 크기가 큰 뎁스는 leaf, 낮은 뎁스는 root, 나머지는 inner 로 처리하는 방식이다. 

 

 

2. CASE WHEN 사용하기

SELECT N, 
	(CASE WHEN P IS NULL THEN "Root" 
		WHEN N IN (SELECT DISTINCT P FROM BST) THEN "Inner"
		ELSE "Leaf" END AS node)
FROM BST
ORDER BY N

 CASE WHEN 으로 푸는 방식은 사실 쉽다. 부모 노드가 없으면 "Root"가 되는 거고, 부모 노드에 포함되지 않은 노드들은 "Leaf"가 된다. 다만 고려해볼 문제가 있다.

 

 

2-1 NOT IN VS IN

 

 LEAF 와 INNER를 결정할 때, 두 가지 방식을 생각해볼 수 있다. N이 P에 들어있지 않는 경우를 LEAF로 처리하고 ELSE로 INNER를 구하는 경우와, P에 들어있는 N를 INNER로 지정하고 ELSE로 LEAF를 처리하는 경우다.

 

           <N이 P에 들어있지 않은 경우 LEAF>                                                <P에 들어있는 N의 경우 INNER> 

 볼 때는 별 차이가 없어보이지만 NOT IN으로 하는 경우 결과값이 제대로 나오지 않는다. LEAF로 적용되어야 하는 경우에도 INNER로 처리된다.  N과 (SELECT DISTINCT P FROM BST)의 값을 비교하는 과정에서 NULL값 때문에 오류가 난다. (SELECT DISTINCT P FROM BST)의 결과값이 NULL, 2, 4 가 있다고 생각해보자. 그럼 N != NULL, N != 2, N != 4 부분을 모두 통과해야 제대로 LEAF로 결과가 나올 것이다. 그런데 N != NULL 부분에서 오류가 난다. NULL은 값이 없기때문에, 스칼라 연산자인 != 를 수행할 수 없기 때문이다. N!= NULL의 결과값은 FASLE, TRUE 도 아닌 Unknown 으로 나오므로 N이 조건을 만족하지 못해 INNER 값이 나오게 된다.

반면 IN 으로 수행하는 경우에는 N = NULL, N = 2, N = 4 중 하나만 통과해도 Inner로 처리되기 때문에 ELSE도 제대로 처리되며 LEAF 값도 정상적으로 도출된다.

 

 

 

2-2 CASE WHEN 순서

SELECT N, 
	CASE WHEN  N IN (SELECT DISTINCT P FROM BST) THEN "Inner"
		WHEN P IS NULL THEN "Root"
		ELSE "Leaf" end as node
FROM BST
ORDER BY N

 위 코드는 2-1에 나온 코드와 똑같다. WHEN 조건절의 순서를 제외한다면 말이다. 앞 정답 코드에는 P IN NULL THEN ROOT 조건절 다음에 INNER 조건절이 나오고, 위의 코드에서는 INNER 다음에 ROOT 조건절이 온다. 별 상관이 없다고 생각했지만?? 순서를 잘 지키지 않아도 잘못된 결과 값이 나온다. INNER 조건절의 비교 대상인 SELECT DISTINCT P 부분에 NULL이 포함되어 있기 때문이다. CASE WHEN 안에서도 순서가 있는 듯하다. 먼저 오는 조건절을 실행한 뒤에 다음 조건절을 돌리는 듯 하다. 공통된 부분이 있다면 조건절 순서에도 주의를 해야할 필요가 있다.

 

 

 

 

+ CASE WHEN 순서에 따른 성능 고찰

 앞에 말한 것처럼 조건절 안의 순서대로 돌아가기 때문에, 어느 절을 먼저 위치시키냐에 따라 성능이 좋아질 수 있다. 예를 들어보자.

 

CASE WHEN A = 1 THEN A

       WHEN B = 2 THEN B

       ELSE C

       END AS TMP

 

A=1 를 만족하는 경우가 1000만개고 B = 2 를 만족하는 경우가 300개가 있다고 해보자. 그러면 처음부터 돌아가기 때문에 대부분이 A = 1 THEN A에 걸리게 된다. 

 

 

 

CASE WHEN B = 2 THEN B

       WHEN C = 3 THEN C

       ELSE A

 

그러나, 위의 경우에는 앞서 말한 A = 1의 조건 평가가 ELSE까지 내려가야한다. 그러므로 더 오래 걸릴 수 밖에 없다.

 

 

참고 링크:

http://databaser.net/moniwiki/wiki.php/CASEWHEN%EC%88%9C%EC%84%9C