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