트리(Tree) 🌲
-
자주 쓰는 자료구조인 리스트, 큐 등과 다르게, 트리는 계층적인 형태를 띈다.
-
즉 입력 받는 데이터 간의 상하관계가 존재하는데, 위에 있는 노드를 부모 노드, 그 아래의 최대 2개의 노드를 자식 노드라고 명칭한다.
(출처: https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html)
- 루트 노드 (Root Node) - 이름 그대로 트리의 뿌리, 즉 트리의 시작점에 위치한 노드를 말한다.
- 부모 노드 (Parent Node) - 자식 노드의 위에 있는 노드로, 최대 2개의 자식 노드를 거느린다.
- 자식 노드 (Child Node) - 부모 노드의 아래에 위치하는 노드를 말한다. 두 자식 노드는 **형제(자매)관계 **
Siblings라 부를 수 있다.
- 리프 노드 (Leaf Node) - 나뭇잎은 더 이상 다른 나무로 이어지지 않는 것처럼, 자식 노드가 존재하지 않는 노드를 말한다.
- 부분 트리 (Sub-tree) - 전체 트리의 내부에 위치한 작은 하위 트리를 일컫는다.
- 레벨 (깊이) - 특정 노드가 루트 노드로부터 떨어진 정도를 말한다. - 레벨은 0부터 시작한다.
- 높이 - 레벨과 비슷한 개념이지만, 특정 노드를 대상으로 말한다기보다는 전체 트리를 기준으로 말할 때 사용한다. - Ex) 위 트리는 3의 높이를 갖고 있다.
이진 트리 🌳
-
이진 트리란, 각 노드가 최대 2개의 자식노드를 거느릴 수 있는 트리이다.
-
이진 트리는 쓰임새가 다양하고 용이해, 트리를 사용할 때는 일반적으로 이진 트리를 이용한다.
이러한 이진 트리에는 가진 모양에 따라 3가지의 종류로 나뉜다.
1. 정 이진 트리
(출처: https://www.wikiwand.com/en/Binary_tree)
- 정 이진 트리는 모든 노드가
0개 혹은2개의 자식 노드를 갖고 있는 것을 말한다.
2. 포화 이진 트리
- 포화 이진 트리는 모든 레벨의 노드들이 빠짐없이 차 있는 형태를 말한다.
3. 완전 이진 트리
(출처: https://www.wikiwand.com/en/Binary_tree)
-
완전 이진 트리는 마지막 레벨을 제외한 모든 레벨들에서는 노드들이 꽉 차 있으며, 마지막 레벨의 노드는 왼쪽부터 차례대로 채워진 형태를 말한다.
-
가장 많이 사용되는 방식으로, 우선 순위 큐 또는 힙 큐에서도 이와 같은 형태를 유지해야만 한다.
완전 이진 트리는 다음과 같은 특징들이 존재한다.
① 전체 노드의 개수를 통해서 트리의 높이를 구할 수 있다.
완전 이진 트리는 각 층별로 최대 2^레벨 만큼의 노드를 갖고 있다.
- 레벨 0:
2^0 = 1개 - 레벨 3:
2^3 = 8개
그러므로 높이가 3인 완전 이진 트리는 최대 1 + 2 + 4 + 8 = 15개의 노드를 가질 수 있다.
이와 비슷한 방식으로 최소 노드 또한 구할 수 있다. 최소 노드를 가지기 위해서는, 마지막 레벨에서 노드를 1개만 가져야 한다.
- 레벨 1:
2^0 + 1 = 2개 - 레벨 2:
2^0 + 2^1 + 1 = 4개 - 레벨 3:
2^0+ 2^1 + 2^2 + 1 = 8개
이를 통해서 높이가 3인 완전 이진 트리의 노드 개수 범위는 2^3인 8부터 2^4 - 1 15까지인 것을 알 수 있다.
이는 전체 노드 개수에 log2()를 씌운 후에 그보다 작은 정수 중 가장 큰 값에도 해당한다.
👉 python에서는 int(math.log2(15)) 이와 같이 3을 구할 수 있다.
👉 높이가 4인 완전 이진 트리의 전체 노드 개수 범위는?: 2^4인 16개 ~ 2^5 - 1인 31개
👉 어떤 완전 이진 트리의 전체 노드 개수가 64개라면, 이 트리의 높이는 몇인가?: log2(64) = 6이므로 높이는 6
② 리프 노드의 개수를 통해서 트리의 높이를 구할 수 있다.
리프 노드의 개수를 구한 후에, log2()를 씌운 후 올림하면 높이를 구할 수 있다.
높이가 2인 경우에 모든 노드가 꽉 차있다면, 리프 노드는 4개가 존재할 것이다.
여기서 가장 왼쪽의 노드에서 자식 노드가 2개 생긴다고 가정하면, 리프 노드는 레벨2에서 3개, 레벨3에서 2개가 존재해 총 5개가 된다.
math.ceil(math.log2(5)) 은 3이므로 리프 노드를 통해 높이가 3인 것을 알 수 있다.
하지만 이 방법은 트리가 정 이진 트리의 형태인 경우에만 가능하다.
👉 만약 위와 같은 트리에서 자식 노드가 1개만 생성된다면, 리프 노드는 그대로 4개가 존재하게 되므로 높이에 변화가 생기지 않기 때문이다.
③ 부모 노드의 인덱스를 통해서 자식 노드의 인덱스를 구할 수 있다.
왼쪽 자식 노드 인덱스 = 부모 노드의 인덱스 X 2
오른쪽 자식 노드 인덱스 = 부모 노드의 인덱스 X 2 + 1
위 트리를 리스트로 나타내면, [None,10,5,15,1,7,12,20]이 된다.
index 2에 해당하는5는1과7을 자식 노드로 갖는데, 이는index 4와index 5에 해당한다.
👉 위의 공식이 성립함을 알 수 있다.
④ 자식 노드의 인덱스를 통해서 부모 노드의 인덱스를 구할 수 있다.
부모 노드 인덱스 = 자식 노드 인덱스 // 2
index 4에 위치한1과index 5에 위치한7의 부모 노드인,5는index 2에 위치해있다.
👉 위의 공식이 성립함을 알 수 있다.