원형 이중 연결 리스트란?
-
원형 이중 연결 리스트를 이루는 최소 단위는 노드이다.
하나의 노드는 3개의 데이터를 가진다.
-prev포인터: 이전 노드의 메모리 주소를 가리키는 포인터
-data: 실제 저장하는 값 (10, 20, 30 등)
-next포인터: 다음 노드의 메모리 주소를 가리키는 손 -
일반 이중 연결 리스트는 첫번째 노드의
prev는 갈 곳이 없고, 마지막 노드(40)의next도 갈 곳이 없다.
끊겨 있는 형태이기에 마지막 노드의next포인터는 아무것도 가리키지 않는null이 된다. -
원형 이중 연결 리스트는 시작과 끝이 연결되어 있고, 완벽한 원형 구조에서는 첫 번째 노드(10)의
prev포인터 역시 마지막 노드(40)를 가리키게 설계되는 것이 일반적이다.끝이 없는 회전 구조이기에 리스트의 처음과 끝을
O(1)시간 만에 오갈 수 있다.원형 큐나 플레이리스트의 ‘반복 재생’ 기능처럼 시작과 끝이 연결되어
순환해야 하는 로직 구현할 때 많이 사용된다.
벡터 맨 뒤에서 삽입/삭제가 O(1)인 이유
배열과 벡터의 물리적 특징은 메모리가 연속적으로 붙어 있다는 점이다.
중간 삽입(밀기)
-
방이 5개 있는 일렬로 된 책상(10, 20, 30, 40)이 있고,
맨 앞에(0번 인덱스)에 새 데이터 '5'를 넣으려고 한다. -
연속성을 유지해야 하므로, 기존에 있던 10, 20, 30, 40을 전부
한 칸씩 뒤로 밀어야만 맨 앞에 빈자리가 생긴다. -
당연히 데이터가 N개 있다면 최대 N번의 데이터 이동이 발생한다.
중간 삭제(땡기기)
- 맨 앞의 '5'를 삭제하면 그 자리가 비게 된다.
- 당연히 중간에 빈틈이 있으면 안되기에 데이터를 한 칸씩
앞으로 땡겨와야 하고, 마찬가지로 데이터 개수 만큼이니
o(n)이 된다.
벡터 맨 뒤에 삽입/삭제가 O(1)인 이유는 뭘까?
-
현재 마지막 데이터는 3번 인덱스의 '40'인데
여기에 push_back(50)을 수행하여 맨 뒤에 '50'을 넣으려고 한다. -
맨 앞에 넣을 때는 뒤의 데이터를 밀어야 했지만
맨 뒤인 4번 인덱스는 이미 비어있는 공간이다.
그 어떤 데이터도 뒤로 밀 필요 없이, 비어있는 곳에 값을 쓱 넣기만 하면 된다.
다른 데이터에 영향을 주지 않으므로 딱 한 번의 연산인O(1)이 나온다. -
삭제도 맨 뒤에 있는 데이터 하나 지우는 것이니
앞의 데이터들에 영향이 없기에O(1)이 나온다. -
정적 배열도 사실 위의 맨 뒤에서 일어나는 일련의 과정들에 대한
O(1)이
똑같긴 한데 정적 배열은 방 크기가 고정되어 있기에
방이 꽉 차면 정적 배열은 새로운 데이터를 추가하는 것 자체가 불가능하지만벡터는 내부적으로는 똑같은 배열을 사용하지만 방이 꽉 찼을 때
자동으로 더 큰 집으로 이사하는 기능이 내장되어 있다.
동적 배열의 확장이 일어날 때 얼마나 확장되는가?
-
Java (현재 가장 많이 쓰이는
java.util.ArrayList)- 기존 크기의
oldCapacity >> 1(절반을 더함)을 해서 정확히 1.5배씩 늘어난다.
- 기존 크기의
-
언어나 환경에 따라 달라지긴 하지만 평균적으로 1.5배 ~ 2배 정도 확장한다고 한다.
-
이유는 1칸씩 늘리면 당연히 너무 많은 대이동이 발생하기에 비효율적이고,
너무 크게 늘릴 경우에는 실질적으로 한 데이터를 13개 정도 밖에 안 쓰는데
배열 크기를 1,000개로 늘려버리면 남은 공간은 놀고 있는 것이고, 낭비된다. -
2배보다 1.5배가 더 좋다고 평가받는 이유
-
2배로 늘릴 때: 4 -> 8 -> 16 -> 32칸으로 늘어난다.
이때 이사를 가기 위해 새로 잡는 메모리 크기(32)는
이전에 버렸던 메모리들의 총합()보다 항상 크다.
그래서 컴퓨터가 이전에 썼던 메모리 자리를 다시 재사용하지 못하고,
계속 새로운 공간을 찾아 떠나야 한다. -
1.5배로 늘릴 때: 연속해서 이사를 가다 보면
이전에 버렸던 메모리 구역들을 합친 크기가
새로 필요한 메모리 크기보다 커지는 순간이 온다.
컴퓨터 시스템 입장에서는 "이전에 쓰다 버린 빈자리들 합치니까
이번에 이사 갈 집 크기 나오네! 여기 재사용하자"가 가능해져서
메모리를 훨씬 효율적으로 쓰게 된다.
-
AVL 트리
-
AVL 트리는 높이 균형에 집학하는 완벽주의자이며 좌우 높이를 칼같이 맞춘다.
-
왜 Balance Factor(BF)는 -1, 0, 1만 허용되는가?
-
이 속도를 유지하려면 트리가 양옆으로 예쁘게 퍼진 '삼각형' 모양 유지해야함
-
데이터가 계속 삽입/삭제되는 동적 상황에서 왼쪽과 오른쪽의 높이를 항상 '0(완벽한 똑같은 높이)'으로 맞추는 것은 불가능 하기에
최소한의 허용 오차: 1 -
BF = 0: 왼쪽과 오른쪽 서브트리의 높이가 완벽히 같은 상태 (가장 이상적)
-
BF = 1: 왼쪽이 오른쪽보다 딱 1층 더 높은 상태 (이 정도는 탐색 속도에 영향 없음)
-
BF = -1: 오른쪽이 왼쪽보다 딱 1층 더 높은 상태 (이 정도는 탐색 속도에 영향 없음)
-
밸런스 팩터(BF)라는 기준
원리: 각 노드마다 (왼쪽 서브트리 높이) - (오른쪽 서브트리 높이)를 계산한다.
이 값을 밸런스 팩터(BF)라고 한다.
규칙: BF는 반드시 -1, 0, 1 중 하나여야 한다.
이 범위를 벗어나는 순간(2 또는 -2가 되는 순간) 트리가 무너졌다고
판단하고 즉시 행동에 나선다.
해결책: 회전(Rotation)
균형이 깨지면 흐트러진 부분을 왼쪽이나 오른쪽으로 돌리는 회전 연산을 수행한다.
LL / RR (단일 회전): 한쪽으로 쏠린 노드들을 팽이처럼 한 번 슥 돌려서 균형을 맞춘다.
LR / RL (이중 회전): 지그재그 모양으로 꼬여서 쏠려 있는 경우, 한 번 돌려 일직선으로 만든 다음, 반대 방향으로 한 번 더 돌려 균형을 맞춘다.
AVL 트리는 책장이 한쪽으로 기울어지는 것을 절대 못 보는 결벽증 정리 정돈 전문가이다.
책이 한 권만 잘못 들어와도 그 즉시 전체 책장을 완벽한 대칭으로 다시 정리한다.
탐색 속도는 항상 최상이지만, 무언가를 넣거나 뺄 때마다 책장을
계속 재정리(회전)해야 하므로 수정 작업이 잦을 때는 피곤한 스타일이다.
레드-블랙 트리
- 레드-블랙 트리는 완벽한 높이 대칭을 맞추는 대신,
"노드에 색을 칠하자"라는 기발한 아이디어를 가져왔다.
"가장 긴 경로가 가장 짧은 경로의 2배만 넘지 않으면
탐색 성능()에 문제없다"는 실용주의자
5가지 엄격한 컬러 규칙
레드-블랙 트리는 아래 규칙만 지키면 대략적인 균형이 잡힌다는
수학적 증명을 기반으로 움직인다.
모든 노드는 레드(Red) 아니면 블랙(Black)이다.
루트 노드(가장 최상위 노드)는 무조건 블랙이다.
모든 리프 노드(끝에 달린 빈 노드, NIL)는 블랙이다.
레드 노드는 연속으로 올 수 없다. (레드 다음엔 무조건 블랙)
어떤 노드에서 출발하든, 리프 노드로 내려가는 길에 만나는 블랙 노드의 개수는 모두 같다.
해결책: 색칠하기(Re-coloring)와 회전
새로운 노드를 삽입할 때는 일단 레드로 넣는다.
이때 4번 규칙(레드 연속 금지)을 위반하는 상황이 오면 주변 노드의 색을 보고 판단한다.
삼촌 노드가 레드라면? 색상만 슥슥 다시 칠한다.
삼촌 노드가 블랙이라면? AVL 트리처럼 회전을 시킨다.
레드-블랙 트리는 "굳이 매번 칼같이 대칭을 맞출 필요가 있나?
가장 긴 경로가 가장 짧은 경로의 2배만 넘지 않으면 탐색하는 데 문제없어!"라고
생각하는 실용주의자이다.
규칙이 복잡해 보이지만, 색상만 바꾸는 가벼운 작업으로 균형을
유지할 때가 많아서 삽입/삭제 시 AVL 트리보다 훨씬 유연하고 빠르게 대처한다.
