스토리지

정점(Vertices)와 정점 사이를 잇는 간선(Edge)으로 이루어진 자료구조 Tree와 다르게 부모,자식 관계가 없다. 방향 그래프 무방향 그래프 - 간선에 방향이 있음 - 간선에 방향이 없음 namespace Study04 { public class App { public App() { Graph graph = new Graph(); string seoul = "서울"; string daegu = "대구"; string gangneung = "강릉"; string daejeon = "대전"; string busan = "부산"; //정점 생성 및 추가 graph.AddVertex("서울"); graph.AddVertex("대전"); graph.AddVertex("대구"); graph.AddVerte..

1. 삽입 및 검색 연산 구현, 검증 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Study03 { public class Node { public int data; public Node left; public Node right; public Node(int data) { this.data = data; } } public class BST { private Node root; public BST() { } public void Add(int data) { if (root == null) { root = new Node(da..

정의 왼쪽 노드의 값이 루트 노드의 값보다 작고, 오른쪽 노드의 값이 루트 노드의 값보다 큰 이진트리. 왼쪽에서 오른쪽으로 갈 수록 크므로 정렬되어 있다. Add연산의 경우, 알아서 자기가 위치할 자리를 찾아간다. 예시코드 using System; namespace Study03 { public class Node { public int data; public Node left; public Node right; public Node(int data) { this.data = data; } } public class BSTree { private Node root; public BSTree() { } public void Add(int data) { if(root == null) { root = new ..

using System; namespace Study03 { public class App { public App() { /* * A * / \ * / \ * B C * / \ / * / \ / * D E F */ BinaryTree tree = new BinaryTree(); Node root = tree.SetRoot("A"); Node b = tree.SetLeft(root, "B"); Node c = tree.SetRight(root, "C"); Node d = tree.SetLeft(b, "D"); Node e = tree.SetRight(b, "E"); Node f = tree.SetLeft(c, "F"); Console.Write("Preorder Traversal : "); tree.Pre..

private void PreorderTraversalImpl(Node node) { if (node == null) return; Console.Write("{0} ", node.data); PreorderTraversalImpl(node.left); PreorderTraversalImpl(node.right); } public void PreorderIterative() { Stack stack = new Stack(); stack.Push(this.root); while (stack.Count > 0) { var temp = stack.Pop(); Console.Write("{0} ", temp.data); if (temp.right != null) { stack.Push(temp.right); }..

Tree를 이루는 Array의 형태 ( 1부터 시작하는 Index ) 0 1 2 3 4 5 6 7 null A B C D null null G ( ∵ 배열을 1부터 시작하는 이유는 인덱스가 잘 보이고 계산하기 편하다... ) using System; namespace Study02 { public class BinaryTree { private string[] arr; public BinaryTree(int capacity = 8) { this.arr = new string[capacity]; } public void SetRoot(string data) { this.arr[1] = data; } public string GetRoot() { return this.arr[1]; } public void ..

정의 자식 노드의 수가 2개 이하인 것을 이진트리 (Binary Tree)라고 한다. 구현방법 구현방법 장단점 링크드리스트 레퍼런스때문에 헷갈린다. 힙영역을 사용해 공간이 충분하다. 배열 쉽다, 공간복잡도가 높아진다. Heap 자료구조 구현방법. 작업 수행시간 연산 수행시간 (평균) 수행시간 (최악) 삽입 O(log n) O(n) 삭제 O(log n) O(n) 검색 O(log n) O(n) 평균의 수행시간들은 모두 AVL 균형트리가 기준이다. 평균 수행시간 : 좌우 서브트리의 균형이 맞춰진 AVL 트리 or Red Black Tree 최악 수행시간 : 사향트리 (한쪽으로 쏠린 트리) ∵ 이진트리의 성능을 최대로 뽑을려면 양쪽 서브트리의 높이의 차가 2 이하로 유지되어야 한다. 수행시간 평균 계산과정 더보..

using System; using System.Collections.Generic; namespace Study02 { public class LCRSTree { public LCRSNode root; public LCRSTree(string data) { this.root = new LCRSNode(data); } public LCRSNode AddChild(LCRSNode parent, string data) { LCRSNode child = new LCRSNode(data); if (parent.left == null) { parent.left = child; } else { var temp = parent.left; while (temp.right != null) { temp = temp.rig..

namespace Study01 { public class Node { public string data; public Node left; public Node right; public Node(string data) { this.data = data; } } } using System; using System.Collections.Generic; namespace Study01 { public class Tree { private Node root; public Tree(string data) { this.root = new Node(data); } public Node AddChild(Node parent, string data) { if (parent == null) return null; if (..

정의 여러 노드들이 가지처럼 연결되어 있는 비선형적 자료구조. 나무를 뒤집어놓은 것 처럼 생겼다 (Root 노드부터 시작해서 여러개의 Child 노드로 이어진다) 자식은 부모노드를 하나만 가질 수 있고 부모노드는 여러개의 자식노드를 가질 수 있다. 표현은 N-링크 표현법과 왼쪽 자식, 오른쪽 형제 표현법이 있다. 1. N-링크 표현법 using System.Collections.Generic; namespace Study01 { public class TreeNode { public string data; public List links; public TreeNode(string data, int max = 3) { this.data = data; this.links = new List(); } } } ..