[문제풀이] Hacker Rank - Binary Tree Nodes

출처

Binary Tree Nodes | HackerRank

 

문제

You are given a table, BST, containing two columns: N and P, where N represents the value of a node in Binary Tree, and P is the parent of N.

Write a query to find the node type of Binary Tree ordered by the value of the node. Output one of the following for each node:

• Root: If node is root node.
• Leaf: If node is leaf node.
• Inner: If node is neither root nor leaf node.

문제에 대한 해석

P는 N의 부모

N의 부모가 없을 경우 Root

N의 자녀가 없는 경우 Leaf

 

풀이(MYSQL)

SELECT
n,
    CASE WHEN p is null then 'Root'
    WHEN n in(SELECT p  FROM BST b  ) then 'Inner'
    ELSE 'Leaf' END 
FROM BST a
ORDER BY n

 

풀이(ORACLE)

SELECT N
     , CASE WHEN LEVEL = 1 THEN 'Root' -- 최상위 레벨일 경우 root
            WHEN CONNECT_BY_ISLEAF = 1 THEN 'Leaf' -- 최하위 레벨일 경우 leaf
            ELSE 'Inner' END NODE
  FROM BST
 START WITH P IS NULL -- 1.P의 값이 없는 경우 최상위로 지정
 CONNECT BY PRIOR N = P -- 2.n의 부모는 p
 ORDER BY 1
;

작동순서

💡SQL 실행 순서는 From -> Where -> Group by -> Having -> Select -> Order by ->결과반환

1. FROM 절: BST 테이블에서
2. SELECT 절: n과
   1. p가 null값인 경우(부모가 없는 경우)  'Root' 출력
   2. n이 p에도 있는 경우(누군가의 부모 인 경우) 'Inner'출력
   3. 부모가 있지만, 누군가의 부모는 아닌 경우 'Leaf'출력
3. ORDER BY 절: n의 오름차순으로 조회 

 

배운점

계층형 쿼리는 오라클에서만 지원한다

계층형 쿼리 구문

• SELECT ... FROM ... START WITH ... CONNECT BY ...
• START WITH 절: 계층 구조의 시작 위치지정
• CONNECT BY 절: 상위-하위 관계정의
• ORDER SIBLINGS BY 절: 동일 상위 계층의 하위 데이터렬

계층형 쿼리 함수

• LEVEL 함수: 현재 레벨확인 > 1은 최상위 Root로 현재 테이블에는 4레벨까지 존재
•  

• CONNECT_BY_ROOT 함수: 현재 행의 최상위 부모 값반환
• CONNECT_BY_ISLEAF 함수: 현재 행이 리프 노드인지 확인
• SYS_CONNECT_BY_PATH 함수: 현재 행까지의 경로를 문자열로 반환

 

-- 오답
SELECT
n,
    CASE WHEN p is null then 'Root'
    WHEN n not in(SELECT p  FROM BST b  ) then 'Leaf'
    ELSE 'Inner' END 
FROM BST a
ORDER BY n

오류 : where n not in(SELECT p  FROM BST b  ) then ' Leaf ' -> 결과 X

의미 : 부모 컬럼( SELECT p  FROM BST )에 값이 없는 경우 

즉, 누군가의 부모가 아닌 경우 (= Leaf )을 출력하고 싶으나 결과가 나오지 않음

왜 ?

 < SELECT p  FROM BST의 출력값>

not in()에null 값이 있을 경우 논리구조

SELECT * FROM users WHERE name NOT IN ('Alice', 'Charlie', NULL);

 

의도한 내용 : name 컬럼에서 'Alice', 'Charlie', NULL이 아닌 경우 필터링 하여 조회하라

 

위의 쿼리는 다음과 같이 해석이 된다

name != 'Alice' AND name != 'Charlie' AND name != NULL

'Alice'가 아니고 'Charlie'가 아니고 NULL가 아닌 경우

 

여기서 각 조건을 살펴보면:

1. name != 'Alice' - TRUE 또는 FALSE
2. name != 'Charlie' - TRUE 또는 FALSE
3. name != NULL - UNKNOWN

SQL의 3값 논리에 따르면 AND 연산의 결과는 다음과 같습니다:

• TRUE AND UNKNOWN = UNKNOWN
• FALSE AND UNKNOWN = FALSE
• UNKNOWN AND UNKNOWN = UNKNOWN

따라서, name != NULL 조건이 항상 UNKNOWN이 되므로, 전체 AND 조건도 UNKNOWN이 된다.

SQL에서는 WHERE 절의 조건이 TRUE일 때만 해당 행을 반환하기 때문에,

UNKNOWN이 포함된 조건은 FALSE로 간주되어 행이 반환되지 않음!

 그러나 False 의 경우Fasle로 반환되기는 함ㅎㅎ

 

요약

• NULL과의 모든 비교는 UNKNOWN으로 평가
• NOT IN 절에 NULL이 포함되면 전체 조건이 UNKNOWN이 되어 FALSE로 간주
• 따라서, NULL 값을 포함하지 않도록 쿼리 작성

이러한 특성 때문에 NOT IN을 사용할 때는 NULL 값을 피해야 하며,

필요시 IS NOT NULL 조건을 추가하거나 NOT EXISTS를 사용하는 것

SELECT
n,
    CASE WHEN p is null then 'Root'
    WHEN NOT EXISTS (SELECT p  FROM BST b  WHERE b.p = a.n) then 'Leaf'
    ELSE 'Inner' END 
FROM BST a
ORDER BY n

 

• p IS NULL일 때 Root 반환
• NOT EXISTS (SELECT 1 FROM BST b WHERE b.p = a.n)을 사용하여 a.n이 다른 어떤 노드의 부모 노드가 아닌 경우를 찾습니다. 이는 해당 노드가 Leaf임을 의미합니다.
• > WHERE b.p = a.n : p의 컬럼과 n의 컬럼에서 같은게 있을 경우의 데이터의 결과가 not exists존재하지 않을때(즉,  n에대한 데이터가 p에 존재하지 않을때) TRUE를 반환하여 leaf를 반환
• 그 외의 경우에는 Inner 반환