자료구조란?
자료구조는 데이터를 효율적으로 저장, 관리, 처리하기 위한 다양한 형태입니다. 각각의 자료구조는 특정 문제를 해결하기 위해 설계되어있습니다.
상위 10개의 데이터 구조가 실제 세계에서 사용하는 모든 데이터 구조의 99%를 차지합니다.
Array, Stack, Queue, Set, Map, Heap, Tree, Graph
질문 정리
저는 Java를 주로 사용하므로 Java 위주로 정리했습니다.
선형, 비선형 자료구조에 대해 설명해 주세요.
선형 구조
선형 구조는 데이터가 연속적으로 나열된 자료구조입니다.
긱 요소는 그 전후에 단 하나의 요소만을 가질 수 있습니다. 이로 인해 데이터 요소들은 한 줄로 나열될 수 있어 직선의 관계를 가집니다.
예시로는 배열, 연결 리스트(Linked List), 스택, 큐, 덱 등이 있습니다.
비선형 구조
비선형 구조는 데이터가 일렬로 나열되지 않고 자료 순서나 관계가 복잡한 구조입니다.
하나의 데이터 요소가 둘 이상의 데이터 요소와 관계를 맺을 수 있습니다. 이로 인해 그래프나 트리 같은 복잡한 구조를 형성할 수 있습니다.
예시로는 그래프, 트리, 힙 등이 있습니다.
정리)
선형 구조
- 데이터가 연속적으로 나열된 자료구조이다
- 각 요소가 최대 두 개의 이웃(앞, 뒤)을 가진다. (직선 관계)
- 구현과 사용이 비교적 간단하다.
비선형 구조
- 데이터 요소가 비선형적인 자료구조이다
- 하나의 요소가 여러 개의 요소와 연결될 수 있다.
- 데이터가 계층적이거나 그래프 구조를 이룹니다.
Java의 Collection 프레임워크에 설명해 주세요
Java의 컬렉션 프레임워크는 데이터 집합을 저장하고 관리하기 위한 통합된 아케텍쳐를 제공합니다.
List, Map, Set 등 다양한 자료구조를 제공합니다.
객체지향적 설계를 통해 표준화되어 있으며, 재사용성이 높고 사용하기 편리하다는 장점이 있습니다.
Array에 대해 설명해 주세요.
Array는 데이터를 연속된 메모리 공간에 저장하는 자료구조 입니다.
고정된 크기를 가지며 데이터에 순서가 있어 0부터 시작하는 인덱스가 있습니다. 인덱스를 사용해 특정 요소에 빠르게 접근하고 조작할 수 있습니다.
하지만 배열은 크기가 고정되어 있어 동적으로 조정할 수 없다는 단점이 있습니다.
이러한 이유로 크기를 자유롭게 변경할 수 있는 ArrayList가 대안으로 사용되기도 합니다.
List, Map, Set의 설명과 차이점에 대해 말해주세요.
List, Map, Set은 컬렉션 프레임워크의 대표적인 자료구조 입니다..
List
- 중복 가능
- 순서가 있다.
Map
Key, Value 형태로 자료를 저장한다.
- Key의 중복을 허용하지 않는다.
- 순서가 없다.
Set
- 중복 불가능
- 순서가 없다.
List와 구현체에 대해 설명해 주세요.
리스트는 선형으로 데이터를 저장하는 자료 구조 중 하나로 객체들을 순서대로 저장하고 관리합니다.
java에서 사용하는 주요 구현체로는 ArrayList, LinkedList가 있습니다.
ArrayList
ArrayList 는 동적 배열을 기반으로 하는 리스트 구현체입니다.
인덱스를 통해 요소에 빠르게 접근할 수 있습니다. 시간 복잡도는 O(1)입니다.
무작위 접근이 많이 필요한 경우 유용합니다.
요소의 추가 및 삭제에는 O(n) 시간 복잡도가 발생할 수 있습니다. 리스트의 중간에 요소를 추가하거나 삭제할 경우, 나머지 요소들을 이동시켜야 하기 때문입니다.
내부적으로 배열 크기를 자동으로 조정합니다. 배열이 가득 차면, 더 큰 새 배열을 생성하고 기존 요소들을 복사합니다.
동적 배열 : 고정된 크기를 가진 일반벅인 배열과 달리 크기를 동적으로 조정할 수 있는 배열이다. 자동으로 크기를 축소하거나 확장하여 메모리를 효율적으로 사용할 수 있게 합니다.
단점으로 재할당 비용과 오버헤드가 있습니다.
재할당 비용 : 크기를 조정할 때 기존 데이터를 새로운 메모리 공간으로 복사할 때 성능 저하가 발생할 수 있다.
오버헤드 : 크기를 조정할 때 실제 사용하는 요소보다 더 많은 메모리 공간을 할당할 수 있어 메모리 사용이 비효율적일 수 있다.
LinkedList
LinkedList는 이중 연결 리스트를 기반으로 하는 리스트 구현체입니다.
각 요소는 이전 요소와 다음 요소에 대한 참조를 가집니다.
요소의 추가 및 삭제가 O(1) 시간 복잡도로 빠르게 이루어 집니다.
특정 인덱스의 요소에 접근하기 위해서는 처음부터 순차적으로 탐색하므로 O(n) 시간 복잡도가 발생합니다.
LinkedList 스택, 큐, 덱 등의 다양한 추상 데이터 타입을 구현하는데 사용됩니다.
이중 연결 리스트(Double Linked List) : 각 노드가 이전 노드와 다음 노드에 대한 두 개의 참조를 가진 연결 리스이다. 이중 연결 리스트는 양방향으로 순회할 수 있는 유연성을 제공한다.
단점으로 추가적인 메모리 필요와 구현이 단순 연결 리스트보다 복잡할 수 있다는 점이 있다.
Array와 ArrayList 차이점에 대해 말해주세요.
가장 큰 차이는 가변 여부입니다.
Array는 메모리 크기가 고정적인 반면 ArrayList는 메모리 크기가 가변적입니다.
Array는 초기화시 고정된 메모리를 가져 메모리 크기 변경에 따른 오버헤드가 없습니다. ArrayList는 추가, 삭제 시에 동적으로 변경하여 오버헤드가 발생할 수 있고 느립니다.
ArrayList는 느릴 수 있지만 편의성이 더 좋다는 장점이 있습니다.
Array : 고정된 크기의 단순한 연속 데이터를 다룰 때 사용
ArrayList : 데이터의 추가 및 삭제가 빈번하고 동적으로 크기를 조정할 때 사용
Array와 LinkedList 차이점에 대해 말해주세요.
Array는 인덱스 값을 알고 있으면 O(1)로 해당 요소로 접근할 수 있습니다. 즉 RandomAccess 무작위 접근이 가능해 속도가 빠릅니다.
LinkedList는 각각의 요소들이 자기의 양 옆에 요소들을 기억하고 있기 때문에 이 부분만 다른 값으로 바꿔주면 되서 삽입과 삭제를 O(1)로 해결할 수 있습니다.
LinkedList는 원하는 위치에 한 번에 접근할 수 없다는 단점이 있습니다. 원하는 위치를 찾기 위해 첫번째 원소부터 확인해야하기 때문입니다.
Array는 검색은 빠르지만 삽입, 삭제가 느립니다.
LinkedList는 삽입, 삭제가 빠르지만 검색이 느립니다.
LinkedList에 역순 출력 방법을 말해주세요.
스택을 이용하는 방법, 포인터를 이용하는 방법 2가지 방법이 있습니다.
스택을 이용하는 방법은 스택에 데이터를 넣어 출력합니다.
포인터를 이용하는 방법은 반복문을 이용해 다음 노드가 가리키는 노드를 이전 노드로 바꿔서 역순으로 방향을 바꿉니다.
Stack에 대해 설명해 주세요.
Stack
Stack은 후입선출(LIFO) 방식으로 나중에 들어간 원소가 먼저 나오는 구조입니다. (LIFO : Last In First Out)
선형 자료구조의 한 종류로 Array와 LinkedList로 구현할 수 있습니다.
스택 연산(push, pop)은 일반적으로 O(1) 시간복잡도를 가집니다.
스택의 예시로는 ‘웹 브라우저의 뒤로 가기’와 ‘Java의 Stack 메모리 영역’이 있습니다.
Java의 Stack 메모리 영역
지역변수와 매개변수 데이터 값이 저장되는 공간이며 메소드 호출시 메모리에 할당되고 종료되면 메모리가 헤제됩니다. LIFO 구조를 가집니다.
Java의 Stack은 Vector를 상속받아서 구현했다.
Queue에 대해 설명해 주세요.
Queue는 선입선출(FIFO) 방식으로 먼저 들어간 원소가 먼저 나오는 구조입니다. (FIFO : First In First Out)
선형 자료구조의 한 종류로 Array와 LinkedList로 구현할 수 있습니다.
큐의 기본 연산(Enqueue, Dequeue)는 일반적으로 O(1) 시간 복잡도를 가집니다.
Enqueue : 큐의 뒤쪽에 새로운 요소 추가
Dequeue : 큐의 앞쪽에 요소 제거하고 반환
큐는 프린터 작업 스케줄링, 운영 체제의 테스크 관리, 웹 서버 요청 처리(HTTP 요청), 데이터 스트림 처리, 이벤트 처리 시스템, BFS 알고리즘 등 다양한 분야에서 사용합니다.
OS 스케쥴러
자원의 할당과 회수를 하는 스케쥴러 역할을 큐가 할 수 있습니다.각 작업은 큐에 추가되고 스케줄러는 큐에서 작업을 하나씩 가져와 처리합니다. 이 정책을 선입선처리(First Come First Served)입니다.
원형 큐(Circular Queue)에 대해 설명해 주세요.
큐는 선입선출 형태의 자료구조로 한쪽 끝에는 삽입 연산이 반대쪽에는 삭제 연산이 이루어집니다.
큐의 문제점은 공간의 낭비입니다. 선형 큐에서는 데이터가 삽입되면 rear(뒤쪽) 포인터가 증가하고 데이터가 제거되면 front(앞쪽) 포인터가 증가합니다. 이 과정이 반복되면 front 포인터는 계속 뒤로 가게 되고 rear 포인터는 배열에 끝에 도달하여 더 이상 새로운 데이터를 삽입할 수 없게 됩니다. 이 상태를 큐의 포화 상태라 부릅니다. 이 때, 실제로 배열의 앞부분에 공간이 비어도 큐가 가득 찼다고 판단되어 더 이상 삽입 연산을 수행할 수 없습니다. 즉 큐의 앞부분에 남아 있는 빈 공간을 재사용할 수 없어 공간 낭비가 발생합니다.
이 단점을 극복하기 위한게 원형 큐 입니다. 원형큐는 선형 형태가 아닌 원 형태를 가집니다. 원형 큐는 배열의 끝과 시작이 연결된 것처럼 동작하여 front와 rear 포인터가 끝에 도달하며 다시 배열의 시작으로 돌아가 빈 공간을 재사용할 수 있게 합니다. 이로 인해 원형 큐는 선형 큐에 비해 메모리를 효율적으로 사용할 수 있다.
스택 2개로 큐 구현하는 법을 말해주세요
스택1에 데이터를 전부 집어넣는다.
스택1에 데이터를 꺼내서 스택2에 채워넣는다.
스택2에서 데이터를 하나씩 꺼낸다.
선입선출 구조로 큐가 구현된다.
큐 2개로 스택 구현하는 법을 말해주세요.
큐1에 데이터를 전부 집어넣는다.
큐1에 데이터를 하나만 남기고 큐2에 집어넣는다.
큐1에 남은 데이터 하나를 꺼낸다.
이 과정을 반복하면 스택이 구현된다.
Queue와 Deque 차이점을 말해주세요.
Queue는 FIFO로 먼저 추가된 요소가 먼저 제거됩니다.
데이터 추가는 뒤에만 되고 데이터 제거는 앞에만 됩니다.
반면 Deque는 양쪽 끝에서 요소를 추가하고 제거할 수 있는 일반화된 선형 자료구조입니다.
Deque는 FIFO인 Queue와 LIFO인 Stack 기능을 모두 제공합니다. Queue보다 더 다양한 연산을 지원합니다.
Queue 기능을 확장하여 다양한 상황에 사용될 수 있습니다.
Heap에 대해 설명해 주세요.
트리 기반의 자료구조 입니다. 데이터의 최대값과 최소값을 빠르게 찾을 수 있습니다.
힙의 주요 특징은 각 노드가 자식 노드보다 크거나 같거나 자식 노드보다 작거나 같은 순서를 유지하는 것 입니다. 크거나 같은 경우는 최대 힙(Max Heap), 작거나 같은 경우는 최소 힙(Min Heap)입니다. 힙은 일반적으로 배열을 사용하여 효율적으로 구현됩니다.
주요 특징
- 완전 이진 트리 : 모든 레벨이 노드로 완전히 채워져 있으며 마지막 레벨은 왼쪽에서 오른쪽 순서로 차례대로 채워집니다.
- 힙 속성 : 부모 노드의 값이 자식보다 항상 크거나, 작거나를 유지해서 최소힙, 최대힙을 구현해야 합니.
- 시간 복잡도 : 주요 연산인 삽입과 삭제의 시간복잡도는 일반적으로 O(log n)입니다. 삽입과 삭제할 때 재정렬하는 과정에서 O(log n)이 소요됩니다. 반면 조회 연산의 시간 복잡도는 O(1)입니다. 힙의 루트에 위치하기 때문입니다.
사용처
힙은 데이터의 최대값이나 최소값을 빠르게 찾아야하는 다양한 알고리즘과 시스템에서 사용합니다. 예를 들어, 우선 순위 큐, 힙 정렬 알고리즘, 그래프 알고리즘에서 최단 경로를 찾는데 사용합니다.
Priority Queue에 대해 설명해 주세요.
우선순위 큐로 들어간 순서에 상관없이 우선 순위가 높은 데이터를 먼저 꺼내는 자료구조입니다.
우선순위 큐의 구현 방식으로는 배열, 연결 리스트, 힙이 있습니다.
그 중 힙 방식이 최악의 경우에도 시간 복잡도 O(log N)을 보장해서 일반적으로 완전 이진트리 형태의 힙을 이용해 구현합니다.
시간 복잡도 표
조회 삽입, 삭제| 힙 | O(log n) | O(log n) |
| 배열(정렬 안된 상태) | O(1) | O(n) |
| 배열(정렬 된 상태) | O(n) | O(1) |
| 리스트(정렬 안된 상태) | O(1) | O(n) |
| 리스트(정렬 된 상태) | O(n) | O(1) |
java에서도 PriorityQueue 인터페이스는 주로 힙을 사용해 구현됩니다.
우선순위 큐에서는 데이터 추가, 삭제시 우선순위에 따라 정렬됩니다.
우선순위 큐는 작업 스케줄링, 다익스트라 알고리즘, 허프만 코딩, 이벤트 시뮬레이션 등에 사용됩니다.
작업 스케줄링 : 가장 중요한 작업부터 처리한다.
다익스트라 알고리즘 : 그래프에서 최단 경로를 찾는 알고리즘으로 가장 낮은 비용을 가진 노드를 우선적으로 방문한다.
허프만 코딩 : 데이터 압축에 사용되며 가장 낮은 빈도를 가진 노드들을 우선적으로 합치는 과정에 사용된다.
이벤트 시뮬레이션 : 시뮬레이션이 발생하는 이벤트들을 시간 순서대로 처리할 때 사용된다.
Hash Map에 대해 설명해 주세요.
해시맵은 Key-Value 형태로 데이터를 저장하는 자료구조입니다.
키는 유일하며 이를 통해 빠르게 조회, 삽입, 삭제 할 수 있습니다.
해시맵은 해시테이블을 내부적으로 사용하여 이러한 기능을 구현합니다.
해시함수
해시맵의 핵심은 해시함수입니다. 해시함수는 임의 크기의 데이터를 고정된 크기의 해시 값으로 변환합니다. 이 해시 값은 보통 배열의 인덱스로 사용되어 데이터의 저장 위치를 결정합니다.
충돌 해결
두 개 이상의 키가 같은 해시 값을 가질 때 충돌이 발생합니다.
충돌 해결에는 다양한 방법이 있습니다. 가장 일반적인 충돌 해결 기법은 체이닝과 오픈 어드레싱이 있습니다.
성능
해시맵의 조회, 삽입 삭제의 시간 복잡도는 모두 O(1) 입니다. 하지만 최악의 경우 (모든 키가 동일한 인덱스로 해시되는 경우) O(n)이 될 수도 있습니다. 효율적인 해시 함수와 충돌 해결 매커니즘은 해시 맵의 성능에 큰 영향을 끼칩니다.
사용처
해시맵은 데이터 조회가 필요한 많은 응용 프로그램에서 사용합니다. DB 인덱싱, 캐싱 등에 활용됩니다.
Hash 충돌에 대해 설명해 주세요.
키는 해시 함수를 통해 고정된 크기의 해시 값으로 반환합니다.
해시 충돌은 서로 다 키가 같은 해시 값을 가져 헤시 테이블 내에 같은 위치에 데이터를 저장하려고 할 때 발생합니다.
해시 테이블은 키를 해시 함수를 통해 해시 값으로 변환하고 이 해시 값으로 데이터를 저장할 배열의 인덱스를 결정하는 방식으로 작동합니다.
해시 충돌이 발생하는 주요 원인
- 해시 함수의 제한된 범위 : 해시 함수의 범위가 키의 값들의 집합보다 작은 경우 일어난다.
- 해시 함수의 특성 : 일부 해시 함수는 특정 유형의 데이터에 대해 충돌이 더 자주 발생할 수 있는 패턴을 가질 수 있습니다. 해시 함수가 데이터의 모든 부분을 고르게 고려하지 않거나 유사한 키가 유사한 해시 값을 생성하는 경우 충돌이 더 자주 발생합니다.
Hash 충돌 해결 방법에 대해 말해주세요.
체이닝 (Chanining)
각 인덱스에 데이터 구조(보통 연결 리스트)를 두어 여러 개의 키-값 쌍을 저장할 수 있도록 하는 방법입니다. 같은 해시 값을 가지는 키들이 하나의 리스트에 연결되어 저장됩니다.
작동 방식 : 해시 값이 같은 여러 개의 요소가 하나의 버킷에 저장될 때, 이 요소들은 해당 버킷의 연결 리스트에 차례대로 추가됩니다.
장점 : 간단하고 구현이 쉽습니다. 해시 테이블 크기에 비해 많은 수의 키-값 쌍을 저장할 수 있습니다.
단점 : 연결 리스트의 길이가 길어질수록 특정 키에 대한 조회 성능이 저하될 수 있습니다. 메모리 사용량이 늘어날 수 있습니다.
오픈 어드레싱(Open Addressing) 개방 주소법
오픈 어드레싱은 모든 요소를 해시 테이블 자체에 직접 저장하고, 충돌이 발생한 경우 다른 인덱스를 탐색하여 빈 슬롯을 찾는 방식입니다.
세부적으로 선형 조사법, 이차 조사법, 이중 해싱이 있습니다.
선형 조사법(Linear Probing)
충돌이 발생한 위치로부터 선형적으로 다음 위치를 조사하여 빈공간을 찾습니다. 선형 조사는 구현이 간단하고 쉽지만 클러스터링(데이터가 테이블 내에서 뭉치는 현상) 문제가 발생할 수 있습니다.
이차 조사법(Quadratic Probing)
충돌이 발생하면 충돌이 발생 위치로부터 이차식(1, 4, 9, 16…)을 사용하여 탐색 위치를 결정합니다. 이 방법은 선형 조사의 클러스터링 문제를 어느 정도 해결할 수 있습니다.
이중 해싱(Double Hashing)
두 개의 해시 함수를 사용하는 방법입니다. 첫 번째 해시 함수로 위치를 결정했을 때 충돌이 발생하면 두 번째 해시 함수를 사용하여 탐색 간격을 결정합니다. 클러스터링 문제를 더욱 효과적으로 줄일 수 있으며 탐색 간격이 일정하지 않아 해시 테이블 전체에 데이터가 고르게 분포될 가능성이 있습니다.
장점 : 메모리를 더 효율적으로 사용할 수 있습니다. 체이닝에 비해 추가적인 메모리 할당이 필요 없습니다.
단점 : 해시 테이블이 가득 차면 성능이 급격히 저하될 수 있습니다.
Hash Table에 대해 설명해 주세요.
해시 테이블은 Key, Value 형태로 데이터를 저장하는 자료구조입니다.
빠르게 데이터를 검색할 수 있습니다.
검색 속도가 빠른 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문입니다.
Key 값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있어 평균 O(1) 시간 복잡도로 데이터를 조회할 수 있습니다.
하지만, 인덱스 값이 충돌할 경우 Chanining에 연결된 리스트들까지 검색해야 하므로 O(n)까지 증가할 수 있습니다.
Hash Map와 Hash Table 차이점을 말해주세요.
동기화 지원 여부와 null 값 허용 여부의 차이가 있습니다.
Hash Map
- Thread-safe 하지 않다.
- Null 값을 허용한다.
Hash Table
- Thread-safe 하다
- Null 값을 허용하지 않는다.
그래프와 트리의 차이점을 말해주세요.
그래프와 트리는 모두 비선형 구조의 자료구조입니다.
노드와 노드를 잇는 간선으로 구성되어 있습니다.
그래프와 트리의 차이점으로는 순환, 방향, 계층이 있습니다.
그래프
- 순환을 이룰 수 있다.
- 방향이 단방향, 양방향 모두 가능하다.
- 루트 노드, 부모-자식이라는 개념이 없다.
트리
- 순환을 이룰 수 없다.
- 방향은 단방향이다.
- 루트 노드, 부모-자식이라는 개념이 존재한다. 즉 계층이 있다.
트리는 그래프의 한 일종이다.
Tree에 대해 설명해 주세요.
트리는 계층적 관계를 표현하는 자료구조 입니다.
트리는 비선형 자료구조의 한 종류입니다
노드와 노드를 연결하는 에지로 구성되어 있습니다.
노드는 데이터의 저장 단위이고 에지는 노드 간의 관계를 나타냅니다.
트리 구조는 계층적이며 루트 노드에서 시작하여 여러 레벨을 통해 데이터를 구성합니다.
트리의 특징
- 순환 구조가 없음
- N개의 노드는 N-1개의 엣지를 가짐
- 다양한 변형 : 이즌 트리, 균형 이진 트리, 이진 탐색 트리, B-트리 등이 있다.
깊이
루트 노드에서 해당 노드까지 도달하는데 사용되는 간선의 갯수입니다.
루트 노드의 깊이는 0 입니다.
BST (Binary Search Tree)와 Binary Tree 설명해 주세요.
이진 트리 (Binary Tree) 자식 노드가 최대 두 개로 구성된 트리입니다.
이진 탐색 트리 (Binary Search Tree) 이진 탐색과 연결 리스트를 결합한 구조이다.
이진 탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있다.
이진 탐색 트리는 왼쪽 트리의 모든 값은 반드시 부모 노드보다 작아야 하고, 오른쪽 트리의 값은 부모 노드보다 커야한다는 특징이 있다.
이진 탐색 트리의 탐색 연산은 트리의 높이에 영향을 받는다. 높이가 h일 때 탐색 시간 복잡도는 O(h)이다.
트리의 균형이 한쪽으로 치우쳐진 경우 최악의 경우가 되어 O(n)의 시간 복잡도를 가진다.
이 최악의 경우를 막기 위해 나온 것이 RBT (Red-Black Tree)와 AVL 트리입니다.
RBT (Red-Black Tree)에 대해 설명해 주세요.
RB Tree 특징
- 균형 이진 트리의 한 종류
- 노드가 추가적인 정보인 색을 가진다. 빨강, 검정
- 루트는 항상 검은색이다.
- 빨간 노드의 자식 노드들은 모두 검은색이다.
- 모든 리프 노드는 검은색이다. 실제데이터를 포함하지 않은 가상의 노드다.
- 어떤 노드로부터 시작해서 리프 노드에 이르기까지 각 경로에는 동일한 수의 검은 노드가 있어야 한다. 이를 검은 높이라고 한다.
RBT(Red-Black Tree)는 이진 탐색 트리를 기반으로 하는 트리 형식의 자료구조이다.
레드 블랙 트리는 이진 탐색 트리의 삽입, 삭제 과정에서 발생하는 문제점을 해결하기 위해 만들어졌다. (한 쪽으로 치우처지는 문제)
이진 탐색 트리를 기반으로 하므로 이진 탐색 트리의 특징을 가지고 있다.
노드의 자식 노드가 없을 경우 자식을 가리키는 포인터는 NIL 값을 저장합니다. 이러한 NIL들을 리프노드로 간주합니다.
모든 노드를 빨간색 혹은 검은색으로 칠하며 연결된 노드들은 색이 중복되지 않습니다.
AVL 트리에 대해 설명해 주세요.
AVL 트리는 자가 균형 이진 탐색 트리입니다.
왼쪽과 오른쪽 트리의 높이 차이를 1이하로 유지합니다.
높이 차이가 1보다 커지면 균형을 잡아서 차이를 줄입니다.
이 때, 균형을 잡는 방법은 불균형이 생긴 노드를 기준으로 회전을 합니다.
이진 탐색 트리, 포화 이진 트리, 완전 이진 트리를 설명해 주세요.
이진 탐색 트리는 검색에 특화되어 있는 트리이다. 이진 탐색이 항상 동작하도록 구현되어 탐색 속도를 극대화시켰다.
이진 탐색 트리는 부모 노드 보다 작은 값은 왼쪽에 배치하고 부모 노드 보다 큰 값은 오른쪽에 배치된 트리이다.
포화 이진 트리는 모든 이진 트리가 가득 차 있는 트리이다.
완전 이진 트리는 완전한 형태를 가진 이진 트리이다.
마지막 레벨을 제외한 모든 레벨에 노드가 완전히 채워져 있어야 한다.
마지막 레벨은 가득 차 있지 않으면 왼쪽부터 차례대로 삽입해야 한다.
참조 사이트
https://towardsdatascience.com/8-common-data-structures-every-programmer-must-know-171acf6a1a42
https://dev-coco.tistory.com/159
