트라이(Trie) 문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조이다. Prefix Tree, Retrieval Tree, Digital Search Tree 라고도 부른다. 정렬된 트리구조다. 문자열같은 것들을 트라이에 구축을 해둬야하기 때문에 문자열 저장을 위한 메모리가 (많이)필요하지만 탐색이 빠르다. 길이가 N개인 문자열 탐색의 시간복잡도는 O(N)이다. 대신 사전에 이런 문자열들을 이 트라이 형태로 구축을 해야하는데 구축할 때 드는 생성시 시간복잡도는 트라이에 넣으려는 문자열의 개수가 M개라고 할 때 O(MN)이다. 하지만 한번 구축하면 탐색할 때 굉장히 빠르다는 장점이 있다. 동일 위치에서의 공통 부분들은 중복해서 들어가지는 않지만 다른 부분에 대해서는 트라이를 적용시켜줘야 하기 ..
선형 큐에 대한 설명과 힙(보통 우선순위 큐를 구현할 때 사용되는 자료구조)에 대한 설명은 아래 링크에 있다. 더보기 [자료구조] 큐 / 원형 큐 / 양방향 큐 [비선형 자료구조] 힙(Heap) 우선순위 큐(Priority Queue) 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. ( 일반적인 큐는 선입선출(FIFO)인 선형 자료구조이다. ) 일반적으로 힙(Heap)을 이용하여 구현한다. (힙으로 구현했을 때, 우선순위 큐의 Enqueue, Dequeue는 최소(or 최대) 힙의 삽입, 삭제와 같다.) Dequeue시, 우선순위가 높은 순서대로 나간다. 우선순위가 같은 경우에는 FIFO가 적용된다. 우선순위 큐의 구현..
힙에 들어가기에 앞서, 이진 트리에 대해서는 알아두는 편이 좋다. 이진 트리 포스팅 더보기 트리(1) - 이진 트리(Binary Tree) 힙(Heap) 힙은 우선순위 큐를 구현하는데 자주 사용되는 자료구조이다. ( 우선순위 큐 링크 ) 완전 이진 트리(Complete Binary Tree) 형태이다.(왼쪽부터 차곡히 다 쌓인 트리) BST(이진 탐색 트리)와 달리 중복 값을 허용한다. 반 정렬 상태(느슨한 정렬 상태)를 유지한다. 반 정렬 상태가 무슨 뜻이냐면 최소 힙(Min Heap)에서는 루트 노드(최상단 노드)가 가장 최소값이고, 최소 힙 기준으로 부모 노드의 값은 자식 노드보다 작다. 최대 힙(Max Heap)에서는 루트 노드(최상단 노드)가 가장 최대값이고, 최대 힙 기준으로 부모 노드의 값은..
그래프(Graph) 그래프는 트리의 상위 개념의 자료구조로, 정점과 간선으로 구성된다. 연결된 정점간의 관계를 표현할 수 있는 자료구조이다. 그래프의 용도는 지하철 노선도나 통신 네트워크같은데에서 쓰인다. 그래프에서 사용되는 용어 정점(Vertex) : 그래프 구조의 자료 값을 담고 있는 단위(노드) 간선(Edge) : 노드 간의 연결선(link, branch) 인접 정점(Adjacent vertex) : 간선 하나를 두고 바로 연결된 정점 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수의 2배 진입 차수(In-degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(Out-degree) : 방향 그래프..
저번 포스팅에선 AVL 트리에 대해 알아보았다. [비선형 자료구조] 트리 링크 더보기 트리(1) - 이진 트리(Binary Tree) 트리(2) - 이진탐색트리 트리(3) - AVL 트리 이번 포스팅에서는 AVL 트리와 같이 자기 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)의 종류중 하나인 Red-Black 트리에 대해 알아보자. 마찬가지로 O(logN)의 시간복잡도를 가진다. Red-Black Tree(RB tree) 여러개의 규칙으로 이루어진 트리로 다소 이해하기 어려운 면이 있다. AVL 트리보다 균형을 맞추는 방법이 직관적이지는 않다.자바의 TreeSet과 TreeMap은 Red-Black 트리를 베이스로 한 구현을 사용한다. RB 트리는 다음과 같은 조건을..
저번 포스팅에선 트리, 이진 트리에 대해 알아보았다. [비선형 자료구조] 트리 링크 더보기 트리(1) - 이진 트리(Binary Tree) 트리(2) - 이진탐색트리 트리(4) - Red-Black 트리 이전 포스팅에서 구현한 기본적인 이진 탐색 트리의 경우 삽입 순서에 따라 편향이 발생할 수 있다. 편향이 발생한 경우 탐색에 O(N)의 시간이 필요하므로 성능이 떨어지게 된다. 이번 포스팅에서는 BST의 종류중 조건에 맞춰 균형을 유지하도록 하는 AVL 트리에 대해 알아보자. 균형이진탐색트리(Balanced Binary Search Tree) 노드의 삭제나 삽입에 균형을 유지하도록 조건을 맞춰서 코드가 더 짜여진 트리로 AVL 트리, Red-Black 트리 등이 있다. 편향을 해결하여 탐색에 O(logN..
저번 포스팅에선 트리, 이진 트리에 대해 알아보았다. [비선형 자료구조] 트리 링크 더보기 트리(1) - 이진 트리(Binary Tree) 트리(3) - AVL 트리 트리(4) - Red-Black 트리 이번 포스팅에서는 이진 탐색 트리에 대해 알아보자. 이진 탐색 트리(Binary Search Tree = BST) 이진 탐색 트리는 이진 트리의 종류중 하나로 다음과 같은 특징을 가지고 있다. 왼쪽 자식 노드의 키는 부모 노드의 키보다 작다. 오른쪽 자식 노드의 키는 부모 노드의 키보다 크다. 각각의 서브트리도 이진탐색트리를 유지한다. 중복된 키를 허용하지 않는다. 중위순회(왼중오)하면 오름차순으로 (탐색)나온다. 기존 이진트리에 비해 탐색이 빠르다.(하지만 균형 유지가 필요하다.) 이진 트리는 규칙없이..
[비선형 자료구조] 트리 링크 더보기 트리(2) - 이진탐색트리 트리(3) - AVL 트리 트리(4) - Red-Black 트리 트리(Tree) 트리는 노드와 링크로 구성된 자료구조다. 그래프의 일종으로 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph) 또는 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류 이다.(Acyclic = cycle이 존재하지 않는 그래프) 계층적 구조(계층 모델)를 나타낼 때 사용한다. 조직도, 가계도, 폴더(디렉토리, 서브 디렉토리)와 같은 파일시스템 구조나 계층적으로 저장할 때 많이 쓰인다. 구조상 데이터 저장보다는 저장된 데이터의 효과적인 탐색을 위해 사용된다. 선형 자료구조는 정렬이 되어있지않은 상태에..
연결리스트는 데이터를 링크로 연결해서 관리하는 자료구조다. 자료의 순서는 정해져 있지만 메모리상의 연속성은 보장되지 않는다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전, 다음 노드와의 연결을 담당한다. 연결리스트에서 사용되는 용어는 다음과 같다. node : 데이터 저장 단위로 값과 포인터로 구성된다.(내부 부품이기에 외부에 노출되지 않는것이 좋다. private) pointer : 다음 노드나 이전 노드의 연결 정보(다음 혹은 이전 노드의 주소(정보)값)(Next) head : 가장 처음에 위치하는 노드를 일컫는다. tail : 가장 마지막에 위치하는 노드를 일컫는다. 노드를 가리키는 포인터는 C에서는 포인터변수가 있었지만 여기서는 그냥 같은 타입으로 해서 연결해주면 된다. no..
ADT(Abstract Data Type) ADT(Abstract Data Type)은 추상자료형, 구현방법을 명시하지 않고 자료구조의 특성들과 어떤 Operation이 있는지를 설명하는 자료구조의 한 형태이다. 대표적으로 스택과 큐가 있다. 어떻게 구현되는지가 추가되면 DS로써의 스택과 큐가 된다. 자바 기준으로는 interface가 ADT, class가 DS이다. 스택이 어쩌고 저쩌고 -> ADT 관점, 그래서 스택을 어떤 구현체를 써서 구현했어 -> DS 관점이다. 선형(Linear) 자료구조, 비선형(Nonlinear) 자료구조 선형 자료구조는 하나의 자료 뒤에 하나의 자료가 존재하는 것이다. 자료간의 1:1 관계가 유지되는 것이다. 스택, 큐, 배열 등이 이에 해당한다. 비선형 자료구조는 하나의..
