🦌 크리스마스 D-10 기념으로 트리에 대해서 알아보자 🎅🏻 물론 크리스마스 트리 말고 ,,  자료구조 트리이다 ^_^ 트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조이다. 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1이다. 부모-자식 관계로 이루어져 있다. 트리 내에 하위 트리가 있고, 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 하다.

🦌 크리스마스 D-10 기념으로 트리에 대해서 알아보자 🎅🏻 

물론 크리스마스 트리 말고 ,,  자료구조 트리이다 ^_^ 

목차

1. 트리 (Tree)란 ?
2. 이진 탐색 트리 (Binary Search Tree)
3. 트리의 순회 (Tree Travelsal)

트리 (Tree)란 ?

트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조이다. 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1이다. 부모-자식 관계로 이루어져 있다. 트리 내에 하위 트리가 있고, 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 하다. 컴퓨터의 directory 구조가 트리 구조의 대표적인 예이다.

❄️ 루트 노드 (root node) : 부모가 없는 최상위 노드

❄️ 단말 노드 (leaf node) : 자식이 없는 노드

❄️ 크기 (size) : 트리에 포함된 모든 노드의 개수

❄️ 깊이 (depth) : 루트 노드부터의 거리 (= 간선의 수)

❄️ 높이 (height) : 깊이 중 최댓값

❄️ 차수 (degree) : 각 노드의 (자식 방향) 간선 개수 (= 하위 트리 개수)

이진 탐색 트리 (Binary Search Tree)

이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종이다.

🔔 이진 탐색 트리의 특징 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

이진 탐색 트리가 이미 구성되어 있다면 데이터를 조회하는 방법은 다음과 같다.

🔔 루트 노드부터 방문하여 탐색을 진행한다.

🔔 현재 노드와 찾고자 하는 값을 비교한다.

🔔 원소를 찾았다면 탐색을 종료한다.

트리의 순회 (Tree Traversal)

트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법을 의미한다.

대표적인 트리 순회 방법은 다음과 같다.

🎄 전위 순회 (pre-order traverse) : 루트를 먼저 방문한다.

    • 노드 - 왼쪽 자식 - 오른쪽 자식 순

🎄 중위 순회 (in-order traverse) : 왼쪽 자식을 방문한 뒤에 루트를 방문한다.

    • 왼쪽 자식 - 노드 - 오른쪽 자식 순

🎄 후위 순회 (post- order traverse) : 오른쪽 자식을 방문한 뒤에 루트를 방문한다.

    • 왼쪽 자식, 오른쪽 자식, 노드 순

전위 순회 : A - B - D - E - C - F - G

중위 순회 : D - B - E - A - F - C - G

후위 순회 : D - E - B - F - G - C - A

Reference

덱은 double-ended queue를 줄여서 표현한 것으로, 양방향으로 넣고 뺄 수 있다는 사실에 초점이 맞추어져 지어진 이름이다. 스택과 큐의 특성을 모두 갖는, 둘을 조합한 형태의 선형 자료구조로 이해되고 있다.

목차

덱 (Deque) 이란?

• 덱의 분류
• 덱의 사용
• Java class 'Deque'
• 장단점
• 시간 복잡도 (Time complexity)

덱 (Deque) 이란 ?

양쪽에서 삽입과 삭제가 가능한 자료구조이며 스택과 큐의 연산을 모두 지원한다. 덱은 double-ended queue를 줄여서 표현한 것으로, 양방향으로 넣고 뺄 수 있다는 사실에 초점이 맞추어져 지어진 이름이다. 스택과 큐의 특성을 모두 갖는, 둘을 조합한 형태의 선형 자료구조로 이해되고 있다.

• appendleft : 왼쪽에서(앞에서) 데이터를 삽입
• append : 오른쪽에서(뒤에서) 데이터를 삽입
• popleft : 왼쪽에서 데이터를 꺼내기 (삭제)
• pop : 오른쪽에서 데이터를 꺼내기 (삭제)

덱의 분류

• Scroll : 입력 제한 덱 (Input restricted deque) - 입력은 한쪽에서만 발생, 출력은 양쪽에서 발생
• Shelf : 출력 제한 덱 (Output restricted deque) - 입력은 양쪽에서 발생, 출력은 한쪽에서만 발생

덱의 사용

덱은 자주 쓰이지 않는다.

주로 앞, 뒤 모두에서 삽입, 삭제가 이루어질 때 사용한다.

데이터가 가변적일 때 사용한다.

• 보통 스케줄링에 사용
• 우선순위 조절 시 사용

Java class ‘Deque’

// Deque 선언, ArrayDeque 사용
Deque<E> deque = new ArrayDeque<>();

// First : 왼쪽, Last : 오른쪽

// 값 추가 (push) 
deque.offerFirst(추가할 값); //정상적으로 삽입 시 true, 용량 제한 시 false
deque.offerLast(추가할 값); 

deque.addFirst(추가할 값); // 용량 제한 시 예외(Exception) 발생 //push()와 동일
deque.addLast(추가할 값); //add()와 동일

// 값 꺼내기 (pop)
deque.pollFirst(); // 덱이 비어있으면 null // poll()과 동일
deque.pollLast();

deque.removeFirst(); // 덱이 비어있으면 예외 발생 // remove(), pop()과 동일 
deque.removeLast();

// 맨 앞과 맨 뒤의 값 출력
deque.peekFirst(); // 덱이 비어있으면 null //peek()와 동일
deque.peekLast();

deque.getFirst(); // 덱이 비어있으면 예외 발생
deque.getLast();

// 크기 구하기
deque.size();

// 비어있는지 확인 후 boolean 타입으로 반환
deque.isEmpty();

// 검색 후 삭제
deque.removeFirstOccurrence(제거할 값); // 왼쪽(앞)에서부터 탐색
deque.remove(제거할 값); // first와 동일
deque.removeLastOccurrence(제거할 값); // 오른쪽(뒤)에서부터 탐색

// 값이 있는지 확인
deque.contain(확인할 값);

// 순회 (Iterator)
deque.iterator(); // iterator로 변환
deque.descendingIterator(); // 역순 iterator 변환

장단점

장점 

• 크기가 가변적이다.
• 데이터 삽입, 삭제가 빠르다.
• 원하는 데이터에 바로 접근이 가능하다.

단점

• 구현이 어렵다.
• 중간 데이터의 삽입, 삭제가 어렵다.

시간 복잡도 (Time complexity)

• Insertion O(1)
• Deletion O(1)
• Search O(1)

큐는 스택과 함께 가장 많이 볼 수 있는 선형 자료구조이다. 스택과 반대로 선입선출이다. 즉, FIFO(First in First Out) 혹은 LILO(Last In Last Out)구조이다. Queue는 사전적으로 ‘줄을 서서 기다리다’라는 의미를 가진다. 매표소에서 먼저 줄을 선 사람이 먼저 표를 사는 것과 같은 논리이다. 큐의 데이터는 맨 뒤로만 들어와서 맨 앞으로만 나갈 수 있다.

목차

큐 (Queue) 란 ?

• Enqueue와 Dequeue
• 큐의 사용
• Overflow와 Underflow
• Java class 'Queue'
• 큐 구현 방법
• 큐 종류
• 시간 복잡도 (Time comoplexity)

큐 (Queue) 란?

큐는 스택과 함께 가장 많이 볼 수 있는 선형 자료구조이다. 스택과 반대로 선입선출이다. 즉, FIFO(First in First Out) 혹은 LILO(Last In Last Out)구조이다. Queue는 사전적으로 ‘줄을 서서 기다리다’라는 의미를 가진다. 매표소에서 먼저 줄을 선 사람이 먼저 표를 사는 것과 같은 논리이다. 큐의 데이터는 맨 뒤로만 들어와서 맨 앞으로만 나갈 수 있다.

Enqueue와 Dequeue

• Enqueue : 큐 맨 뒤에 데이터 추가
• Dequeue : 큐 맨 앞의 데이터 삭제
• peek : front에 위치한 데이터 조회
• front : 큐 맨 앞의 위치(인덱스)
• rear : 큐 맨 뒤의 위치(인덱스)

큐의 사용

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 사용한다.

보통 컴퓨터 버퍼에서 주로 사용한다.

동시다발적으로 입력이 들어오면 대기열을 만들어 순차적으로 처리하는 것이다.

다음은 큐를 사용하는 사례이다.

• 프린트 출력 처리
• 프로세스 관리
• CPU 스케줄링, 디스크 스케줄링
• 그래프의 넓이 우선 탐색 (BFS)에서 사용
• 서로 다른 스레드 혹은 프로세스 사이에서 자료를 주고 받을 때 자료를 일시적으로 저장 (비동기 전송) (ex) IO 버퍼)

Overflow와 Underflow

• Queue Overflow : 가득 찬 큐에 데이터를 추가하려고 할 때
• Queue Underflow : 빈 큐에서 데이터를 꺼내려고(삭제) 할 때

Java class ‘Queue’

// Queue 선언, Linkedlist 사용
Queue<E> queue = new LinkedList<>();

// 값 추가
queue.add(추가할 값); // 삽입 성공 시 true, 여유 공간이 없어 삽입 실패 시 IllegalStateException 발생
queue.offer(추가할 값);

// 값 꺼내기 (삭제)
queue.poll(); // 맨 앞의 값 반환 후 제거, 큐가 비어있으면 null 반환
queue.remove(); // 맨 앞의 값 제거
queue.clear(); // 초기화

// 맨 앞의 값 출력
queue.peek();

// 모든 값 출력 (Iterator 클래스 사용)
Iterater iter = queue.iterator();
while (iter.hasNext()) {
	System.out.println(iter.next());
}

// 크기 구하기
queue.size();

// 비어있는지 확인 후 boolean 타입으로 반환
queue.isEmpty();

큐 구현 방법

스택과 마찬가지로 배열 혹은 연결리스트를 이용하여 구현할 수 있다.

큐 종류

1. 선형 큐 (Linear Queue)

기본적인 큐의 형태로써 막대 모양으로 된 큐이다.

선형 큐는 문제점이 있다.

선형 큐에서 삽입(Enqueue), 삭제(Dequeue)를 계속 반복하다 보면 Rear가 맨 마지막 인덱스 ‘5’를 가리키고, 앞에는 비어 있을 수 있지만 이를 꽉 찼다고 인식한다. 이는 데이터 삭제 시 한 칸 앞으로 이동하지 않기 때문이다.

• 선형 큐 문제점
  • 배열 구현 시 크기가 제한되어 있다.
  • 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다. (지연시간 발생)
  • Enqueue, Dequeue 작업이 계속적으로 일어나면 큐가 비어있어도 데이터 추가가 불가능하다. (Overflow 발생)

2. 원형 큐 (Circular Queue)

선형 큐의 문제점을 보완한 것이다. 원형 큐는 1차원 배열 형태의 큐를 원형으로 구성하여 배열의 처음과 끝을 연결한다. 환형 큐라고도 한다. 데이터 추가 시 Rear가 한 칸 움직이고, 데이터 삭제 시 Front가 한 칸 움직인다.

시간 복잡도 (Time complexity)

• Insertion O(1)
• Deletion O(1)
• Search O(n)

물건을 쌓아 올리듯이 데이터를 쌓는 자료구조로, 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료구조(Linear Data Structur)이다. ‘Pushdown list’라 부르기도 한다.

목차

스택 (Stack) 이란?

• Push
• Pop
• 스택의 사용
• Overflow와 Underflow
• Java class 'Stack'
• 스택 구현 방법
• 시간 복잡도 (Time complexity)

스택 (Stack) 이란 ?

물건을 쌓아 올리듯이 데이터를 쌓는 자료구조로,

한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료구조(Linear Data Structur)이다.

‘Pushdown list’라 부르기도 한다.

자료를 넣는 것을 Push 라고 하고, 꺼내는 것을 Pop 이라고 한다.

꺼내지는 자료는 가장 최근에 Push한 자료부터 나오게 된다.

평소에 사용하는 ‘뒤로가기’를 생각하면 이해가 쉽다.

뒤로가기를 누르면 가장 최근에 방문한 사이트를 보여주는 것 말이다.

제일 마지막에 넣은 값이 먼저 나오는 것을 LIFO(Last in First out) 혹은 FILO(First in Last out)구조라고 한다.

Push

데이터를 스택에 넣는다.

step 1 : 스택이 가득 찼는지 확인

step 2 : 스택이 가득 차면 오류 발생하고 종료

step 3 : 스택이 가득 차지 않으면 Top 증가

step 4 : Top이 가리키는 스택 위치에 데이터 추가

Pop

데이터를 스택에서 꺼내온다. 즉, 제거한다.

step 1 : 스택이 비어 있는지 확인

step 2 : 스택이 비어 있으면 오류 발생하고 종료

step 3 : 스택이 비어 있지 않으면 Top이 가리키는 데이터 제거

step 4 : Top 값 감소

step 5 : 성공을 반환

스택의 사용

스택은 직전의 데이터를 빠르게 가져올 수 있고, 균형성 검사도 가능하다.

다음은 스택을 사용하는 사례이다.

• 자바 Stack 메모리
• 재귀 알고리즘
• Backtracking
• 웹 브라우저 방문 기록, 뒤로 가기
• 실행 취소 (undo)
• 역순 문자열 만들기
• 그래프의 깊이 우선 탐색 (DFS)

Overflow와 Underflow

Stack Overflow : 스택이 완전히 꽉 찼을 때

Stack Underflow : 스택이 완전히 비어 있을 때

Java class ‘ Stack ’

// Stack 선언
Stack<E> stack = new Stack<>();

// 값 추가
stack.push(추가할 값);

// 값 꺼내기 (삭제)
stack.pop();

// 전체 값 삭제 (초기화)
stack.clear(); 

// 가장 상단의 값 출력
stack.peek();

// 비어있는지 check (비어있으면 true)
stack.empty();

// 1이 있는지 check (있으면 true)
stack.contains(1);

스택 구현 방법

1. 배열 사용

• 장점 : 구현하기 쉽다.
• 단점 : 크기가 동적이 아니다. 런타임 시 필요에 따라 늘어나거나 줄어들지 않는다.

2. 연결 리스트 사용

• 장점 : 크기가 동적이다. 필요에 따라 크기가 확장되거나 축소될 수 있다.
• 단점 : 포인터를 위한 추가 메모리 공간이 필요하다.

시간 복잡도 (Time complexity)

• Insertion O(1)
• Deletion O(1)
• Search O(n)

삽입(push), 삭제(pop)는 항상 Top에서만 일어나기 때문에 O(1) 시간이 걸린다.

하지만 특정 데이터를 찾을 때에는 특정 데이터를 찾을 때까지 수행하기 때문에 O(n)이다.