본문 바로가기

Python/그래프와 트리 (Graph and Tree)

 (4)
14. 트리 순회 (Tree Traversal): 파이썬 자료구조와 알고리즘 순회 (Traversal) 란 트리 또는 그래프 같은 연결된 구조에서 객체 (노드) 를 방문하는 데 사용되는 알고리즘이다. 순회 문제는 모든 노드를 방문하는 방법을 찾거나 특정 노드만 방문하는 방법을 찾는 것일 수도 있다. 깊이 우선 탐색 깊이 우선 탐색 (depth-first search, DFS) 란 그래프 또는 트리에서 깊이를 우선하여 탐색하는 알고리즘이다. 그래프의 경우는 방문한 노드를 표시해야 하는데. 그렇게 하지 않는다면 무한 반복에 빠질 수 있기 때문이다. 시간 복잡도는 O(V+E) 이다. V는 도달할 수 있는 노드 수 (vertext), E는 도달한 노드에서 나가는 간선 수 (edge) 다. 깊이 우선 탐색은 후입선출 (LIFO) 구조의 스택을 사용하여 구현한다. 깊이 우선 탐색의 세 가지..
13-2. 이진 탐색 트리와 자가 균형 이진 탐색 트리 (Binary Search Tree and Self-balancing Binary Tree): 파이썬 자료구조와 알고리즘 이진 탐색 트리 이진 탐색 트리 (binary search tree) 는 노드를 정렬된 순서로 유지하는 자료구조이다. 이진 트리로 이루어지며, 각 노드에는 값과 두 자식 노드에 대한 포인터가 있다. 또한 선택적으로, 부모 노드의 포인터를 저장할 수도 있다. 각 노드의 값은 왼쪽 하위 트리의 모든 항목보다 크고, 오른쪽 하위 트리의 모든 항목보다 작다. 즉, 노드의 왼쪽 하위 트리에는 노드의 값보다 작은 값의 노드만 존재한다. 노드의 오른쪽 하위 트리에는 노드의 값보다 큰 값의 노드만 존재한다. 왼쪽과 오른쪽 하위 트리 모두 이진 탐색 트리이다. 중복 노드가 없다. 이진 탐색 트리가 균형 트리인 경우, 노드 검색/삽입/삭제에 대한 시간 복잡도는 O(log n) 이다. 이진 탐색 트리 구현 이진 탐색 트리는..
13-1. 이진 트리 용어와 구현 (Binary Tree Terms and Implementation): 파이썬 자료구조와 알고리즘 이진 트리 (binary tree) 는 노드가 최대 두 개의 자식 노드 (왼쪽, left 와 오른쪽, right) 를 갖는 자료구조이다. 자식 노드는 부모 노드에 대한 참조를 포함할 수 있다. 트리의 루트 노드 (root node) 는 모든 노드의 조상이다. 이진 트리에서 노드의 차수는 최대 2다. 트리에 m개의 내부 노드가 있으며, 각 내부 노드에 두 개의 자식 노드가 있다고 가정한다. 또한 트리에 n개의 말단 노드가 있다면, 트리의 차수는 n-1 이다. 즉, 2m = n + m -1 이며, 따라서 m = n - 1 이다. 여기서 m은 내부 노드의 개수, n은 말단 노드의 개수이다. 용어 그래프와 마찬가지로, 트리도 기본적인 용어를 먼저 살펴보자. 노드 차수 (degree): 자식 수 경로 (path)..
12. 그래프 기초 (Graph Basics): 파이썬 자료구조와 알고리즘 그래프란 여러 노드 (node, 또는 정점, vertex) 들이 간선 (edge, 또는 아크, arc) 으로 연결된 추상 네트워크를 뜻한다. 가장 기본적인 용어들부터 알아보도록 하자. 용어 그래프 그래프는 아까 말했듯 여러 노드와 간선으로 연결된 추상 네트워크를 뜻한다. 즉, 그래프는 노드와 간선의 집합으로 정의되며 이를 수식으로 쓰면 다음과 같다. G는 그래프 (graph), V는 노드 (vertex) 의 집합, 즉 아래와 같은 그래프에선 {a,b,c,d} 이고, E는 간선 (edge) 의 집합, 즉 노드 쌍들의 집합이며, 아래와 같은 그래프에선 {{a,b}, {b,c}, {c,d}, {d,a}}이다. 그래프의 방향 그래프에는 방향이 있는 유향 (directed) 그래프와 방향이 없는 무향 (undir..

티스토리툴바