비선형 자료구조는 데이터가 계층적이거나 복잡한 관계를 가지며, 선형 자료구조와 달리 데이터 요소가 서로 연결된 형태를 가집니다.
글 아래에 트리와 그래프에 대한 분석은 글쓴이가 공부용으로 생각한거라 틀린내용이 많을 수 있습니다.
1. 트리 (Tree)
트리는 계층적인 관계를 나타내는 자료구조로, 노드와 간선으로 구성됩니다. 각 노드는 데이터와 자식 노드에 대한 포인터를 가집니다.
이진 트리 (Binary Tree):
정의: 각 노드가 최대 두 개의 자식을 가질 수 있는 트리.
특징:
노드의 자식 노드는 왼쪽 또는 오른쪽으로 구분됩니다.
이진 탐색 트리 (Binary Search Tree, BST):
정의: 이진 트리의 한 종류로, 왼쪽 서브트리의 모든 노드는 부모 노드보다 작고,
오른쪽 서브트리의 모든 노드는 부모 노드보다 큽니다.
특징:
검색, 삽입, 삭제가 O(log n) 시간 복잡도로 가능 (균형 상태일 때).
균형 이진 트리 (Balanced Binary Trees):
정의: 트리의 높이가 균형을 이루도록 설계된 이진 트리.
AVL 트리: 각 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하인 이진 탐색 트리.
레드-블랙 트리: 각 노드가 색상을 가지고 높이 균형을 유지하는 이진 탐색 트리.
힙 (Heap):
정의: 완전 이진 트리로, 최대 힙과 최소 힙으로 나뉩니다.
최대 힙: 부모 노드가 자식 노드보다 크거나 같은 값.
최소 힙: 부모 노드가 자식 노드보다 작거나 같은 값.
특징: 우선순위 큐 구현에 자주 사용됨.
2. 그래프 (Graph)
그래프는 노드(정점)와 엣지(간선)로 구성된 자료구조로, 복잡한 비선형 관계를 표현하는 데 사용됩니다.
유향 그래프 (Directed Graph):
정의: 간선이 방향을 가지며, 한 정점에서 다른 정점으로의 관계를 나타냅니다.
무향 그래프 (Undirected Graph):
정의: 간선에 방향이 없으며, 정점 간의 관계가 대칭입니다.
가중치 그래프 (Weighted Graph):
정의: 각 간선에 가중치(비용)가 부여된 그래프.
장점
복잡한 관계 표현: 비선형 자료구조는 데이터 간의 복잡한 관계를 표현할 수 있습니다.
효율적인 검색: 이진 탐색 트리(BST)는 평균적으로 O(log n)의 시간 복잡도로 검색이 가능합니다.
유연성: 동적 크기 조정이 가능하여 데이터 추가 및 삭제가 용이합니다.
단점
구현 복잡성: 비선형 자료구조는 선형 자료구조에 비해 구현이 복잡할 수 있습니다.
메모리 사용: 포인터 오버헤드로 인해 메모리 사용이 비효율적일 수 있습니다.
접근 속도: 특정 노드에 접근하기 위해 포인터를 따라가야 하므로, 최악의 경우 O(n)의 시간 복잡도를 가질 수 있습니다.
글쓴이 분석
선형 자료구조와는 다르게 사용자가 직접 트리와 그래프를 만들어서 사용하는 자료구조
트리와 그래프를 보면 노드와 간선이라는 게 나왔는데
클래스를 만들어서 객체 안에 노드라는 클래스를 저장하는 방식
노드는 또 자식 노드를 가지고 있음.
트리는 보통 이진 트리로 사용되며
왼쪽 노드와 오른쪽 노드로 구별하며 탐색 하는 것 같음.