cs 스터디 - (2) 자료구조

Yuri JI·2022년 8월 29일

cs스터디

목록 보기

2/9

📒 자료구조

1) Array vs Linked List

Element 검색
- Array는 Random Access를 지원한다. index를 통해 Element에 접근이 가능하다. 따라서, 특정 Element에 접근하는 시간복잡도는 O(1)이다.
- LinkedList는 Sequential Access를 지원한다. 어떤 Element를 접근할 때는 처음 element부터 순차적으로 검색하면서 찾아야하기 때문에 시간 복잡도는 O(n)이다.
저장 방식
- Array는 논리적 저장 순서와 물리적 저장 순서가 같다. element들은 인접한 memory위치에 저장되거나 연이어 저장된다.
- LinkedList의 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. 새로운 element들은 memory 어딘가에 저장된다.
삽입 / 삭제
- Array Element들의 메모리 위치가 연속적이고 고정적이기때문에 O(n)만큼의 시간을 요구한다.
- LinkedList의 경우, 새로운 element는 첫 번째 사용 가능한 빈 Memory 위치에 저장되며, 이전 Node에 Memory 위치의 주소를 저장하는 단 하나의 overhead만이 존재한다. 따라서 Insertion과 Deletion 연산이 빠르다.

2) Stack and Queue

선형 자료구조인 stack과 queue

Stack
Stack은 후입선출(LIFO: Last In First Out)의 자료구조를 구현한 클래스로 나중에 넣은 객체가 먼저 빠져나가는 구조이다.

	Stack<E> stack = new Stack<E>();

Queue
- Queue는 선입선출(FIFO : First In First Out)의 자료구조를 구현한 인터페이스로 먼저 넣은 객체가 먼저 빠져나가는 구조이다.

    Queue<E> queue = new LinkedList<E>();

3) Tree

방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조를 가지고 있다. 계층적 관계를 표현하는 자료구조이다.

구성요소
Node : 트리를 구성하고 있는 각각의 요소
Edge : 트리를 구성하기 위해 노드와 노드를 연결하는선
Root Node: 트리 구조에 최상위에 있는 노드
Terminal Node = Leaf Node = 단말 노드 : 하위에 다른 노드가 연결되어 있지 않은 노드
Internal Node (내부 노드, 비 단말 노드): 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.
level: 루트로부터 몇 번째 깊이인지
degree = 차수: 한 정점에서 뻗어나가는 간선 수
height: 트리의 최고 레벨
특징
루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
루트에서 특정 정점으로 가는 경로는 유일하다.
BST(Binary Search Tree)
효율적인 탐색을 위해서 데이터를 저장하는 규칙을 가지며 해당 규칙은 특정 데이터의 위치를 찾는데 사용될 수 있다.
- 규칙
- 특징 이진 탐색 트리의 노드에 저장된 키는 유일하다.
- 부모의 키가 왼쪽 자식 노드의 키보다 크다.
- 부모의 키가 오른쪽 자식 노드의 키보다 작다.
- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

이진 트리의 탐색 연산은 O(logN)이지만 높이에 따라 O(h)의 시간 복잡도를 갖는다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문이다. 따라서 편향 트리가 될 경우 (저장 순서에 따라 노드가 한 쪽으로만 추가될 경우) 성능에 영향을 미치게 되며, 탐색의 worst case가 되어 O(n)의 시간 복잡도를 가지게 된다.

배열보다 많은 메모리를 사용하며 데이터를 저장했지만 탐색에 필요한 시간복잡도가 같게 되어 비효율적이다. 이를 해결하기 위해 rebalancing 기법이 등장했다. 트리의 균형을 잡아서 편향 트리가 되지 않게 하는 것이다.

이 기법을 구현 트리: Red-Black tree, AVL Tree