본문 바로가기

Data structure3

[Java] Graph (Adjacency Matrix, Adjacency List) 정점(Vertex)과 간선(Edge)로 구성된 것, Graph(G) = (Vertex(V), Edge(E)) Graph 용어 정점(Vertex) - 노드, 특정할 수 있는 실체간선(Edge) - 정점 간 이어져 있는 선가중치(Weight) - 정점 간에 거리, 비용 (간선의 길이라고 생각해도 좋음)경로(Path) - 출발 정점에서 도착 정점까지의 거쳐 간 순서순환(Cycle) - 경로의 출발 정점과 도착 정점이 같은 경우차수(Degree) - 정점에 붙은 간선 수진입 차수(In-Degree) - 정점으로 들어오는 간선 수진출 차수(Out-Degree) - 정점에서 나가는 간선 수Graph 종류 유향 그래프(Directed Graph) - 특정 정점에서 특정 정점으로 이동하는 그래프무향 그래프(UnDire.. 2024. 7. 9.

[Java] Binary Search Tree 앞 포스팅에서 작성한 Tree의 비효율적인 문제를 개선하기 위해 생긴 이진 탐색 트리다.트리는 여러 자식을 가질 수 있지만 이진 검색 트리에서는 Binary Tree의 개념을 사용하기 때문에자식이 Left, Right만 존재한다. 이를 통해 Log_2 (N) 번만에 모든 수행을 끝낼 수 있다. 또, inorder를 수행 시 오름차순 정렬된 결과를 얻을 수 있다. package com.study.datastructrue.nonlinear.binarysearchtree;public class Node { int value; Node left; Node right; public Node(int value) { this.value = value; left = null;.. 2024. 7. 8.

[Java] Tree 트리 자료구조의 종류 : Tree, Binary Tree, Binary Serach Tree, Balanced Binary Serach Tree, Heap, Trie이번 포스트에서는 기본적인 Tree에 대해서만 작성해보자. Tree란 ? Node와 Edge로 구성된 방향이 존재하는 비순환 Graph의 한 종류이다. 그래서 DAG(Directed Acyclic Graphs)라고도 한다.그럼 Graph로 분류하면 되지 왜 Tree냐는 의심을 하게 된다.Tree는 Graph에서 몇가지 특성을 더 가진다. 1. 루트 노드가 하나 존재한다.2. 부모 노드는 하나밖에 존재하지 않는다.3. 노드는 0개 이상의 자식을 가지고 있다.4. 자식이 0개인 경우 단말노드(Leaf Node)라고 한다.5.. 위 특성을 지키는 .. 2024. 7. 7.

이전 1 다음

티스토리툴바