Tree(Graph theory)
연결리스트 부터 이진 트리까지
이 포스트는 트리 구조에 대해서 간단히 정리한 것으로 연결리스트와 노드의 개념에 대해서 알고 있다고 가정하고 작성되었어요. 자세한 저장, 활용에 대해서는 다루지 않아요.
What is the tree?
연결리스트 구조는 데이터의 삽입, 삭제시 데이터를 이동시키지 않는 장점이 있어요. 하지만 검색을 하려면 노드의 첫 시작부터 검색을 해야하는 단점이 있기도 하죠. 우리는 이런 문제를 해결하려고 트리라는 구조를 사용하기 시작했어요. 트리는 쉽게 말해서 "1개 이상의 데이터를 그래프로 표현한 집합" 이라고 말할 수 있어요. 그러니까 데이터를 검색할 때 특정 지점을 정해놓고 그 지점부터 일정한 규칙에 따라 그래프를 만들어 나가는 방식을 사용한거에요. 이런 방식을 사용하면 데이터의 순서를 유지하면서도 빠른 검색과 삽입, 삭제가 가능한 자료구조를 만들 수 있어 자주 사용되고 있어요.
또 트리는 배열이나 연결리스트로 다루는게 일반적이에요.
Tree
트리를 만드는데에는 몇 가지의 중요한 용어들이 있어요. 그 중 첫번째는 루트(root) 노드에요. 트리는 1개 이상의 노드를 가지고 있는 집합 구조이기 때문에 반드시 하나 이상의 노드가 필요해요. 그리고 이런 노드 중 상위 노드를 루트라고 부르기로 했어요.
두번째로는 부모-자식 노드에요. 우리는 이런 루트 노드를 부모 노드라고 부를 수도 있고, 그 부모 노드는 각각 자식 노드를 가질 수 있어요. 또, 이런 부모-자식간의 노드를 분리해서 서브트리로 만들 수 있어요.
마지막으로는 레벨이에요. 루트 노드로부터 내려오는 서브트리들을 단계별로 레벨로 묶을 수 있는데 예를 들면 아래 그림과 같아요.
Binary Tree
원래 트리는 여러 자식을 가지고 있을 수 있지만, 저는 보통 이진 트리를 사용하는 편이에요. 이진 트리란 자식 노드의 수가 2개 이하인 것을 말해요.
그 중에서도 이진트리에는 스큐(skewed) 트리, 포화(full) 트리, 완전(complete) 트리 등이 있어요.
Reference
Last updated
