1. Data structures augmentation 코딩
● Rank 구현 (1)
- Rank 함수
숫자와 목록을 만들고 그에 해당하는 오름차순, 내림차순을 결정하여 목록에 해당하는 순위값을 자동으로 출력하는 함수
위의 이미지 처럼 값들이 쭉 입력된 목록이 있고 크기 순으로 rank(순위)를 매기는 목록이 있음.
- Rank(순위) 알고리즘 or 등수 알고리즘
주어진 자료 중에서 순위(등수)를 구할 때 사용함.
모든 점수는 처음에는 1등으로 설정한 후 해당 점수보다 큰 점수가 나타날 때마다
등수를 1씩 증가시켜 순위를 낮추는 것(등수가 밀리는 것)이 핵심 로직.
- C#을 통한 Rank 알고리즘 구현
using System;
using System.Linq;
class RankAlgorithm
{
static void Main()
{
//① 입력
int[] scores = { 90, 87, 100, 95, 80 }; //등수: 3, 4, 1, 2, 5
int[] rankings = Enumerable.Repeat(1, 5).ToArray(); //모두 1로 초기화
//② 처리: RANK
for (int i = 0; i < scores.Length; i++)
{
rankings[i] = 1; //1등으로 초기화, 순위 배열을 매 회전마다 1등으로 초기화
for (int j = 0; j < scores.Length; j++)
{
if (scores[i] < scores[j]) //현재(i)와 나머지(j) 비교
{
rankings[i]++; //RANK: 나보다 큰 점수가 나오면 순위 1증가
}
}
}
//③ 출력
for (int i = 0; i < scores.Length; i++)
{
Console.WriteLine($"{scores[i],3}점 : {rankings[i]}등");
}
}
}(출처: https://thebook.io/006890/part03/ch31/08/ )
● Rank 구현 (2)
- Rank(r, 순위):
해당 원소 앞의 개수를 특정하는 수단으로, 원소에 접근해 접근, 삽입, 삭제 등을 할 수 있음
리스트 형태로 구현됨, 원소들의 순서 집단을 저장하기 위한 기초적이고 일반적인 데이터 구조
- 메소드 개요
일반 메소드
boolean isEmpty()
integer size()
iterator elements()
접근 메소드
element get(r)
갱신 메소드
element set(r, e)
add(r, e)
addFirst(e)
addLast(e)
element remove(r)
element removeFirst()
element removeLast()
- 구현 방법에 따른 시간복잡도
- 1차원 배열을 통한 구현
< 기본 구성요소 >
→ 배열 메모리 크기 N: 현재 최대로 담을 수 있는 원소 개수
→ 리스트 크기 n: 저장된 원소 개수
→ 순위 r: 0부터 시작
< 초기화: O(1) >
→ init 함수를 통해 숫자를 입력받은 만큼 동적 메모리를 할당해 저장
Alg init()
input array V, integer N, integer n
output an empty array V of size N
1. n ← 0
2. return// 각 원소가 문자(character)를 담는다고 가정
#include<stdio.h>
void init(char** V, int N, int* n){
*V = (char*)malloc(sizeof(char)*N);
*n = 0;
}
int main(){
char* V;
int N, n;
scanf("%d", &N);
init(&V, N, &n);
return 0;
}
< 순회 : O(n) >
→ 배열의 각 원소에 접근하기 위해서는 for문을 사용해 인덱스 0부터 n-1까지 접근한다.
→ 이때 시간복잡도는 O(n)
Alg traverse()
input array V, integer N, integer n
output none
1. for r←0 to n-1
visit(V[r])
2. return// 각 원소가 문자(character)를 담는다고 가정
// traverse의 결과가 보이도록 print기능으로 구현
void print(char *V, int n) {
for(int r=0; r<n-1; r++){
printf("%d ", V[r]);
}
printf("\n");
}
< 삽입 >
→ 삽입할 값, 배열, 배열 크기, rank 값, (삽입할 인덱스 위치) 등을 함수 인자로 입력받는다.
→ rank 값이 0보다 작거나 배열 크기 n보다 크면 안되므로 예외 처리를 한다.
→ 삽입할 인덱스보다 인덱스가 큰 값들은 기존의 배열에서 한 칸씩 뒤로 밀어 저장한다.
→ 삽입할 인덱스에 삽입할 값을 저장한다.
→ 배열 크기 n의 값을 하나 증가시킨다.
→ 함수 각각의 시간복잡도는 add-O(n), addFirst-O(n), addLast-O(1)
→ addLast 함수는 제일 끝에 삽입할 값만 넣으면 돼서 O(1)이지만
add 함수는 최악의 경우 배열의 모든 값을 뒤로 미루는 계산을 해야하고
addFirst 함수는 항상 배열의 모든 값을 한 칸씩 뒤로 밀어야 하므로 O(n)의 시간복잡도를
갖는다.
Alg add(r, e)
input array V, element e, rank r, integer N, integer n,
output none
1. if(r<0 || r>n)
invalidRankException()
2. if(n==N)
fullListException()
3. for i←n-1 downto r
V[i+1] ← V[i]
4. V[r] ← e
5. n ← n+1
6. returnchar add(char *V, char e, int r, int N, int *n) {
// 예외처리
if( (r<0)||(r>(*n)) ){
printf("invalid rank exception\n");
return e;
}
if(*n==N){
printf("full list exception\n");
return e;
}
// 삽입 수행
for(int i=*n; i>r; i--)
V[i] = V[i-1];
V[r] = e;
*n += 1;
return e;
}
< 삭제 >
→ 배열, 배열 크기, rank 값 등을 함수 인자로 입력받는다.
→ rank 값이 0보다 작거나 배열 크기 n보다 같거나 크면 안되므로 예외 처리를 한다.
→ 삭제할 인덱스에 있는 값을 다른 곳에 저장해두고 마지막에 이 값을 return하며 함수를
종료한다.
→ 삭제할 인덱스보다 인덱스가 큰 값들은 기존의 배열에서 한 칸씩 앞으로 당겨 저장한다.
→ 배열 크기 n의 값을 하나 감소시킨다.
→ 함수 각각의 시간복잡도는 remove-O(n), removeFirst-O(n), removeLast-O(1)
→ removeLast 함수는 제일 끝에 삭제할 값만 삭제하면 돼서 O(1)이지만
remove 함수는 최악의 경우 배열의 모든 값을 앞으로 당기는 계산을 해야하고
removeFirst 함수는 항상 배열의 모든 값을 한 칸씩 앞으로 당겨야 하므로
O(n)의 시간복잡도를 갖는다.
Alg remove(r)
input array V, rank r, integer N, integer n
output element e
1. if(r<0 || r>n-1)
invalidRankException()
2. for i←r to n-2
V[i] ← V[i+1]
3. n ← n-1
returnchar Remove(char* V, int r, int* n) {
if( (r<0)||(r>(*n)-1) ){
printf("invalid rank exception\n");
return '0';
}
char e = V[r];
for(int i=r; i<(*n)-1; i++)
V[i] = V[i+1];
*n -= 1;
return e;
}
- 이외에도...
원형 배열, 단일 연결리스트, 이중 연결리스트를 사용한 구현 방법 등이 있음
● AVL tree 구현
- 균형 이진 탐색 트리(Balanced BST) 개념
→ 이진 탐색 트리에서 탐색(Search), 삽입(Insert), 삭제(Delete) 등의 연산은
트리의 높이 ℎ에 비례하는 시간 즉, 𝑂(ℎ) 시간이 소요된다.
→ 이진 탐색 트리의 높이를 𝑂(log 𝑛)으로 제한할 수있으면,
위의 연산 모두 𝑂(log 𝑛) 시간에 수행된다.
→ 높이가 𝑂(log 𝑛)인 이진 탐색 트리를 "균형 이진 탐색 트리"라고 한다.
→ 균형 이진 탐색 트리에는 AVL 트리, 레드-블랙 트리 등이 있다.
- AVL tree 개념
→ AVL 트리는 스스로 균형을 잡는 이진 탐색 트리
→ 트리의 높이가 h일 때 이진 탐색 트리의 시간 복잡도는 O(h)
→ 한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아져 시간 복잡도가 커지기 때문에
이를 방지하고자 높이 균형을 유지하는 AVL 트리를 사용하게 된다.
- AVL tree 특징
→ AVL 트리는 이진 탐색 트리의 속성을 가진다.
→ 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.
어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아
높이 차이를 줄인다.
→ AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의
시간 복잡도는 O(logN) 이다.
- Balance Factor(BF)
→ 외쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값
Balance Factor (k) = height (left(k)) - height(right(k))
→ BF가 1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한단계 높다는 것을 의미함.
→ BF가 0이면 왼쪽 서브트리와 오른쪽 서브트리의 높이가 같다는 것을 의미함.
→ BF가 -1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한단계 낮다는 것을 의미함.
→ EX) AVL 트리의 예: BF가 -1과 1 사이에 있음을 알 수 있음
- AVL tree 구현
→ 회전 (rotation)
AVL 트리에서 이진 탐색 트리의 삽입 알고리즘을 이용하여 노드를 삽입하면 균형 인자가
2 혹은 -2 가 되는 노드가 생길 수 있다.
이 경우 AVL 트리를 유지하도록 보정 작업이 필요 한데, LL, LR, RL, RR 등 네 종류의 회전
이 있다.
1. LL(Left Left) case
y는 z의 왼쪽 자식 노드이고, x는 y의 왼쪽 자식 노드인 경우 right rotation을 수행하여
균형을 맞춘다.
<Right rotation 수행 과정>
1) y노드의 오른쪽 자식 노드를 z노드로 변경
2) z노드 왼쪽 자식 노드를 y노드 오른쪽 서브트리(T2)로 변경
3) y는 새로운 루트 노드가 됨
<right rotation 코드 구현>
struct node *rightRotate (struct node *z) {
struct node *y = z->left;
struct node *T2 = y->right;
// y의 오른쪽 자식 노드를 z로 지정
y->right = z;
// z의 왼쪽 자식 노드를 T2로 지정
z->left = T2;
// 새로운 루트 노드 y를 반환
return y;
}
2. RR(Right Right) case
y는 z의 오른쪽 자식 노드이고, x는 y의 오른쪽 자식 노드인 경우 left rotation을 수행하여
균형을 맞춘다.
<Left rotation 수행 과정>
1) y노드의 왼쪽 자식 노드를 z노드로 변경
2) z노드 오른쪽 자식 노드를 y노드 왼쪽 서브트리(T2)로 변경
3)y는 새로운 루트 노드가 됨
<left rotation 코드 구현>
struct node *lefttRotate (struct node *z) {
struct node *y = z->right;
struct node *T2 = y->left;
// y의 왼쪽 자식 노드를 z로 지정
y->left = z;
// z의 오른쪽 자식 노드를 T2로 지정
z->right = T2;
// 새로운 루트 노드 y를 반환
return y;
}
3. LR(Left Right) case
y는 z의 왼쪽 자식 노드이고, x는 y의 오른쪽 자식 노드인 경우 left , right 순으로 총 두 번의 rotation을 수행하여 균형을 맞춘다.
<LR 코드 구현>
y = z->left;
y = leftRotate(y);
z = rightRotate(z);
4. RL(Right Left) case
y는 z의 오른쪽 자식 노드이고, x는 y의 왼쪽 자식 노드인 경우, right, left 순으로 총 두번의 rotation을 수행하여 균형을 맞춘다.
<RL 코드 구현>
y = z->right;
y = rightRotate(y);
z = leftRotate(z);
- AVL tree를 구현한 전체 코드
→ 이진 트리가 주어졌을 때 이를 AVL tree로 바꿔주는 코드
→ 노드 생성하는 생성자, left rotation 함수, right rotation 함수, BF 값을 가져오는 함수,
트리의 높이 균형을 유지하는 (트리의 상황에 맞게 rotation함수를 실행시키는) 함수,
노드를 입력받아 생성자를 실행해 노드를 생성하고 트리에 노드를 하나씩 삽입한 후
삽입이 모두 끝나면 rotation 함수를 실행시키는 함수가 구현되어 있다.
struct node {
int key;
struct node *left, *right;
int height;
};
int max(int a, int b) {
return (a > b)? a : b;
}
struct node* newNode(int key) {
struct node *temp = (struct *node)malloc(sizeof(struct node));
temp->data = key;
temp->left = NULL;
temp->right = NULL;
temp->height = 1;
return temp;
}
struct node *lefttRotate (struct node *z) {
struct node *y = z->right;
struct node *T2 = y->left;
// left 회전 수행
y->left = z;
z->right = T2;
// 노드 높이 갱신
z->height = 1 + max(z->left->height, z->right->height);
y->height = 1 + max(y->left->height, y->right->height);
// 새로운 루트 노드 y를 반환
return y;
}
struct node *rightRotate (struct node *z) {
struct node *y = z->left;
struct node *T2 = y->right;
// right 회전 수행
y->right = z;
z->left = T2;
// 노드 높이 갱신
z->height = 1 + max(z->left->height, z->right->height);
y->height = 1 + max(y->left->height, y->right->height);
// 새로운 루트 노드 y를 반환
return y;
}
// BF(BalanceFactor)값을 가져오는 함수.
int getBalanceFactor(struct node *n) {
if (n == NULL)
return 0;
return n->left->height - n->right->height;
}
// 트리의 높이 균형을 유지하는 함수.
// 4가지 케이스를 가지고 rotate를 수행함.
struct node* rebalance(struct node* root) {
int bFactor = getBalanceFactor(root);
// LL Case
if (bFactor > 1 && key < node->left->key)
return rightRotate(root);
// RR Case
if (bFactor < -1 && key > node->right->key)
return leftRotate(root);
// LR Case
if (bFactor > 1 && key > node->left->key){
root->left = leftRotate(root->left);
return rightRotate(root);
}
// RL Case
if (bFactor < -1 && key < node->right->key){
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// 삽입 함수.
struct node* insert(struct node* root, int key) {
// 삽입 수행
if (root == NULL)
return newNode(key);
if (key > root->data)
root->right = insert(root->right, key);
else if (key < root->data)
root->left = insert(root->left, key);
else
return root;
// 노드 높이 갱신
root->height = 1 + max(node->left->height, node->right->height);
// 노드 균형 유지
root = rebalance(root);
return root;
}
2. AVL tree 정의 등 강의 내용 정리
- AVL 트리
→ 모든 노드에 대해 왼쪽 및 오른쪽 하위 트리의 높이 차이가 1보다 클 수 없는
자체 균형 이진 검색 트리(BST)
위의 트리는 모든 노드에 대한 왼쪽 및 오른쪽 하위 트리의 높이 차이가 1보다 작거나 같기 때문에 AVL 임.
위의 트리는 8과 12에 대한 왼쪽 및 오른쪽 하위 트리의 높이 차이가 1보다 크므로 AVL이 아님.
- 왜 AVL tree인가?
→ 대부분의 BST 작업(예: 검색, 최대, 최소, 삽입, 삭제 등)은 O(h) 시간이 소요되며
여기서 h는 BST의 높이.
이러한 연산의 비용은 편향된 이진 트리의 경우 O(n)이 될 수 있다.
모든 삽입 및 삭제 후에 트리 높이가 O(log(n))로 유지되도록 하면
이러한 모든 작업에 대해 O(log(n))의 상한을 보장할 수 있다.
AVL 트리의 높이는 항상 O(log(n))입니다. (여기서 n은 트리의 노드 수)
- AVL 트리에 삽입
→ 모든 삽입 후에 주어진 트리가 AVL을 유지하도록 하려면 일부 재조정을 수행하기 위해
표준 BST 삽입 작업을 보강해야 함
다음은 BST 속성을 위반하지 않고 BST의 균형을 맞추기 위해 수행할 수 있는 두 가지 기본 작업이다.
(keys(left) < key(root) < keys(right)).
- Left Rotation
- Right Rotation
T1, T2 and T3 are subtrees of the tree, rooted with y (on the left side) or x (on the right side)
y x
/ \ Right Rotation / \
x T3 - - - - - - - > T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
Keys in both of the above trees follow the following order
keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.
- 삽입을 위해 따라야 할 단계
새로 삽입된 노드를 w로 설정
w에 대한 표준 BST 삽입을 수행
w에서 시작하여 위로 이동하여 첫 번째 불균형 노드를 찾음
z를 첫 번째 불균형 노드, y를 w에서 z로 가는 경로에 있는 z의 자식, x를 w에서 z로 가는 경로에 있는 z의 손자라고 가정
z를 기반으로 하는 하위 트리에서 적절한 회전을 수행하여 트리의 균형을 재조정
x, y, z가 4가지 방식으로 배열될 수 있으므로 처리해야 하는 4가지 가능한 경우가 있을 수 있음.
다음은 가능한 4가지 경우의 수입니다.
1) y는 z의 왼쪽 자식이고 x는 y의 왼쪽 자식일 경우 (Left Left Case)
2) y는 z의 왼쪽 자식이고 x는 y의 오른쪽 자식일 경우 (Left Right Case)
3) y는 z의 오른쪽 자식이고 x는 y의 오른쪽 자식일 경우 (Right Right Case)
4) y는 z의 오른쪽 자식이고 x는 y의 왼쪽 자식일 경우 (Right Left Case)
다음은 위에서 언급한 4가지 경우에 수행되는 작업입니다.
모든 경우에 우리는 z로 뿌리를 둔 하위 트리의 균형을 재조정하기만 하면 되며 z로 뿌리를 둔 하위 트리의 높이(적절한 회전 후)가 삽입 전과 같아짐에 따라 완전한 트리가 균형을 이루게 됩니다.
1. Left Left Case
T1, T2, T3 and T4 are subtrees.
z y
/ \ / \
y T4 Right Rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T22. Left Right Case
z z x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T23. Right Right Case
z y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T44. Right Left Case
z z x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
- 노드 삽입 코드 구현
노드 삽입 코드 구현아이디어는 재귀적 BST 삽입을 사용하는 것이다.
삽입 후 상향식 방식으로 모든 조상에 대한 포인터를 하나씩 얻는다.
따라서 위로 이동하기 위해 부모 포인터가 필요하지 않다.
재귀 코드 자체는 위로 이동하여 새로 삽입된 노드의 모든 조상을 방문한다.
<아이디어를 구현하려면 아래에 언급된 단계를 따르기>
일반 BST 삽입을 수행한다.
현재 노드는 새로 삽입된 노드의 상위 노드 중 하나여야 한다. 현재 노드의 높이를 업데이트한다.
현재 노드의 균형 요소(왼쪽 하위 트리 높이 – 오른쪽 하위 트리 높이)를 가져온다.
균형 요소가 1보다 크면 현재 노드는 불균형 상태이고 우리는 왼쪽 왼쪽 케이스 또는 왼쪽 오른쪽 케이스에 있다.
왼쪽 대소문자인지 확인하려면 새로 삽입된 키를 왼쪽 하위 트리 루트의 키와 비교한다.
균형 요소가 -1보다 작으면 현재 노드가 불균형 상태이고 오른쪽 또는 오른쪽-왼쪽의 경우이다.
Right Right 케이스인지 확인하려면 새로 삽입된 키와 오른쪽 하위 트리 루트의 키를 비교한다.
다음은 위의 접근 방식을 구현한 것입니다.
|
// C++ program to insert a node in AVL tree
#include<bits/stdc++.h>
using namespace std;
// An AVL tree node
class Node
{
public:
int key;
Node *left;
Node *right;
int height;
};
// A utility function to get maximum
// of two integers
int max(int a, int b);
// A utility function to get the
// height of the tree
int height(Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
// A utility function to get maximum
// of two integers
int max(int a, int b)
{
return (a > b)? a : b;
}
/* Helper function that allocates a
new node with the given key and
NULL left and right pointers. */
Node* newNode(int key)
{
Node* node = new Node();
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially
// added at leaf
return(node);
}
// A utility function to right
// rotate subtree rooted with y
// See the diagram given above.
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left),
height(y->right)) + 1;
x->height = max(height(x->left),
height(x->right)) + 1;
// Return new root
return x;
}
// A utility function to left
// rotate subtree rooted with x
// See the diagram given above.
Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left),
height(x->right)) + 1;
y->height = max(height(y->left),
height(y->right)) + 1;
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// Recursive function to insert a key
// in the subtree rooted with node and
// returns the new root of the subtree.
Node* insert(Node* node, int key)
{
/* 1. Perform the normal BST insertion */
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys are not allowed in BST
return node;
/* 2. Update height of this ancestor node */
node->height = 1 + max(height(node->left),
height(node->right));
/* 3. Get the balance factor of this ancestor
node to check whether this node became
unbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced, then
// there are 4 cases
// Left Left Case
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
// A utility function to print preorder
// traversal of the tree.
// The function also prints height
// of every node
void preOrder(Node *root)
{
if(root != NULL)
{
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}
// Driver Code
int main()
{
Node *root = NULL;
/* Constructing tree given in
the above figure */
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
/* The constructed AVL Tree would be
30
/ \
20 40
/ \ \
10 25 50
*/
cout << "Preorder traversal of the "
"constructed AVL tree is \n";
preOrder(root);
return 0;
}
// This code is contributed by
// rathbhupendra
|
Output:
Preorder traversal of the constructed AVL tree is
30 20 10 25 40 50
- 시간 복잡도 분석
→ 시간 복잡도: O(log(n)), 삽입용
→ 보조 공간: O(1)
회전 작업(왼쪽 및 오른쪽 회전)은 몇 개의 포인터만 변경되기 때문에 일정한 시간이 걸린다.
높이를 업데이트하고 균형 요소를 얻는 데에도 일정한 시간이 걸린다.
따라서 AVL 인서트의 시간 복잡도는 BST 인서트와 동일하게 유지되며, 여기서 h는 트리의 높이이다.
AVL 트리가 균형을 이루기 때문에 높이는 O(Logn)
따라서 AVL 삽입의 시간 복잡도는 O(Logn)
- 레드 블랙 트리와 비교
AVL 트리 및 Red Black과 같은 다른 자체 균형 검색 트리는 모든 기본 작업을 O(log n) 시간에 완료하는 데 유용.
AVL 트리는 Red-Black Tree에 비해 균형이 더 잘 잡혀 있지만 삽입 및 삭제 중에 더 많은 회전이 발생할 수 있음.
따라서 애플리케이션에 빈번한 삽입 및 삭제가 포함되는 경우 Red Black 트리가 선호되어야 함.
그리고 삽입과 삭제가 덜 빈번하고 검색이 더 빈번한 작업이라면 AVL 트리가 레드 블랙 트리보다 선호되어야 함.
- 삭제를 위해 따라야 할 단계
주어진 트리가 모든 삭제 후에 AVL을 유지하도록 하려면 일부 재조정을 수행하기 위해 표준 BST 삭제 작업을 보강해야 함.
다음은 BST 속성을 위반하지 않고 BST를 재조정하기 위해 수행할 수 있는 두 가지 기본 작업이다.
keys(left) < key(root) < keys(right))
- Left Rotation
- Right Rotation
T1, T2 and T3 are subtrees of the tree rooted with y (on left side)
or x (on right side)
y x
/ \ Right Rotation / \
x T3 – - – - – - – > T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
Keys in both of the above trees follow the following order
keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.
삭제할 노드는 w로 설정
w에 대한 표준 BST 삭제를 수행
w에서 시작하여 위로 이동하여 첫 번째 불균형 노드를 찾기
z를 첫 번째 불균형 노드, y를 z의 더 큰 높이 자식, x를 y의 더 큰 높이 자식이라고 가정하기
(x 및 y의 정의는 삽입과 다름)
z를 기반으로 하는 하위 트리에서 적절한 회전을 수행하여 트리의 균형을 재조정함.
x, y, z가 4가지 방식으로 배열될 수 있으므로 처리해야 하는 4가지 가능한 경우가 있을 수 있음.
다음은 가능한 4가지 경우의 수입니다.
1) y는 z의 왼쪽 자식이고 x는 y의 왼쪽 자식일 경우 (Left Left Case)
2) y는 z의 왼쪽 자식이고 x는 y의 오른쪽 자식일 경우 (Left Right Case)
3) y는 z의 오른쪽 자식이고 x는 y의 오른쪽 자식일 경우 (Right Right Case)
4) y는 z의 오른쪽 자식이고 x는 y의 왼쪽 자식일 경우 (Right Left Case)
삽입과 마찬가지로 위에서 언급한 4가지 경우에 수행해야 하는 작업은 다음과 같다.
삽입과 달리 노드 z를 수정해도 전체 AVL 트리가 수정되지 않음
z를 수정한 후 z의 조상도 수정해야 할 수 있음
a) Left Left Case
T1, T2, T3 and T4 are subtrees.
z y
/ \ / \
y T4 Right Rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2b) Left Right Case
z z x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2c) Right Right Case
z y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4d) Right Left Case
z z x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z y
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
위 그림들은 값이 32인 노드가 삭제되는 과정이다.
32를 삭제한 후 위로 이동하여 44인 첫 번째 불균형 노드를 찾음
이를 z로 표시하고, 더 높은 높이의 자식을 y로 62로, y의 더 높은 높이의 자식을 x로 표시.
(둘 다 78 또는 50일 수 있음).
같은 높이의 노드인 78을 고려했음.
이제 Right Right 이므로 left rotation 을 수행
- 노드 삭제 코드 C++ 구현
다음은 AVL 트리 삭제를 위한 C 구현이다.
다음 C 구현은 재귀적 BST 삭제를 기본으로 사용한다.
재귀적 BST 삭제에서 삭제 후 상향식으로 모든 조상에 대한 포인터를 하나씩 얻는다.
따라서 위로 이동하기 위해 부모 포인터가 필요하지 않다.
재귀 코드 자체는 위로 이동하여 삭제된 노드의 모든 조상을 방문한다.
일반 BST 삭제를 수행한다.
현재 노드는 삭제된 노드의 상위 노드 중 하나여야 한다.
현재 노드의 높이를 업데이트함.
현재 노드의 균형 요소(왼쪽 하위 트리 높이 – 오른쪽 하위 트리 높이)를 가져옴.
균형 요소가 1보다 크면 현재 노드가 불균형 상태이며 Left Left case 또는 Left Right case에 있다.
Left Left case인지 Left Right case인지 확인하려면 왼쪽 하위 트리의 균형 요소를 가져옴
왼쪽 하위 트리의 균형 요소가 0보다 크거나 같으면 Left Left case이고, 그렇지 않으면 Left Right case.
균형 요소가 -1보다 작으면 현재 노드가 불균형 상태이고 Right Right case 또는 Right Left case 임.
Right Right case인지 Right Left case인지 확인하려면 오른쪽 하위 트리의 균형 요소를 가져옴.
오른쪽 하위 트리의 균형 요소가 0보다 작거나 같으면 Right Right case이고 그렇지 않으면 Right Left case.
|
// C++ program to delete a node from AVL Tree
#include<bits/stdc++.h>
using namespace std;
// An AVL tree node
class Node
{
public:
int key;
Node *left;
Node *right;
int height;
};
// A utility function to get maximum
// of two integers
int max(int a, int b);
// A utility function to get height
// of the tree
int height(Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
// A utility function to get maximum
// of two integers
int max(int a, int b)
{
return (a > b)? a : b;
}
/* Helper function that allocates a
new node with the given key and
NULL left and right pointers. */
Node* newNode(int key)
{
Node* node = new Node();
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially
// added at leaf
return(node);
}
// A utility function to right
// rotate subtree rooted with y
// See the diagram given above.
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left),
height(y->right)) + 1;
x->height = max(height(x->left),
height(x->right)) + 1;
// Return new root
return x;
}
// A utility function to left
// rotate subtree rooted with x
// See the diagram given above.
Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left),
height(x->right)) + 1;
y->height = max(height(y->left),
height(y->right)) + 1;
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(Node *N)
{
if (N == NULL)
return 0;
return height(N->left) -
height(N->right);
}
Node* insert(Node* node, int key)
{
/* 1. Perform the normal BST rotation */
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys not allowed
return node;
/* 2. Update height of this ancestor node */
node->height = 1 + max(height(node->left),
height(node->right));
/* 3. Get the balance factor of this
ancestor node to check whether
this node became unbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced,
// then there are 4 cases
// Left Left Case
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
/* Given a non-empty binary search tree,
return the node with minimum key value
found in that tree. Note that the entire
tree does not need to be searched. */
Node * minValueNode(Node* node)
{
Node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;
return current;
}
// Recursive function to delete a node
// with given key from subtree with
// given root. It returns root of the
// modified subtree.
Node* deleteNode(Node* root, int key)
{
// STEP 1: PERFORM STANDARD BST DELETE
if (root == NULL)
return root;
// If the key to be deleted is smaller
// than the root's key, then it lies
// in left subtree
if ( key < root->key )
root->left = deleteNode(root->left, key);
// If the key to be deleted is greater
// than the root's key, then it lies
// in right subtree
else if( key > root->key )
root->right = deleteNode(root->right, key);
// if key is same as root's key, then
// This is the node to be deleted
else
{
// node with only one child or no child
if( (root->left == NULL) ||
(root->right == NULL) )
{
Node *temp = root->left ?
root->left :
root->right;
// No child case
if (temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
*root = *temp; // Copy the contents of
// the non-empty child
free(temp);
}
else
{
// node with two children: Get the inorder
// successor (smallest in the right subtree)
Node* temp = minValueNode(root->right);
// Copy the inorder successor's
// data to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right,
temp->key);
}
}
// If the tree had only one node
// then return
if (root == NULL)
return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root->height = 1 + max(height(root->left),
height(root->right));
// STEP 3: GET THE BALANCE FACTOR OF
// THIS NODE (to check whether this
// node became unbalanced)
int balance = getBalance(root);
// If this node becomes unbalanced,
// then there are 4 cases
// Left Left Case
if (balance > 1 &&
getBalance(root->left) >= 0)
return rightRotate(root);
// Left Right Case
if (balance > 1 &&
getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}
// Right Right Case
if (balance < -1 &&
getBalance(root->right) <= 0)
return leftRotate(root);
// Right Left Case
if (balance < -1 &&
getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// A utility function to print preorder
// traversal of the tree.
// The function also prints height
// of every node
void preOrder(Node *root)
{
if(root != NULL)
{
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}
// Driver Code
int main()
{
Node *root = NULL;
/* Constructing tree given in
the above figure */
root = insert(root, 9);
root = insert(root, 5);
root = insert(root, 10);
root = insert(root, 0);
root = insert(root, 6);
root = insert(root, 11);
root = insert(root, -1);
root = insert(root, 1);
root = insert(root, 2);
/* The constructed AVL Tree would be
9
/ \
1 10
/ \ \
0 5 11
/ / \
-1 2 6
*/
cout << "Preorder traversal of the "
"constructed AVL tree is \n";
preOrder(root);
root = deleteNode(root, 10);
/* The AVL Tree after deletion of 10
1
/ \
0 9
/ / \
-1 5 11
/ \
2 6
*/
cout << "\nPreorder traversal after"
<< " deletion of 10 \n";
preOrder(root);
return 0;
}
// This code is contributed by rathbhupendra
|
Output:
Preorder traversal of the constructed AVL tree is
9 1 0 -1 5 2 6 10 11
Preorder traversal after deletion of 10
1 0 -1 9 5 2 6 11
- 시간 복잡도
rotation 작업(왼쪽 및 오른쪽 회전)은 몇 개의 포인터만 변경되므로 일정한 시간이 걸림.
높이를 업데이트하고 균형 요소를 얻는 데에도 일정한 시간이 걸림.
따라서 AVL 삭제의 시간 복잡도는 H가 트리의 높이인 O(h)인 BST 삭제와 동일하게 유지됨.
AVL 트리가 균형을 이루기 때문에 높이는 O(Logn)
따라서 AVL 삭제의 시간 복잡도는 O(Log n)
- AVL 트리의 장점
항상 높이 균형을 유지
높이는 절대 LogN을 초과하지 않음. (여기서 N은 노드 수)
이진 검색 트리보다 더 나은 검색을 제공
자체 균형 기능이 있음
- AVL 트리 요약
AVL 트리는 자체 균형 이진 검색 트리
균형 요소 범위는 -1, 0 및 +1.
밸런싱 계수가 범위를 벗어나면 회전을 수행해야 함.
삽입, 삭제, 검색 시간은 O(log N)
AVL 트리는 삽입 및 삭제 작업에 비해 검색이 더 빈번한 곳에서 주로 사용됨.
3. Leet code 문제 풀이
- 110. Balanced Binary Tree
→ 문제
이진트리가 주어졌을 때, AVL(균형 이진트리)인지 아닌지 판별해 T/F를 출력하기
→ 풀이:
recursion을 이용해 AVL 트리인지 판별하도록 했다.
- height 함수:
root 노드의 height를 계산하는 함수
(왼쪽 자식노드의 높이부터 오른쪽 자식노드의 높이까지) 중 max값에, 루트노트의 높이까지 +1 한 값을 반환
위의 식으로 계산하면 해당 노드의 height를 계산할 수 있음
- isBalanced함수:
AVL 트리인지 아닌지 판별하도록 하는 함수
root 노드의 왼쪽 자식노드의 높이와 오른쪽 자식노드의 높이가 하나 이하로 차이나는지 아닌지를 계산해 하나 이하로 차이난다면 true를, 아니면 false를 출력
(왼쪽 자식노드 높이 - 오른쪽 자식노드 높이) 한 값의 절댓값이 1보다 작은지 아닌지를 계산하면 됨
+ 높이를 계산할 때 단말 노드가 나올때까지 계산을 하도록 이에 해당하는 조건도 추가해 주어야 함
출처: AVL Tree | Set 1 (Insertion) - GeeksforGeeks AVL Tree | Set 2 (Deletion) - GeeksforGeeks https://velog.io/@qlwb7187/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0AVL%ED%8A%B8%EB%A6%AC-C
'자료구조실습 수업' 카테고리의 다른 글
| [9주차 과제] (0) | 2022.11.06 |
|---|---|
| [MID] 중간 프로젝트 (0) | 2022.10.16 |
| [3주차 과제] (0) | 2022.09.25 |
| [2주차 과제] (0) | 2022.09.18 |
| [1주차 과제] 리포트 요약 과제 (0) | 2022.09.12 |