자료구조 6일차 Start!
▼오늘 학습한 내용
트리 (Tree)
트리 (Tree)
: 트리는 계층적 구조를 표현하는 비선형 자료구조로 노드들과 노드들을 연결하는 간선들로 구성되어 있다.
트리의 주요 특징
- 하나의 루트 노드를 가짐
- 각 노드는 0개 이상의 자식 노드를 가질 수 있음
- 사이클이 존재하지 않음
트리의 종류
- 일반 트리 (General Tree): 노드가 임의의 수의 자식을 가질 수 있는 트리
- 이진 트리 (Binary Tree): 각 노드가 최대 2개의 자식을 가질 수 있는 트리
- 완전 이진 트리 (Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 이진 트리
- 포화 이진 트리 (Perfect Binary Tree): 모든 내부 노드가 2개의 자식을 가지며, 모든 리프 노드가 같은 레벨에 있는 트리
- 이진 탐색 트리 (Binary Search Tree): 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가지는 이진 트리
- AVL 트리: 자동으로 균형을 맞추는 이진 탐색 트리로, 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1
- 레드-블랙 트리 (Red-Black Tree): 자가 균형 이진 탐색 트리의 일종으로, 색상 속성을 사용하여 균형을 유지
- B-트리: 데이터베이스와 파일 시스템에서 사용되는 균형 검색 트리로, 노드당 여러 개의 키를 저장할 수 있다.
트리의 순회 방법
- 전위 순회: 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리
- 중위 순회: 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리
- 후위 순회: 왼쪽 서브트리 -> 오른족 서브트리 -> 루트
이진 트리와 순회 방법 구현
public class BinaryTree : MonoBehaviour
{
//EX.1) 이진 트리 노드 생성 및 트리의 순회 메서드 구현
public class Node //노드 클래스
{
public int Data;
public Node Left; //왼쪽 자식 노드를 가리키는 Left
public Node Right; //오른쪽 자식 노드를 가리키는 Right
public Node(int data){
Data = data;
Left = Right = null; //Left와 Right 참조를 null로 초기화
}
}
private Node root;
//전위 순회 (루->왼->오)
public void PreOrder(Node node)
{
if(node==null) //만약 노드가 null이면 순회를 중단하고 반환
return;
Debug.Log(node.Data); //현재 노드의 데이터를 출력
PreOrder(node.Left); //왼쪽 자식 노드로 전위 순회를 이어감
PreOrder(node.Right); //오른쪽 자식 노드로 전위 순회를 이어감
}
//중위 순회 (왼->루->오)
public void Inorder(Node node)
{
if (node == null)
return;
Inorder(node.Left);
Debug.Log(node.Data);
Inorder(node.Right);
}
//후위 순회 (왼->오->루)
public void Postorder(Node node)
{
if (node == null)
return;
Postorder(node.Left);
Postorder(node.Right);
Debug.Log(node.Data);
}
// 레벨 순회 (Level-order)
public void LevelOrder()
{
if (root == null)
return;
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(root);
while (queue.Count > 0)
{
Node current = queue.Dequeue();
Debug.Log(current.Data + " ");
if (current.Left != null)
queue.Enqueue(current.Left);
if (current.Right != null)
queue.Enqueue(current.Right);
}
}
// 트리 생성 및 테스트
void Start()
{
root = new Node(100);
root.Left = new Node(50);
root.Left.Left = new Node(40);
root.Left.Right = new Node(60);
root.Right = new Node(110);
Debug.Log("전위 순회:");
PreOrder(root);
Debug.Log("중위 순회:");
Inorder(root);
Debug.Log("후위 순회:");
Postorder(root);
Debug.Log("레벨 순회:");
LevelOrder();
}
}
그래프(Graph)
그래프 (Graph)
: 노드들과 그들을 열결하는 간선들의 집한으로 이루어진 자료구조
그래프의 주요 특징
- 방향성: 방향 그래프와 무방향 그래프로 구분
- 가중치: 간선에 비용이나 거리 등의 가중치를 부여할 수 있음
- 순환성: 순환이 허용되어 한 노드에서 시작하여 같은 노드로 돌아올 수 있음
- 연결성: 모든 노드가 연결되어 있지 않을 수 있음
그래프 구현
using UnityEngine;
using System.Collections.Generic;
public class Graph : MonoBehaviour
{
public class Vertex
{
public string name;
public Dictionary<Vertex, float> neighbors;
public Vertex(string name)
{
this.name = name;
neighbors = new Dictionary<Vertex, float>();
}
}
private Dictionary<string, Vertex> vertices;
void Start()
{
vertices = new Dictionary<string, Vertex>();
}
// 정점 추가
public void AddVertex(string name)
{
if (!vertices.ContainsKey(name))
{
vertices.Add(name, new Vertex(name));
Debug.Log($"정점 {name}이(가) 추가되었습니다.");
}
}
// 간선 추가 (가중치 있는 방향 그래프)
public void AddEdge(string fromName, string toName, float weight)
{
if (vertices.ContainsKey(fromName) && vertices.ContainsKey(toName))
{
Vertex from = vertices[fromName];
Vertex to = vertices[toName];
if (!from.neighbors.ContainsKey(to))
{
from.neighbors.Add(to, weight);
Debug.Log($"간선 {fromName} -> {toName} (가중치: {weight})가 추가되었습니다.");
}
}
}
// 너비 우선 탐색 (BFS)
public void BFS(string startName)
{
if (!vertices.ContainsKey(startName)) return;
HashSet<Vertex> visited = new HashSet<Vertex>();
Queue<Vertex> queue = new Queue<Vertex>();
Vertex start = vertices[startName];
queue.Enqueue(start);
visited.Add(start);
while (queue.Count > 0)
{
Vertex current = queue.Dequeue();
Debug.Log($"방문: {current.name}");
foreach (var neighbor in current.neighbors.Keys)
{
if (!visited.Contains(neighbor))
{
visited.Add(neighbor);
queue.Enqueue(neighbor);
}
}
}
}
// 깊이 우선 탐색 (DFS)
public void DFS(string startName)
{
if (!vertices.ContainsKey(startName)) return;
HashSet<Vertex> visited = new HashSet<Vertex>();
DFSUtil(vertices[startName], visited);
}
private void DFSUtil(Vertex vertex, HashSet<Vertex> visited)
{
visited.Add(vertex);
Debug.Log($"방문: {vertex.name}");
foreach (var neighbor in vertex.neighbors.Keys)
{
if (!visited.Contains(neighbor))
{
DFSUtil(neighbor, visited);
}
}
}
// 다익스트라 최단 경로 알고리즘
public void Dijkstra(string startName)
{
if (!vertices.ContainsKey(startName)) return;
Dictionary<Vertex, float> distances = new Dictionary<Vertex, float>();
Dictionary<Vertex, Vertex> previous = new Dictionary<Vertex, Vertex>();
HashSet<Vertex> unvisited = new HashSet<Vertex>();
// 초기화
foreach (var vertex in vertices.Values)
{
distances[vertex] = float.MaxValue;
previous[vertex] = null;
unvisited.Add(vertex);
}
Vertex start = vertices[startName];
distances[start] = 0;
while (unvisited.Count > 0)
{
// 가장 가까운 미방문 정점 찾기
Vertex current = null;
float minDistance = float.MaxValue;
foreach (var vertex in unvisited)
{
if (distances[vertex] < minDistance)
{
current = vertex;
minDistance = distances[vertex];
}
}
if (current == null) break;
unvisited.Remove(current);
foreach (var neighbor in current.neighbors)
{
float alt = distances[current] + neighbor.Value;
if (alt < distances[neighbor.Key])
{
distances[neighbor.Key] = alt;
previous[neighbor.Key] = current;
}
}
}
// 결과 출력
foreach (var vertex in vertices.Values)
{
Debug.Log($"{startName}에서 {vertex.name}까지의 최단 거리: {distances[vertex]}");
}
}
}
레드-블랙 트리 구현
레드-블랙 트리 구현
using UnityEngine;
public class RedBlackTree : MonoBehaviour
{
// 노드의 색상을 정의하는 열거형
private enum NodeColor
{
Red,
Black
}
// 노드 클래스 정의
private class Node
{
public int data;
public Node left, right, parent;
public NodeColor color;
// 새로운 노드는 항상 Red로 생성 (조건 1 관련)
public Node(int data)
{
this.data = data;
left = right = parent = null;
color = NodeColor.Red;
}
}
private Node root;
private Node TNULL; // NIL 노드 (조건 3 관련)
void Start()
{
// NIL 노드는 항상 Black (조건 3)
TNULL = new Node(0);
TNULL.color = NodeColor.Black;
root = TNULL;
}
// 삽입 시 트리 재조정을 위한 좌회전
private void LeftRotate(Node x)
{
Node y = x.right;
x.right = y.left;
if (y.left != TNULL)
y.left.parent = x;
y.parent = x.parent;
if (x.parent == null)
root = y;
else if (x == x.parent.left)
x.parent.left = y;
else
x.parent.right = y;
y.left = x;
x.parent = y;
}
// 삽입 시 트리 재조정을 위한 우회전
private void RightRotate(Node x)
{
Node y = x.left;
x.left = y.right;
if (y.right != TNULL)
y.right.parent = x;
y.parent = x.parent;
if (x.parent == null)
root = y;
else if (x == x.parent.right)
x.parent.right = y;
else
x.parent.left = y;
y.right = x;
x.parent = y;
}
// 노드 삽입
public void Insert(int key)
{
Node node = new Node(key);
node.left = TNULL;
node.right = TNULL;
Node y = null;
Node x = root;
// 삽입 위치 찾기
while (x != TNULL)
{
y = x;
if (node.data < x.data)
x = x.left;
else
x = x.right;
}
node.parent = y;
if (y == null)
root = node; // 조건 2: 루트는 항상 Black이 되도록 InsertFixup에서 처리
else if (node.data < y.data)
y.left = node;
else
y.right = node;
InsertFixup(node); // 레드-블랙 트리 속성 복구
}
// 삽입 후 레드-블랙 트리 속성 복구
private void InsertFixup(Node k)
{
Node u;
// 조건 4: Red 노드의 자식은 Black이어야 함
while (k.parent != null && k.parent.color == NodeColor.Red)
{
if (k.parent == k.parent.parent.right)
{
u = k.parent.parent.left;
// Case 1: 삼촌 노드가 Red인 경우
if (u.color == NodeColor.Red)
{
// 색상 변경으로 해결
u.color = NodeColor.Black;
k.parent.color = NodeColor.Black;
k.parent.parent.color = NodeColor.Red;
k = k.parent.parent;
}
else
{
// Case 2 & 3: 삼촌 노드가 Black인 경우
if (k == k.parent.left)
{
k = k.parent;
RightRotate(k);
}
// 색상 변경 및 회전으로 해결
k.parent.color = NodeColor.Black;
k.parent.parent.color = NodeColor.Red;
LeftRotate(k.parent.parent);
}
}
else
{
// 위의 경우의 대칭
u = k.parent.parent.right;
if (u.color == NodeColor.Red)
{
u.color = NodeColor.Black;
k.parent.color = NodeColor.Black;
k.parent.parent.color = NodeColor.Red;
k = k.parent.parent;
}
else
{
if (k == k.parent.right)
{
k = k.parent;
LeftRotate(k);
}
k.parent.color = NodeColor.Black;
k.parent.parent.color = NodeColor.Red;
RightRotate(k.parent.parent);
}
}
if (k == root)
break;
}
// 조건 2: 루트는 항상 Black
root.color = NodeColor.Black;
}
}
▼개인정리
재귀함수
재귀함수
: 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식
- 종료조건 반드시 필요
- 주로 반복문 구현 시 사용
딕셔너리
딕셔너리
: Key-Value 쌍으로 데이터를 저장하는 자료구조
사용법
Dictionary<TKey, TValue>