네, 반갑습니다. 오늘 이 영상을 끝까지 보신 후엔 트리 구조의 기본적인 개념과 용어를 알게 되고 이진 트리의

다양한 형태를 경험하게 됩니다. 자, 그럼 오늘도 고고싱! 트리 자료 구조란 무엇인가? 지금 보시는 이 그림이 트리

구조인데요. 이 트리 구조라고 하면 노드들의 집합을 의미합니다. 그러니까 이 하나하나가 다 노드인 거죠. 그러면은 이

각 노드들은 값과 또 다른 노드들을 가르키는 레퍼런스들로 구성이 되어 있습니다. 그래서 실제로 구현 관점

에서 엄밀히 따지면, 뿐만 아니라 다른 노드를 가르키는 레퍼런스를 이렇게 포함해서 이 하나를 노드라고 이해를

하시면 됩니다. 그러니까 여기서도 이게 노드인 거고 여기서도 이게 노드인 거죠. 노드는 구현 관점에서 엄밀히

따지면 가뿐한 게 아니라 레퍼런스가 이제도 포함한다는 것, 그렇게 기억을 해 주시면 좋을 것 같아요. 자, 그러면

트리 관련된 주요 용어를 살펴보겠습니다. 지금 용어를 좀 살펴볼게 많은데요. 그렇게 어렵지

않으니까 잘 따라와 주세요. 먼저 간선, 영어로는 엣지라는 건데, 이 의미는 노드와 노드를 연결하는 선입니다. 그러니까

이렇게 하얀색 화살표로 표시된 이거 있잖아요? 이게 다 간선이에요. 이런 것들이 다 간선인 건데, 구현

관점에서는 이 간선이 레퍼런스를 의미합니다. 그러니까 아까 앞에서도 잠깐 설명을 드린 건데, 예를 들어서 이

노드를 객체지향 형태로 표현을 한다 치면, 이 노드는 내부적으로 일단은 값을 저장을 하고요. 그 값만 아니라 다른

노드를 가르키는 레퍼런스들을 같이 저장을 한다. 그리고 이 레퍼런스들이 트리를 나타내는 그 구조에서는 방금

설명드린 간선에 해당한다. 그렇게 이해를 하시면 될 것 같습니다. 그리고 이 간선 혹은 엣지라는 거는 링크라고 불리기도 하고요

브랜치라고요. 트리의 최 상단에 있는 노드 그림에서는 2번 노드, 이 노드가 루트 노드이다. 트리의 시작점이 됩니다. 자

다음은 자녀 노드에 대한 개념인데요. 트리에서 모든 노드는 0개 이상의 자녀 노드를 가진다고 보시면

되겠습니다. 그러니까 여기서 예를 들어서 이 9번 노드의 자녀 노드는 11번이고요. 또 11번 노드의 자녀

노드는 8번, 1번, 4번인 거죠. 5번 노드의 자녀 노드는 6번, 7번이고 6번 노드의 자녀 노드는 3번인

겁니다 당연히 2번 노드의 자녀 노드는 5번 9번이 있죠 그래서 모든 노드는 0개 이상의 자녀 노드를

가진다 그렇게 이해를 하시면 될 거 같고요 반대로 그러면 부모 노드라고 있습니다 부모 노드는 자녀 노드를

가지는 노드를 말해요 여기서는 2번 5번 9번 6번 11번이 부모 노드에 해당하겠죠 얘네들은 다 자녀 노드를

가지니까 그리고 형제 노드는 뭐냐 같은 부모를 가지는 노드들입니다 그림에서 보면은 8번 1번 4번

노드요 노드가 모두 11번이랑 같은 부모 노드를 가지잖아요 그래서 얘네들은 다 형제 노드 영어로는

시블링이고요 마찬가지로 6번 7번 노드도 5번 노드를 부모 노드로 가지기 때문에 얘네들도 형제 노드 또

마찬가지로 5번과 9번 노드도 2번을 부모 노드로 가지기 때문에 얘네들도 형제 노드가 되는 거죠. 다음은 조상

노드입니다. 요거는 부모 노드를 따라서 루트 노드까지 올라가면서 만나는 모든 노드를 조상 노드라고 해요. 가령 예를

들어서 8의 조상 노드, 그러니까 8번 노드는 여기 있는데 이 8번 노드의 조상 노드는 뭐냐면은 11번, 9번,

2번, 지금 2번이 루트 노드니까 9번, 2번 노드가 모두 조상 노드라고 볼 수 있겠습니다. 자, 반대로

다음은 자손 노드인데, 자손 노드는 자녀 노드를 따라서 내려가면서 만날 수 있는 모든 노드를 자손 노드라고

합니다. 그래서 9번 노드, 여기죠. 9번 노드의 자손 노드는 이렇게 이제 자녀를 따라가는 거라서 11번, 8번

1번 4번이 모두 자손 노드가 되는 겁니다. 어렵지 않죠? 뭐 다른 거 하나 더 해 볼까요? 이 5번 노드에 자손

노드는 그러면 뭐가 될까요? 얘는 6번 7번 3번이 자손 노드가 되겠죠. 내부 노드는 뭐냐? 인터널 노드라고 하는데요,

자녀 노드를 가지는 모든 노드를 내부 노드라고 합니다. 다른 말로는 브랜치 노드 혹은 인노 노드라고 하는데요. 이

예에서는 보면은 모든 자료 노드를 가지는 노드, 그러니까 부모 노드인 거죠. 이 부모 노드는 2번 5번 9번,

6번 11번이 거잖아요. 이 다섯 개의 노드가 내부 노드에 해당한다. 이렇게 이해를 하시면 되고요. 반면에 외부

노드, 익스터널 노드라고 하는데요. 자녀 노드가 없는 노드를 의미합니다. 리프 노드 혹은 아우터 노드 혹은 터미널

노드, 우리말로는 단말 노드라고 불리기도 하는데요. 이 그림에서는 3번, 7번, 8번, 1번, 4번 노드가 자녀가

없는 노드들이에요. 이런 노드를 외부 노드라고 부르는 거죠. 저는 이제 리프 노드라고 제일 익숙한데요. 어쨌든

다양하게 이렇게 불릴 수 있다라는 것 이해를 해 주시면 될 거 같고요. 자, 경로, 영어로는 패스라는 개념이 있는데요. 이 개념은 뭐냐면 하나의

노드와 다른 노드 사이에서 그 노드들의 시퀀스를 의미를 합니다. 그러니까 예를 들어서 2번 노드에서

7번 노드로 가기 위해서 이 경로가 여기 5번 노드를 거쳐서 이렇게 갈 수 있는 거잖아요. 그러면 이때 이

경로는 어떻게 표현하냐면 출발 노드로부터 이 도착 노드까지 다 포함해서 2번, 5번, 7번 이렇게 적어

주면 되는 겁니다. 다른 거 한번 해 볼까요? 만약에 2번 노드에서 4번 노드까지의 경로는 무엇이냐 이렇게

물어보면 얘는 2번에서 4번 노드까지 가기 위해서는 9번을 거치고 11번을 거쳐야 4번 노드에 도달하게

되는 거잖아요. 그러면 2번과 4번 노드 사이의 경로는 2, 9, 11, 4 이렇게 되는 거죠. 그러면 이때 이

경로의 길이, 랭스 오브 패스는 뭐가 되냐? 경로에 있는 노드들의 수를 의미를 합니다. 그래서 2번 노드에서

7번 노드로 가는 경로는 총 세 개의 노드가 연관이 되어 있기 때문에 이때 이 경로 길이는 3이 되는 거고요.

만약에 2번 노드에서 3번 노드까지 가기 위한 경로는 총 네 개의 노드가 이렇게 연관이 되어 있기 때문에

그래서 이 경로의 길이는 4가 되는 겁니다. 어렵지 않죠? 자 이번에는 높이라는 개념이 있습니다. 노드의

높이는 뭘 의미를 하냐면 노드에서 리프 노드 - 단어가 하나 빠졌는데 - 자기 자손의 리프 노드까지의 가장 긴 경로의

간선, 그러니까 엣지의 수를 의미를 합니다. 그러면 예를 들어서 이 5번 노드의 높이는 뭐냐면 얘는 리프

노드가 지금 총 두 개가 있잖아요. 이 5번 노드에서 출발할 수 있는 리프 노드가 총 두 개가 있는데 이 리프

노드 중에서 3번 노드로 가는 경로가 더 길단 말이죠. 그러면은 이 3번 노드로 가기 위한 경로에서 엣지의

수는 한 개, 두 개인 거니까 이때 그럼 5번 노드의 높이는 2가 되는 겁니다. 하나만 더 예를 들어서 해

볼까요 만약에 9번 노드의 높이는 어떻게 될까요? 그러면 9번 노드에서 갈 수 있는 리프 노드는 8번, 1번, 

1번, 4번인데 얘는 모두 두 개의 엣지를 이렇게 거쳐야 갈 수 있는 거잖아요. 그래서 이 9번 노드의 높이도 

2가 되는 겁니다. 그러면 리프 노드의 높이는 뭐가 되냐? 리프 노드의 높이는 0이라고 표현을 합니다. 근데 좀 

찾아보시면 요것도 약간씩 개념이 다를 때가 있어요. 그래서 높이 계산을 간선, 그러니까 엣지로 하는 게 아니라 노드로 

하는 경우도 있거든요. 그래서 관련된 문서를 읽을 때 이 높이 계산하는 게 엣지 수인 건지 아니면 노드 수인 건지 잘 파악을 하시고 보는 게 

좋습니다. 만약에 노드 수 했다면 은 엣지 수보다 하나씩 많겠죠. 그래서 노드로 카운트할 때는 + 1이 추가로 

된다 그렇게 이해를 하시면 될 거 같아요 자 그리고 트리의 높이입니다 바로 앞에서는 노드의 높이였다

이제 전체 트리의 높이는 어떻게 계산하나 트리의 높이는 결국 루트 노드의 높이거나 지금 여기서 루트

노드는 2번 노드니 결국 트리의 높이는 2번 노드의 높이인 건데 그러면 2번 노드에서 가장 멀리

떨어져 있는 리프 노드까지 가기 위한 엣지의 개수가 몇 개냐 했을 때 지금 가장 멀리 떨어져 있는 리프 노드는

3번 8번 1번 4번 얘네들까지 가기 위해서는 총 세 개의 엣지를 거쳐가야 되기 때문에 그러면 이때 루트 노드의 높이는

3이라고 할 수 있고 결국 트리의 높이는 3이 되는 겁니다 이해가 되시죠 이번에는 높이와 비슷하지만 또

다른 개념인 깊이, 영어로는 depth인데요, 이 깊이를 살펴볼게요. 먼저 노드의 깊이를 살펴보겠습니다. 임의의 노드에서 깊이는

뭘 의미하면서 해당 노드까지의 경로, 그 경로의 엣지 수를 의미합니다. 그래서 예를 들어서 11번 노드의

깊이는 뭐가 되냐면 루트 노드에서 이 11번 노드까지의 경로, 이 경로에 있는 엣지 수거요청, 엣지 수는 여기서는

하나, 둘, 두 개기 때문에 11번 노드의 깊이는 2가 되는 겁니다. 그러면 다른 예를 하나 들어 볼게요. 3번 노드의 깊이는 어떻게 되냐

그러면 루트 노드에서 출발을 해서 이 3번 노드까지 가기 위해서 총 세 번의 엣지를 거쳐야 되거든요. 그러면은

이때 이 3번 노드의 깊이는 3이 되는 거죠. 자, 그러면 루트 노드의 깊이는 뭐가 되냐? 루트 노드의 깊이는

0이라고 합니다 그러면 이제는 트리의 깊이 트리의 뎁스를 살펴볼게요 트리의 깊이는 뭘 의미하느냐 트리에 있는

노드들의 깊이 중에 가장 긴 깊이를 트리의 깊이라고 합니다 그러면 이 모든 노드들 중에서 루트 노드로부터 가장

멀리 떨어져 있는 그 리프 노드의 깊이가 곧 트리의 깊이가 되겠죠 그러면 이 트리에서 루트 노드로부터

가장 멀리 떨어져 있는 리프 노드를 찾아보면 3번 8번 1번 4번이 때문에 그럼 얘네들의 깊이는 뭐가

되냐 얘네들 모두는 루트 노드로부터 총 세 번의 엣지를 거쳐야만 도달을 할 수 있거든요 이렇게요 그래서

결국 이 트리의 깊이는 3이 되는 겁니다 그리고 이제 우리가 높이와 깊이의 개념을 알았기 때문에 트리의

높이는 곧 트리의 깊이가 됩니다. 자, 노드의 차수는 뭐냐? 영어로는 차수가 디그리(degree)입니다. 총 자녀가 세 개기 때문에 3이고요.

3번 노드의 차수는 자녀가 없기 때문에 0입니다. 그러면 트리의 차수는 뭐냐? 트리에 있는 모든 노드들의 차수

중에 가장 큰 차수를 트리의 차수라고 합니다. 그러면 지금 여기 보시는 이 트리에서 가장 자녀가 많은 노드는 11번 노드죠. 얘는 자녀를 세 개를

가지고 있기 때문에 11번 노드가 이 트리에서는 가장 많은 자녀를 가지고 있고, 그러면 이 11번 노드의 차수는

3이기 때문에 이 3이 곧 이 트리의 차수가 되는 겁니다. 자, 이번에는 디스턴스, 두 노드 사이의 거리를 의미하는 건데요. 이 디스턴스는 두 노드가

이어지기 위한 최소한의 엣지의 수를 의미합니다. 그래서 예를 들어서 9번 노드와 8번 노드는 최소 두 개의 엣지를 거쳐야만 갈 수 있기

때문에 얘의 디스턴스 n 2라고 하고요 3번 노드와 8번 노드의 디스턴스 n 얘는 이렇게 가야 도달할

수 있는 거리잖아요 그러면 이때 총 몇 개의 엣지를 거치면 총 여섯 개의 엣지를 거치기 때문에 3번 노드와

8번 노드의 디스턴스 n 6이라고 하는 겁니다 이해가 되시죠 이번에는 노드의 레벨을 살펴보겠습니다 노드의

레벨은 노드와 루트 노드 사이의 경로에서 엣지의 수를 의미합니다 얘는 그래서 쉽게 표현하면 이렇게

되는 거죠 왜 그러냐면 이 노드는 루트 노드로부터 한 번의 엣지로 도달할 수 있고 11번 노드는 루트 노드로부터

두 번의 엣지로 도달할 수 있고 3번 노드는 루트 노드로부터 세 번의 엣지로 도달을 할 수 있기 때문에

그래서 레벨이 이런 식으로 0, 1, 2, 3 이렇게 늘어난다 그래서 좀 더 예쁘게 표현하면 이런 식으로 레벨이

형성이 되는 거죠 이해가 되시죠? 근데 이것도 마찬가지로 어떤 문서에서는 루트 노드의 레벨을 0으로부터

시작하는 것이 아니라 1로부터 시작하기도 해요 근데 우리는 0으로부터라고 하겠습니다 그러면 스, 이거는 뭐냐? 얘는 임의의 레벨에서

노드의 수를 의미합니다 가령 예를 들어서 레벨 2, 여기를 말하는 거죠 레벨 2에서 스는 총 세 개의 노드가

있기 때문에 스가 3이 되는 거고요 만약에 레벨 3에서 스를 구하라고 하면 여기는 노드가 총 네 개기 때문에

네 이때는 레벨 3의 스는 4가 되는 겁니다 이번에는 노드의 크기입니다 이 노드의 크기는 노드 자신을 포함한

자선 노드의 수를 의미해요. 그래서 예를 들어서 9번 노드의 크기는 이 노드의 9번 노드의 크기는 자기

자신을 포함해서 자손 노드가 네 개가 있기 때문에 총 5가 되는 거고요. 5번 노드의 크기는 자기 자신을

포함해서 자손 노드가 세 개가 있기 때문에 4가 되는 겁니다. 그러면 트리의 크기는 뭐냐? 트리의 크기는

결국 트리의 모든 노드의 수입니다. 그래서 여기는 총 10개의 노드가 있기 때문에 이 트리의 크기는 10이 되는

트리(tree) 구조의 기본 개념과 용어들을 설명합니다~ 이진 트리(binary tree)의 형태에 따른 다양한 종류도 설명하니까요 기본 개념 잡고 싶으시면 도움되실 거에요 :)

8년차 백엔드 개발자가 배워서 남주려고 만든 채널이에요

알기 쉽게 설명합니다

함께 성장했으면 좋겠어요 :)


#컴공맛집 #백엔드전문채널
