Blog Posts
- Home /
- Blog Posts
Heap
- Data structure
- 2021년 6월 3일
Tree중 하나로 최대,최솟값을 찾아내는 연산을 빠르게 하기 위한 완전 이진 트리이다. (Complete Binary Tree ) 우선 순위를 무엇에 두냐에 따라 순서가 달라지기 때문에 자료가 들어온 시간을 우선순위로 놓는다고 하면 일반적인 큐도 우선순위 큐가 될 수 있다. 1. 최대 힙(Max Heap) 부모 노드의 key값이 자식 노드의 key값보다 크거나 같은 완전 이진 트리 c++을 이용한...
Read MoreArray와 List
- Data structure
- 2021년 6월 3일
1. 배열 가장 기본적인 자료구조로써, 논리적 저장 순서와 물리적 저장 순서가 일치하고 인덱스를 통하여 원소에 접근이 가능하다. 대부분의 언어에서 [] 를 이용해서 배열을 제공한다. 2. 리스트 배열과 달리 원소들 간의 논리적인 순서로 연결되어 구성있고, 삽입과 삭제를 수행하기 위해서는 첫 원소부터 모두 search해야한다. 자료구조 Tree에 기본이...
Read MoreGraph
- Data structure
- 2021년 6월 3일
연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조로 Tree도 그래프의 일종인데 그래프 중에서도 사이클이 허용되지 않는 그래프이다. 1. 개념 정점(vertex) / 노드(node) : 위치 간선(edge) / 링크(link) : 위치간의 관계 인접 정점 : 간선에 의해 직접 연결된 노드 차수 : 하나의 노드에 인접한 노드의 수 경로 길이 : 경로를...
Read MoreSplay Tree
- Data structure
- 2021년 6월 3일
Splaying이라는 기법이 사용되며, 이는 특정 노드에 대해 접근을 하면, 이를 루트로 위치하도록 재배치 하는 기법의 트리 1. 특징 구현이 단순 많이 접근한 노드에 대해서 빠른 접근이 가능하다 접근 빈도가 불균등하거나 비 랜덤 패턴의 경우 O(lgn)보다 더 유리하다. AVL-Tree와 RB-Tree와 달리 추가 데이터 저장 필요 없다. 최악의 경...
Read MoreAA Tree
- Data structure
- 2021년 6월 3일
RB-Tree를 응용한 트리로 RB-Tree의 많은 조건을 일부 제거하여 구현을 더 간단하게 만든 트리로 균형을 맞추기 위해 레벨의 개념을 사용한 트리이다. 부모와 레벨이 같은 자식 노드의 연결을 수평 링크라고 하며, 이 노드를 구분하기 위해 RED라는 개념을 이용한다. 1. 특징 왼쪽 자식은 RED가 될 수 없다. 연속으로 RED가 올 수 없다. (이중 RED...
Read More