Data Structure

Home /
Categories /
Data Structure

Data structure
2020년 10월 23일

BST (이진 탐색 트리)를 기반으로 둔 Tree. Tree의 Rebalancing 방법 중 하나로 balanced한 트리이다. 각 노드는 값(key)말고도 색을 갖고 있으며, 색은 레드 or 블랙 2종류이다. 1. Red Black Tree가 갖는 특성 Root Property : 루트(root)노드는 블랙(black)이다. External Property : 모든 외부 노드 (external node)는 블랙이다. Depth Property : 모든 단말 노드(leaf n...

Stack Queue

Data structure
2021년 6월 3일

1. 스택 Last In First Out으로 최근에 추가한 항목이 가장 먼저 제거되는 데이터 방식 1) 함수 pop() : 스택에서 가장 위에 있는 항목을 제거 push() : item하나를 스택의 가장 윗 부분에 추가 peek() : 스택의 가장 위에있는 항목을 제거없이 값만 반환 isEmpty() : 스택이 비었는지 검사 2) 사용 예 재귀 알고리즘 웹 방문기록 실행 취소 연결 list를 이용한 코드 예(C 언어) 2. 큐 First In First Ou...

Heap

Data structure
2021년 6월 3일

Tree중 하나로 최대,최솟값을 찾아내는 연산을 빠르게 하기 위한 완전 이진 트리이다. (Complete Binary Tree ) 우선 순위를 무엇에 두냐에 따라 순서가 달라지기 때문에 자료가 들어온 시간을 우선순위로 놓는다고 하면 일반적인 큐도 우선순위 큐가 될 수 있다. 1. 최대 힙(Max Heap) 부모 노드의 key값이 자식 노드의 key값보다 크거나 같은 완전 이진 트리 c++을 이용한...

Array와 List

Data structure
2021년 6월 3일

1. 배열 가장 기본적인 자료구조로써, 논리적 저장 순서와 물리적 저장 순서가 일치하고 인덱스를 통하여 원소에 접근이 가능하다. 대부분의 언어에서 [] 를 이용해서 배열을 제공한다. 2. 리스트 배열과 달리 원소들 간의 논리적인 순서로 연결되어 구성있고, 삽입과 삭제를 수행하기 위해서는 첫 원소부터 모두 search해야한다. 자료구조 Tree에 기본이...

Graph

Data structure
2021년 6월 3일

연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조로 Tree도 그래프의 일종인데 그래프 중에서도 사이클이 허용되지 않는 그래프이다. 1. 개념 정점(vertex) / 노드(node) : 위치 간선(edge) / 링크(link) : 위치간의 관계 인접 정점 : 간선에 의해 직접 연결된 노드 차수 : 하나의 노드에 인접한 노드의 수 경로 길이 : 경로를...

Splay Tree

Data structure
2021년 6월 3일

Splaying이라는 기법이 사용되며, 이는 특정 노드에 대해 접근을 하면, 이를 루트로 위치하도록 재배치 하는 기법의 트리 1. 특징 구현이 단순 많이 접근한 노드에 대해서 빠른 접근이 가능하다 접근 빈도가 불균등하거나 비 랜덤 패턴의 경우 O(lgn)보다 더 유리하다. AVL-Tree와 RB-Tree와 달리 추가 데이터 저장 필요 없다. 최악의 경...

AA Tree

Data structure
2021년 6월 3일

RB-Tree를 응용한 트리로 RB-Tree의 많은 조건을 일부 제거하여 구현을 더 간단하게 만든 트리로 균형을 맞추기 위해 레벨의 개념을 사용한 트리이다. 부모와 레벨이 같은 자식 노드의 연결을 수평 링크라고 하며, 이 노드를 구분하기 위해 RED라는 개념을 이용한다. 1. 특징 왼쪽 자식은 RED가 될 수 없다. 연속으로 RED가 올 수 없다. (이중 RED...

AVL Tree

Data structure
2020년 10월 23일

BST (이진 탐색 트리)를 기반으로 둔 Tree. 어떤 노드를 기준으로 하더라도 왼쪽자식의 깊이와 오른쪽 자식의 깊이 차이가 1을 넘지 않는 트리 1. 용어 개념 정리 균형치 (Balance factor) : 자식노드의 깊이 차이 ( 왼쪽 서브트리의 높이 – 오른쪽 서브트리의 높이 ) BF는 -1, 0, 1이 기준이며, 이 범위를 벗어난다면, 그 트리의 균형은 깨진것이다. 2. 특징 BST의 모든 특징을 갖는다...

Tree

Data structure
2020년 9월 20일

그래프의 일종으로, 여러 노드가 한개의 노드를 가리킬 수 없는 구조 선형구조가 아닌 (비선형), 부모자식의 관계를 가지는 계층형 구조 1. 용어 개념 (설명) Node (노드): 트리를 구성하고 있는 각각의 요소를 의미한다. Edge (= link, 간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다. Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의...