자료구조2 트리 이번 포스팅에서는 트리에 대해서 알아보려고 합니다. 트리는 비선형 자료구조로 자료간의 포함관계, 상하위 관계와 같은 계층 구조를 표현할 수 있는 자료구조 입니다. 아래 그림은 각 자료간 포함관계를 표현합니다. 트리 관련 용어트리는 노드와 간선들로 구성되어 있고, 각 노드는 간선을 사이에 두고 상위, 하위 관계를 가지게 됩니다.여기서 상위 노드는 부모, 하위 노드는 자식이라고 부릅니다.여기서 특징은 무조건 부모는 하나여야 합니다. 그렇기 때문에 트리는 가장 최상위 부모를 루트(root) 라는 용어로 부릅니다. 그리고 트리의 최하위 노드는 리프(leaf)라고 부릅니다. 트리는 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 해당 노드의 깊이라고 합니다.리프 노드의 깊이를 트리의 높이(height.. 2024. 7. 10. Union Find 이번 포스팅에서는 Union Find에 대해서 알아보려고 합니다. Union Find란?Union Find란 상호 배타적 집합을 표현하기 위해 사용되는 자료구조 입니다.상호 배타적 집합이라는 표현에 대해서 조금 더 자세하게 설명해보겠습니다.상호 배타라는 단어는 "서로 겹치지 않는다" 라는 의미이고, 집합은 구별되는 요소들의 모임입니다. 즉 부분집합들이 공통 요소를 가지지 않음을 표현하는 단어가 상호 배타적 집합입니다. 머릿속으로 위 문장을 그려보시면 아래와 같은 그림을 그리실 수 있습니다.각각의 요소들은 서로 다른 집합에 포함되어 있고, 각 집합들은 교집합을 가지지 않습니다.Union Find에서는 각 요소들을 0 ~ n-1로 표현합니다. Union Find의 3가지 연산은 다음과 같습니다.초기화 : .. 2024. 7. 6. 이전 1 다음
