크래프톤 정글 week04, day28 - 배열과 포인터의 관계, 균형 이진 탐색 트리

배열과 포인터의 관계

• 배열:
  • 배열은 여러 개의 데이터를 연속적인 공간에 저장하는 자료구조이다.
  • 예를 들어, 5개의 정수를 저장하는 배열은 메모리에서 연속된 5칸을 차지한다.
  • 배열은 인덱스를 사용하여 특정 위치의 값을 읽거나 쓸 수 있습니다.

• 포인터:
  • 포인터는 주소값을 가지는 변수이다.
  • 자신이 데이터를 저장할 공간을 가지지 않고, 데이터가 저장된 주소를 가리킨다.
  • 포인터는 변수이므로 값을 변경할 수 있다.

• 배열과 포인터의 관계
  • 배열의 이름은 배열의 첫 번째 요소를 가리키는 포인터로 간주될 수 있어 포인터처럼 동작한다.
  • 따라서 배열의 이름은 사실상 포인터이다.
    • 하지만 배열의 이름은 포인터와 달리 재 할당이 불가능한데, 배열의 이름은 그 자체로 주소이며, 변경할 수 없는 상수이다.
    • 배열의 이름과 포인터 변수의 차이점
      • 배열은 메모리에 할당될 때, 컴파일 타임에 배열의 크기가 결정되고 고정된다.
      • 포인터는 런타임에 어떤 주소든 가리킬 수 있으며, 동적 메모리 할당을 통해 가리키는 메모리의 크기를 변경할 수 있다.

#include <stdio.h>

void main(){
	int arr[5] = {1, 2, 3, 4, 5};
	int *ptr = arr;
	// arr은 배열의 이름 *ptr은 포인터 변수이다. 둘 다 arr[0]의 주소를 가리키고 있다.
	
	int another = 10;
	ptr = &another;
	// ptr에 another 변수의 주소를 가리키도록 변경했다.
	// 이처럼 포인터 변수는 다른 주소를 가리키도록 변경할 수 있지만
	
	arr = &another; // This is not valid
	// 주석과 같은 컴파일 오류를 발생시킴
	// 배열의 이름은 배열의 첫 번째 요소의 주소를 가리키며, 이는 변경할 수 없다.
}

• 배열명을 사용하여 각 배열 요소를 참조할 수 있다.
  • 예를 들어 int형 배열이 있다고 가정하면, 배열의 첫 번째 인덱스의 주소에 정수 형태의 인덱스를 더함으로써 배열의 다른 요소를 참조할 수 있다.

#include <stdio.h>

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    
    for(int i = 0; i < 5; i++) {
        printf("arr[%d] = %d\n", i, *(arr + i)); // (arr + i)시 arr[i]의 다음 인덱스로 넘어간다
    }
    
    return 0;
}

// 결과
// arr[0] = 1
// arr[1] = 2
// arr[2] = 3
// arr[3] = 4
// arr[4] = 5

---

균형 이진 탐색 트리

• 모든 노드에 대해 해당 노드의 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 많아야 1인 이진 탐색 트리의 한 종류이다.
• 대표적으로 AVL 트리와, Red-Black 트리가 있다

 

AVL 트리

• 노드의 삽입과 삭제가 일어날 때 균형을 체크하고 유지하는 트리
• BF(Balance Factor) : 왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이를 각 노드의 BF를 [-1, 0, 1]만 가지게 하여 균형을 유지한다.

• AVL 트리 리밸런싱
  • 균형이 깨졌을 때
    • BF가 +면 왼쪽 서브 트리에 이상이 있다.
    • BF가 -면 오른쪽 서브 트리에 이상이 있다.
  • 회전 연산
    • 단순 회전 : LL, RR
      • LL(Left-Left) : 회전 1회, 오른쪽 방향으로 회전

• RR(Right-Right) : 회전 1회, 왼쪽 방향으로 회전

• 이중 회전 : LR, RL
  • LR(Left-Right) : 회전 2회, RR 회전 후 LL 회전

• RL(Right-Left) : 회전 2회, LL 회전 후 RR 회전

 

 

학습 시간 : 13 ~ 25시