6장 레드 블랙 트리- 방통대, 알고리즘

3~5 정렬파트는 한번에 다루는게 좋을것 같아서 먼저 7장부터 진행하겠습니다

학습개요

이번 강의를 포함해서 앞으로 두 번의 강의를 통해서, 주어진 저장 매체에서 원하는 데이터를 찾는 탐색 알고리즘에 대해서 살펴본다. 우선 이번 시간에는 순차 탐색과 이진 탐색과 같은 기본적인 탐색 방법을 비롯하여 이진 탐색 트리와 2-3-4 트리에 대해서 학습한다.

 

학습목표

• 순차 탐색의 개념, 성능, 특징을 이해하고 설명할 수 있다.
• 이진 탐색의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.
• 이진 탐색 트리의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.
• 2-3-4 트리의 개념, 동작, 그리고 성능과 특징을 이해하고 설명할 수 있다.

주요용어

• 순차 탐색(sequential search)
• - 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법
• 이진 탐색(binary search)
• - 정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여가면서 원하는 값을 가진 원소를 찾는 방법
• 이진 탐색 트리(binary search tree)
• - 각 노드의 왼쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 작고, 오른쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 크다는 조건을 만족시키는 이진 트리
• 후속자(계승자) 노드(successor node)
• - 트리에서 어떤 노드의 바로 다음 키값을 갖는 노드
• 2-3-4 트리- k-노드는 (k-1)개의 키와 k개의 자식으로 구성
• - 2-노드, 3-노드, 4-노드로 구성된 균형 탐색 트리
• 노드 분할(node split)
• - 2-3-4 트리에서 노드 분할이란 4-노드 하나를 2-노드 셋으로 분할한 후 가운데 2-노드를 부모 노드로 이동시키는 연산

정리하기

1. 순차 탐색

• 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법
• 성능 → O(n)
• 모든 리스트 형태의 입력에 적용 가능 → 특히 비정렬 데이터 탐색에 적합
• 데이터가 큰 경우에는 부적합

2. 이진 탐색

• 정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여가면서 원하는 값을 가진 원소를 찾는 방법 → 분할정복 방법 적용
• 성능 → 탐색 O(logn), 초기화 O(nlogn), 삽입/삭제 O(n)
• 정렬된 리스트에 대해서만 적용 가능
• 삽입/삭제 연산이 빈번한 응용에는 부적합 → 삽입/삭제 후 입력 리스트의 정렬 상태를 유지하기 위해서는 O(n)의 데이터 이동이 필요

3. 이진 탐색 트리

• 각 노드의 왼쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 작고, 오른쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 크다는 조건을 만족시키는 이진 트리
• 탐색 연산 → 루트 노드로부터 시작해서 값의 크기 관계에 따라 트리의 경로를 따라 내려가면서 진행
• 삽입 연산 → 우선 삽입할 원소를 탐색한 후, 탐색이 실패하면 해당 위치의 자식 노드로서 새 노드를 추가
• 삭제 연산 → 삭제되는 노드의 자식 노드의 개수에 따라 3가지 경우로 나누어 처리
• ① 자식 노드가 없는 경우 → 남는 노드가 없으므로 별도의 처리가 불필요
• ② 자식 노드가 하나인 경우 → 자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따라 올림
• ③ 자식 노드가 두 개인 경우 → 삭제되는 노드의 후속자 노드를 삭제되는 노드의 위치로 올리고, 후속자 노드를 삭제되는 노드로 취급하여 자식 노드의 개수에 따라 다시 처리
• 성능 → 평균 O(logn), 최악 O(n)
• 삽입/삭제 시 기존 노드의 이동이 거의 발생하지 않음
• 원소의 삽입/삭제가 진행됨에 따라 최악의 성능을 갖는 경사 트리 형태가 될 수 있음

4. 2-3-4 트리

• 2-노드, 3-노드, 4-노드로 구성된 균형 탐색 트리 - k-노드는 (k-1)개의 키와 k개의 자식을 가짐
• 4-노드의 분할 → 삽입을 위한 탐색 과정에서 4-노드를 만나면 하나의 4-노드를 3개의 2-노드로 분할하고, 가운데 2-노드에 해당하는 키를 부모 노드로 이동시킴
• 성능 → 탐색/삽입/삭제 O(logn)
• 2-3-4 트리를 그대로 구현하면 노드의 구조가 복잡해서 이진 탐색 트리보다 더 느려질 가능성이 많음\

---

1. 순차탐색

• 탐색이란?
  • 여러 개의 원소로 구성된 데이터에서 원하는 값을 갖는 원소를 찾는 것
  • 데이터의 형태 : 리스트, 트리, 그래프 등
  • 내부 탐색 VS 외부 탐색
  • 관련 연산 → 탐색 + ( 초기화, 삽입, 삭제 )
• 탐색 방법
  • 리스트 형태 → 순차 탐색, 이진 탐색
  • 트리 형태 → 이진 탐색 트리, 2-3-4 트리, 레드-블랙 트리, B-트리
  • 해시 테이블 → 해시 함수, 충돌 해결 방법

리스트 형태로 주어진 원소들을 처음부터 앞에서 부터 차례로 (”순차”) 비교하면서 탐색 하는 방법

탐색, 삭제하는데 항상 1번 ~ n 번 비교함으로 항상 n번 비교

삽입 리스트의 지막에 추가하는데 상수 시간만 필요 O(1)

모든 리스트 형태의 입력에 적용 가능 → 비정렬 데이터 탐색에 적합

탐색과 삭제에 O(n) 시간이 필요 → 데이터가 큰 경우에는 부적합

2. 이진 탐색

📌 정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여 가면서 원하는 값을 가진 원소를 찾는 방법

• 분할 정복 방법이 적용됨

탐색방법

• 배열의 가운데 요소 A[mid] 와 탐색 key를 비교
  • 같으면 탐색 성공
  • key < A[mid] 왼쪽부분을 또 절반 놔눠 순환
  • A[mid] > 오른쪽 부분을 또 절반 놔눠 순환

연결리스트 구조에서는 이진 탐색 자체가 불가능 → 직접적인 접근을 제공하지 않음 연결리스트가

📌 항상 정렬된 배열일때만 적용 가능

탐색연산 O(logn)

초기화 연산 O(nlogn)

삽입/삭제 연산 O(n)

반응형

3. 이진 탐색 트리

• 📌 한 노드의 왼쪽 서브 트리에 있는 모든 키 값은 그 노드의 키 값보다 작다.
• 📌 한 노드의 오른쪽 서브트리에 있는 모든 키 값은 그 노드의 키 값보다 크다

루트 노드에서부터 시작해서 값의 크기 관계에 따라 트리의 경로를 따라 내려가며 탐색 진행

 

key 는 40

 

삽입할 원소를 탐색한 후, 탐색이 실패하면 해당 위치에 자식 노드로서 새 노드를 추가

후속자 노드, 계승자 successor

• 어떤 노드의 바로 다음 키 값을 갖는 노드

삭제 노드의 자식 노드 개수의 따라 구분해서 처리

• [경우1] 자식 노드가 없는 경우(리프 노드의 경우)
  • 남는 노드가 없어 위치 조절이 불필요
• [경우2] 자식 노드가 하나인 경우
  • 자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체로 따로 올림
• [경우3] 삭제 노드가 2개인 경우
  • 삭제되는 노드의 후속자 노드를 삭제되는 노드의 위치로 올리고,
  • 후속자 노드를 삭제되는 노드로 취급하여 자식 노드의 개수에 따라 다시 처리

[경우1] - 노드 20삭제

20은 리프노드임으로 바로 삭제가 가능하다

 

 

[경우2] - 노드 40 삭제

일단 40을 삭제 한 후 그대로 위로 올리면 된다

[경우] - 노드 30삭제

30의 바로 다음값을 찾아야함 키값!

30다음은 40임으로

탐색, 삽입, 삭제 연산의 시간 복잡도

• 키값을 비교하는 횟수에 비례 → 이진 트리의 높이가 h라면 O(h)

 

경사 이진 트리의 문제가 발생함에 따라 최악의 수행시간을 가지게 됨으로 이를 방지하고자 2-3-4 트리가 생겨나게 되었다.

(강의에는 안나왓지만 부연설명을 하자면 결국에 이진탐색의 문제는 아래로 뻗어나가며 노드의 수가 경사 이진트리가 되는 문제가 발생하게 되었다 고로 위로 뻗어나가는 구조인 2-3-4 트리가 등장하게 된 것이다)

4. 2-3-4 트리

균형 탐색 트리로서 다음 성질을 만족한다

• 2노드 → 1개의 키와 2개의 자식을 갖는 노드
• 3노드 → 2개의 키와 3개의 자식을 갖는 노드
• 4노드 → 3개의 키와 4개의 자식을 갖는 노드
• 각 노드의 한 키의 왼쪽 서브트리에 있는 모든 키 값은 그 키값보다 작다.
• 각 노드의 한 키의 오른쪽 서브트리에 있는 모든 키값은 그 키값모다 크다.
• 모든 리프 노드의 레벨은 동일

탐색 키 40을 비교하는 경우

사진을 보면 알겠지만 이진트리와 매우 흡사하다

탐색 과정에서 4-노드를 만나면 항상 노드분할을 우선 수행

노드분할이란?

4-노드란 3개의 키를 갖는다고 위에 설명 했었다, 노드를 키 3개를 분할 한 후

가운데의 노드를 위로 올리는 방식을 말한다. (아래 사진 참조)

⦁ 성능 → 탐색/삽입/삭제 O(logn)

⦁ 2-3-4 트리를 그대로 구현하면 노드의 구조가 복잡해서 이진 탐색 트리보다 더 느려질 가능성이 많음