on
자료구조
자료구조
Array vs Linked List
Array
논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 index로 해당 원소에 접근할 수 있다.
random access가 가능하다는 장점이 있다.
하지만!
만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉 빈공간 발생.
따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift 해줘야 하는 비용이 발생하게 된다.
그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 시간 복잡도의 worst case는 O(n)이 된다.
삽입의 경우도 마찬가지!
Linked List
Array의 문제점을 해결하기 위한 자료구조.
각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. 그래서 이 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1)만에 해결할 수 있는 것이다.
하지만!
원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search하는 과정에 있어서 첫번째 원소부터 다 확인해봐야하는 문제가 있다. 이 과정 때문에, 어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생하게 된다.
Tree 구조의 근간이 되는 자료구조이며, Tree에서 사용되었을 때 그 유용성이 드러난다.
정리
Array : index로 빠르게 값을 찾는 것이 가능함
LinkedList : 데이터의 삽입 및 삭제가 빠름. 검색할 때 처음부터 살펴봐야하므로 시간이 더 걸린다.
ArrayList : 데이터를 찾는데 빠르지만, 삽입 삭제가 느림
Stack and Queue
Stack
선형 자료구조의 일종으로 Last In First Out (LIFO) : 나중에 들어간 원소가 먼저 나옴
언제 사용?
함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법
push() : 데이터 넣음
pop() : 데이터 최상위 값 뺌
isEmpty() : 비어있는 지 확인
isFull() : 꽉차있는 지 확인
Queue
선형 자료구조의 일종으로 Fisrt In First Out (FIFO) : 먼저 들어간 원소가 먼저 나옴
언제 사용?
버퍼, 마구 입력된 것을 처리하지 못하고 있는 상황, BFS
enQueue() : 데이터 넣음
deQueue() : 데이터 뺌
isEmpty() : 비어있는 지 확인
isFull() : 꽉차있는 지 확인
front : deQueue 할 위치 기억
rear : enQueue 할 위치 기억
일반 큐의 단점 : 큐에 빈 메모리가 남아 있어도, 꽉 차있는 것으로 판단할 수 있음 (rear가 끝에 도달했을 때)
이를 개선한 것이
원형 큐 : 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주함
원형 큐의 단점 : 메모리 공간은 잘 활용하지만, 배열로 구현되어 있기 때문에 큐의 크기가 제한
이를 개선한 것이
연결리스트 큐 : 크기가 제한이 없고 삽입, 삭제가 편리
Tree
스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 계층적 관계를 표현하는 자료구조.
Node : 트리를 구성하고 있는 각각의 요소
Edge : 트리를 구성하기 위해 노드와 노드를 연결하는 선
Root Node : 트리 구조에서 최상위에 있는 노드
Terminal Node(leaf Node) : 하위에 다른 노드가 연결되어 있지 않은 노드
Internal Node : 단말 노드를 제외한 모든 노드로 루트 노드 포함
Binary Tree
루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 진다. 또한 나뉘어진 두 서브 트리도 모두 이진 트리어야 한다.
공집합도 이진트리에 포함. 노드가 하나 뿐인 것도 이진 트리 정의에 만족
Perfect Binary Tree (포화 이진 트리) : 모든 레벨이 꽉 찬 이진 트리
Complete Binary Tree (완전 이진 트리) : 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리
Full Binary Tree (정 이진 트리) : 모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리
BST(Binary Search Tree)
이진 탐색 트리의 목적 : 이진탐색 + 연결리스트
이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN), but 삽입, 삭제 불가능
연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), but 탐색하는 시간 복잡도가 O(N)
즉, 효율적인 탐색 능력을 가지고, 자료의 삽입 삭제도 가능하게 만들자
BST의 핵심연산
검색, 삽입, 삭제, 트리 생성, 트리 삭제
삭제의 3가지 경우
1. 자식이 없는 leaf 노드일 때 : 그냥 삭제
2. 자식이 1개인 노드일 때 : 지워진 노드에 자식 올리기
3. 자식이 2개인 노드일 때 : 오른쪽 자식 노드에서 가장 작은 값 or 왼쪽 자식 노드에서 가장 큰 값 올리기
이진 탐색 트리는 이진 트리의 일종이다. 단, 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다.
이진 탐색 트리의 노드에 저장된 키는 유일하다.
부모의 키가 왼쪽 자식 노드의 키보다 크다.
부모의 키가 오른쪽 자식 노드의 키보다 작다.
왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.
배열보다 많은 메모리를 사용하며 데이터를 저장했지만 탐색에 필요한 시간 복잡도가 같게 되는 비효율적인 상황이 발생한다. 이를 해결하기 위해 Rebalancing 기법이 등장하였다.
Rebalancing : 균형을 잡기 위한 트리 구조의 재조정
이 기법을 구현한 트리에는 여러 종류가 존재하고, 그 중에서 하나가 Red-Black Tree
Binary Heap
힙은, 우선순위 큐를 위해 만들어진 자료구조다.
(우선순위 큐 : 우선순위의 개념을 큐에 도입한 자료구조)
언제 사용?
시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산
자료 구조의 일종으로 Tree의 형식을 하고 있으며, Tree 중에서도 배열에 기반한 Complete Binary Tree이다.
배열에 트리의 값들을 넣어줄 때, 0번째는 건너뛰고 1번 index부터 루트노드가 시작된다.
노드의 고유번호 값과 배열의 index를 일치시켜 혼동을 줄이기 위함
힙 트리는 중복된 값 허용하지만 이진 탐색 트리는 중복값 허용하지 않는다.
힙의 종류
Max Heap (최대힙) : 각 노드의 값이 해당 children의 값보다 크거나 같은 complete binary tree
Min Heap (최소힙) : 최대힙의 반대
Root node에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 시간 복잡도는 O(1)이다.
heap의 구조를 계속 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요하다.
여기서 heap은 맨 마지막 노드를 루트 노드로 대체시킨 후, 다시 heapify 과정을 거쳐 heap 구조를 유지한다.
이런 경우, 결국 O(log n)의 시간복잡도로 최대값 또는 최소값에 접근할 수 있게 된다.
from http://jjcec.tistory.com/14 by ccl(A) rewrite - 2021-09-08 21:26:35