트리
트리(tree)는 노드 기반 자료 구조이다.
트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다.
아래의 이미지는 트리를 간단히 표현한 것이다.
위 이미지의 각 노드에는 다른 노드로 이어지는 링크가 있다. 메모리 주소를 표시하지 않고 트리를 아래 이미지와 같이 간결하게 표현할 수 있다.
트리에 쓰이는 고유 용어를 알아보자.
-
가장 상위 노드를 루트(root)라고 부른다.
-
위 이미지에서 "j"를 "m"과 "b"의 부모(parent)라고 한다. 또한 반대로 "m"과 "b"는 "j"의 자식이다.
-
패밀리 트리에는 노드에 자손(descendant)와 조상(ancestor)이 있을 수 있다. 하나의 노드의 자손은 그 노드에서 생겨난 모드 노드이고, 하나의 노드의 조상은 그 노드를 생겨나게 한 모든 노드이다.
-
트리에는 레벨(level)이 있다. 각 레벨은 트리에서 같은 줄(row)이다. 위 이미지의 트리는 세 레벨이다.
-
트리의 프로퍼티(property)는 균형 잡힌정도를 뜻한다. 모든 노드에서 하위 트리의 노드 개수가 같으면 그 트리는 균형(balanced) 트리이다.
-
예를 들어, 아래 중 첫 번째 이미지는 각 노드마다 두 하위 트리의 노드 수가 같으므로 균형 트리이다. 반면 두 번째 이미지는 불균형 트리(imbalanced)이다. 루트로부터 오른쪽 하위 트리가 왼쪽 하위 트리보다 노드가 많으므로 균형이 맞지 않다.
완전 트리
완전 트리(complete tree)는 빠진 노드 없이 완전히 채워진 트리다.
트리의 각 레벨을 왼쪽에서 오른쪽까지 읽었을 때 모든 자리마다 노드가 있어야한다.
하지만 바닥 줄에는 빈 자리가 있을 수 있는데, 이 때, 빈 자리의 오른쪽으로는 어떤 노드도 없어야 한다.
다음 세 개의 트리 중 어떤 트리가 완전하지 않은 트리일까? 한 번 생각해보자.
1.
2.
3.
완전하지 않은 트리는 2번 트리이다. 1번 트리는 빈 노드 없이 가득 채워져있다. 3번 트리는 바닥 레벨에 모든 노드가 있지는 않지만, 노드의 오른쪽으로 어떤 노드도 없으므로 완전하다.
2번 트리는 세 번째 레벨에 한 노드가 빠졌으므로 완전하지 않다.
트리 기반 자료구조
트리 기반 자료 구조는 종류가 다양하다.
이후에 여러 트리 기반 자료 구조를 학습할 때마다 포스팅하고, 본 포스트에 해당 포스트 링크를 작성해둘 예정이다.
2023-10-08
이진 탐색 트리
2023-10-20
이진 힙
2023-12-07
트라이
