BJ.31-1 레드블랙트리(red-black tree)의 기본 개념과 특징을 살펴보고, 삽입 때 레드블랙트리가 어떻게 동작하는지를 아주 자세히 설명합니다! - ko

네 반갑습니다 오늘 이 영상을 끝까지 보신 후엔 레드 블랙 트리의 개념과

속성 그리고 값을 추가할 때 그 동작 방식을 이해하게 됩니다 자 그럼

오늘도 고심 먼저 레드 블랙 트리의 개념과 속성을 알아보도록 하겠습니다

레드 블랙 트리는 이진 탐색 트리의 한 종류입니다 이진 탐색 트리 라는

것은 이전 영상에서 배웠던 것처럼 당 노드에서 자기보다 작은 값들은 그

노드의 왼쪽 서브 트리의 있고 자기보다 큰 값들은 그 노드의 오른쪽

서브 트리의 있다는 그런 특징을 만족하는 이진 트리를 이진 탐색 트리

라고 배웠죠 그러면 이 레드 블랙 트리는 이 이진 탐색 트리의 한

종류인데 2 레드 블랙 트리는 또 어떤 특징 있냐면 스스로 균형을

잡는다는 그런 특징이 있습니다 그래서 이렇게 스스로 균형을 잡게 되며 어떤

장점이 있냐며 일반적인 바이너리 서치 트리에서 의 2월 스 케 이 스 의

단점을 개선을 하게 되요 이게 무슨 말이냐면 바이널 써 치트 위해서

최악의 경우 그러니까 월 스 케이 쓰일 때는 구조가 이런식으로 한쪽으로

편안히 될 수 있거든요 이렇게 한쪽으로 편향이 되어있는 상태에서 의

삽입 삭제 검색 의 시간 복잡도 는 b 구해내 되는데 이게 이제 일반적인

바이너리 서치 트의 단점인 거죠 왜냐하면 시간 복잡도가 피고 애니

라는 말은 최악의 상태에서 그 바이너리 서치 트리에 있는 모든

노드를 한번씩 다 확인을 해줘야 된다 라는 의미 거든요 그래서 이렇게

바이너리 서치 트리에서 월 스케 있을 경우에는 시간 복잡도가 비고 앤 으로

오래 걸린다는 그런 단점을 가지고 있는데 이런 단점을 2 레드 블랙

트리는 스스로 균형을 맞춰서 이 트리가 편향된 구조가 되지 않도록

함으로써 최악의 경우에도 시간 복잡도가 비고 애니 아니라 비고 로그

애니 나올 수 있도록 계산을 하는게 이게 바로 레드 블랙 트리의

장점이라고 보시면 되겠습니다 자 그럼 이 레드 블랙 트리는 어떤 중요한

특징 있냐 모든 노드는 레드 혹은 블랙 이라는거 이런 특징을 가지는 게

레드 블랙 트리가 뭐 이해를 하시면 될 것 같아요

자 그럼 지금부터 레드 블랙 트리 의 속성을 살펴보도록 하겠습니다 먼저

1만 속성은 모든 노드는 레드 호금 블랙이라는 그런 속성이 구요 그래서

지금 왼편에 보시면 모든 노드가 레드 혹은 블랙이 줘 그리고 이번 속성은

루트 노드는 블랙이 달하는 그런 속성이 있습니다 그래서 왼쪽에 보시면

루트 노드가 블랙 이다 라는 것을 보실 수 있어요 이번에 3번 속성을

살펴 봐야 되는데 3번 속성을 살펴보기에 앞서서 1 누드 라는

개념을 설명해야 됩니다 이것은 레드 블랙 트리 에만 존재하는 독특한

개념인데요 이 밀로 드가 어떤 노드 냐 며 존재하지 않음을 의미하는

노드가 바로 기밀 노드 입니다 그래서 자녀가 없을 때의 그 자녀를 릴로

들어 표기를 하는 거죠 다른 옆에서 보시면 이 40에 오른쪽 자녀는 지금

없는 거거든요 그런데 그럼 이렇게 오른쪽 자녀가 없을 때는 이제 오른쪽

자녀의 밀로 들을 펴기를 하는 겁니다 또 다른 경우로 지금 구심을 보시면

90의 왼쪽 오른쪽 차례가 모두 없는 경우 거든요 그럼 이렇게 자녀가 없을

때는 2자녀 위치에 이젠 1일로 들어 표기를 해서 자녀의 존재하지 않음을

이런식으로 일로 들어 표기를 한다는 거죠 그런데 이 레드 블랙 트리에서

느님 일로 듯 5 값이 있는 노드들 이런 노드들 과 동등한 노드로 취급이

됩니다 그래서 밀로 드는 일반적인 노도와 동등하게 취급이 되기 때문에

결국 이 레드 블랙 트리 에서는 리프 노드가 뭐가 되냐 리프 노드 라는

개념이 자녀가 없는 노드를 리프 노드 라고 우리가 배워 짜 나요 그러면 이

레드 블랙 트리의 3 리프 노드는 결국 릴로 드가 리프 노드가 되는

겁니다 그래서 지금 보시면 이 왼쪽에 레드 블랙 트리에서 리프 노드는

얘네들이 리프 노드가 되는거고 결국 이 레드 플랙 트리에서 모든 리프

노드는 일로 드가 리프 노드가 된다 그렇게 이해를 하시면 될 것 같아요

자 그럼 ain't 1 노드의 개념을 잘 이해를 해주셔야 이제 레드 블랙

트리의 3번 속성이 무엇인지 이해를 하실 수 있습니다 2 레드 블랙

트리의 3번 속성은 모든 일로 드 그러니까 레드 블랙 트리에서 를 리프

노드 줘 모든일 노드는 블랙 이다 라는 특징을 가지고 있어요 그래서

이제 1 노드와 일반적인 노드를 9분하기 위해서 이 동그라미를 조금

작게 표기를 했습니다만 어쨌든 얘네들이 의미하는 것은 일반적인

노드와 같은 형태의 노드 라고 생각을 하시면 될것 같고 레드 플랙 트리의

3 이런 1일 노드들은 모두 블랙 이다 라는 것 이게 바로 3번

속성이다 그렇게 이해하시면 될 것 같습니다

자 이어서 4번 속성을 살펴보겠습니다 4번 속성은 레드의 자녀들은 반드시

블랙 이어야 한다 이게 4번 속성 이에요 그럼 이 말은 궁금이

생각해보면 어떤 의미와 통일 하려면 레드가 연속적으로 존재할 수 없다는

입니다 그래서 지금 왼쪽에 레드 블랙 트리를 보시며 지금 여기에 레드 가

있으면 그 자녀들은 다 블랙 이다 라는 것을 확인하실 수 있죠 그리고

여기에 또 레드를 보시면 지금 일로 들을 따로 표기하지 알아서 그렇지

사실에 여기에 지금 단일 노드 가 있는 거죠 이렇게 단일 노드 가 있는

겁니다 그래서 여기에서도 보셔서 알 수 있겠지만 이 레드의 자녀들은 모두

블랙 이어야 한다 이게 레드 블랙 트리의 4번 속성 이구요 이제 5번

속성을 살펴보며 임의의 노드에서 자손 릴로 들까지 칸은 경로 들에 플렉스는

모두 같다 이런 특징을 가지는게 2 레드 블랙 트리의 오븐 속성입니다

큰데 이 때 이 블랙을 카운트를 할 때 자기 자신은 이 카운트에서 채

외가 됩니다 자 그럼 옆에서 얘를 한번 살펴볼게요 이 왼쪽에서 보시는

이 트리가 레드 블랙 틀린 거 잖아요 그러면 임의의 노드 라고 했으니까 2

80 을 가지고 테스트를 해보겠습니다 그러면 80에서 이 80에 자손 일로

들어가는 경로는 1 2 3 이렇게 총 3개가 있습니다 그러면 이 3개의

경로에서 각각 블랙 수가 몇 개 인 적 확인해보면 자기 자신은 강 찾아

온다고 했기 때문에 이 경우에서 블랙은 1 고 2 경로 에서도 블랙

2 1 고 2 경로 에서도 블랙이 하나라는 것을 확인할 수 있습니다

그래서 이 세계의 경로 모두 14 개수가 1개 로 동일하다는 것을 확인

했구요 이번에는 그런 20에서 한번 확인해보겠습니다 20 에서 20에

차선 릴로 들어가는 통로는 1 2 3 4 5 이렇게 총 5개가 있구요

그러면 이 5개의 경로에서 에 블랙스 를 답하기를 한번 해 보며 먼저 이

경로에서 의 블랙 수는 2개입니다 그리고 이 경로에서 도 블랙 수가 두

개 요 2 경우에서도 플렉스가 2개 고의 경우에서도 2개 이 경우 에서도

2개입니다 그래서 이 다섯 개의 경로 모두 블레 개수는 2개로 똑같다는

것을 알 수 있어요 그러면 입욕 앤 오더 뿐만 아니라 나머지 모든 다른

모드들을 확인을 해봐도 다 동일하게 이런 특징을 가지고 있거든요 그래서

레드 블랙 트리는 모든 노드에서 이런 특징을 지닌 인가 그래서 여기서 이미

앤 오더 라고 표현 한 거구요 그래서 임의의 노드에서 자선 일로 듯 까지

가는 경로 들의 블랙 쓰는 같다 이 속성이 바로 레드 블랙 트리의 5번

속성이다 그렇게 이해를 해주시면 될 것 같습니다

자 그러면 이 5번 속성을 바탕으로 나오는 새로운 개념이 있는데요 바로

이 플래 카이트 라는 개념입니다 노드 x 에서 플랙 하이트 라는 것은 그

노드 헥스 에서 이미 의 자손 1 노드 까지 내려가는 경로에서 의 그

플렉스를 이 노드 x 의 블랙 화이트 라고 해요 그리고 여기서도 마찬가지로

이 플렉스를 가운데 할 때 자기 자신은 카운트에서 채울 가 되겠죠 자

그러면 이 플랙 하이트 하는 개념은 5번 속성을 만족 해야만 성립하는

개념입니다 왜냐하면 5번 속성을 만족한다는 것은 이미 의 노드에서 그

노드의 자손 밀 노드 까지 내려가는 모든 경로에 3 블랙 수는 같다 라는

동일하다는 의 의미인 거잖아요 그래서 어차피 모든 경로에 3 블랙 쓰는 다

통일 하니까 그러면 이제 그 경로에 블랙스 를 블랙 화이트로 표시를 할

수 있는 겁니다 이 5번 속성을 만족해야만 성립하는 개념 이라는 거죠

그래서 거꾸로 얘기하면 5번 속성을 만족하지 않는다면 근래 카이트 하는

개념 자체가 존재할 수가 없습니다 왜냐하면 5번 속성을 만족하지 않기

때문에 이미 에 노드 x 에서 그 노드의 자손 1 노드로 가는 모든

경로에 플렉스가 이제는 다를 수 있기 때문에 그럼 이제 블랙화이트 의 개념

자체가 성립할 수가 없고 그 개념은 깨지게 되는 거죠 만족하지 않게 되는

겁니다 자 그러면 이제 왼쪽에서 블랙화이트 를 한번 구해 보도록

하겠습니다 이 왼쪽을 레드 블랙 트릭이 때문에 5번 속성을 만족을

하고 있죠 그러면은 20에서 의 플래 카이트 를 한번 구해 보면 어차피

5번 속성을 만족하고 있으니까 모든 경로 다 확인할 필요 없고 20에서

20에 차 손님 노드를 아무거나 하나 골라서 근일 로드 까지 내려가는

경로에 3 블랙스 를 카운트 만 해주면 20 에플렉 타이틀을 구할

수가 있는 겁니다 자 그러면 저는 이 일을 노드 까지 오는 경로에서

플렉스를 카운트를 해볼게요 그러면 20에서 이렇게 내려오게 되면서 총

2개의 블랙 을 만나게 되죠 그러면 이제 이 20에 블랙 카이트 는 이

가 되는 겁니다 5번 속성을 만족하고 있으니깐 하나의 경로가 확인해보면

되는 거였어요 자 그럼 이번에는 50에서 블랙 하이 표를 구해 보도록

하겠습니다 마찬가지로 일론 으로 가는 경로 하나만 선택해서 그 경우에 블랙

수를 카운터 만하면 블랙화이트 를 구할 수 있겠죠 그러면 저는 2일

노드를 선택을 해서 인 로드 까지 내려가는 무에서 의 블랙스 를

카운트를 해봤더니 이렇게 총 2개가 있어서 그럼 이 50에 블랙 화이트

도 이라는 것을 알 수 있습니다 그리고 이 5번 속성과 관련해서 또

흥미롭게 살펴볼 내용이 하나 있는데요 그게 뭐냐면 색을 바꾸면 서도 5번

속성을 유지하는 방법입니다 이게 무슨 말이냐면 레드 블랙 트리가 오버

속성을 만족하고 있을 때 만약에 어떤 두 자녀가 같은 색을 가지고 있다면

그러면 그 때 부모와 두 자녀의 색을 바꿔줘도 오던 속성은 여전히 만족한다

라는 그런 특징 있어요 그래서 이 왼쪽을 보시면 제가 레드 블랙 트리를

일반화 시켜서 한 형태로 그래 봤는데요 그래서 이 크림 부터

차례대로 설명하며 a 위에 보이는 이 화살표는 a 의 부모가 있다는

뜻이구요 그리고 비화 시 밑에 보이는 이 삼각형은 비워 씨의 서버 털이 를

의미합니다 그리고 이 레드 블랙 트리는 5번 속성을 만족하고 있는

상태 라고 했을 때의 지금 보시면은 이해인은 블랙 이고 페이의 차녀인 b

와 c 는 둘다 래드 잖아요 그러면 이 부모와 자녀의 색깔을 바꿔 줘서

a 를 레드로 만들고 비화 씨를 블랙 으로 만들어도 즉 이렇게 색깔을 바꿔

준비에도 여전히 이 트리는 5번 속성을 만족한다 라는 그런 의미입니다

이게 그냥 직관적으로 생각을 해봐도 그럼 당연한 얘기잖아요 그래서

간단하게 설명을 하고 넘어가면 먼저 이 부모에서 생각을 해 봅시다 이

부모 입장에서 바뀌게 전에 a 와 b 를 통과해서 자손 일로 들어가는 그

경로 에서의 블랙 수나 바뀌고 난 후에 이 부모 입장에서 a 와 p 를

통과해서 이 자손 일로 들어가는 경로에서 의 블랙 쓰는 바뀐게

없습니다 얘는 a 와 p 의 색깔만 바뀌었을 뿐이지 블랙에서 추가 되거나

아니면 블랙의 사라졌고 다 그런게 아닌 거잖아요 마찬가지로 이 부모

입장에서 회의와 시기에 경로를 거쳐서 자손 일로 들어가는거 나 색깔을

바꾸고 나서 이 부모 입장에서 a 와 c 를 거쳐서 자손 일로 도록

하는거나 그 경로에서 fls 또한 바뀐게 없습니다 그러니까 결국 부모

입장에서는 달라진게 없는 거죠 이게 헤이 의 입장에서 생각을 해보면

자녀가 둘 다 블랙 으로 바뀌었기 때문에 왼쪽으로 빠져서 자 손질로

들어가는 경로가 오른쪽으로 빠져서 자산 일로 들어가는 경로나 둘다 그

경로 에서의 블랙 예수가 하나씩 추가 됐을 뿐이지 그 각각의 경로에서 에

블랙 수는 모두 동일합니다 1 가 추가가 된 상태로 그냥 동일 한 거죠

그리고 이 b 와 c 의 경우에는 자기 자신은 카운터를 하지 않기

때문에 바뀌게 전이나 바뀐 후 나 그 자선 일로 들어가는 경로에서 에

블랙스 에는 전혀 영향이 없습니다 그리고 있어 배터리는 바뀐 것이

아무것도 없기 때문에 그러면 결국 부모와 두잔의 색을 바꿔줘도 5번

속성을 여전히 만족한다는 것이 증명이 되는 거죠 그리고 반대로도 성립

하겠죠 만약에 이번에는 이 형태가 5번 속성을 만족하고 있는 상태였다

며 이 형태에서 부모가 자식의 색깔을 바꿔 줘서 이 형태로 만들어 준다

한들 마찬가지로 이 형태의 서도 5번 속성을 여전히 만족을 하게 되는

겁니다 그래서 레드 블랙 트리가 5번 속성을 만족하고 있는 상태에서 부

자녀가 같은 색을 가질 때 부모 와 두 자녀의 색을 바꿔줘도 5번 속성을

여전히 만족한다는 이 특징인 특징을 잘 기억을 해주시면 좋을것 같아요

나중에 뒤에서 삽입하거나 삭제할 때 이 특징을 사용하기 때문에 잘 기억을

해 주시면 좋을 것 같습니다 자 그래서 이제 레드 블랙 트리 의

5가지 속성은 다 살펴 보았구요 그러면 이제 레드 블랙 트리가 어떻게

균형을 잡는 지에 대해서 간단하게 정리하고 넘어가도록 하겠습니다 이랜드

블랙 트리에서 삽입과 삭제를 하게 되며 주로 2 4번 속성과 5번

속성을 위반을 하게 됐거든요 그러면 이렇게 위반 한 것을 해결하려고

구조를 바꾸다 보면 자연스럽게 2 레드 블랙 트리의 균형이 잡히게

됩니다 그래서 이런 식으로 균형을 잡아줌으로써 2 레드 블랙 트리는

편향 되지 않을 수 있는 거죠 자 그러면 지금부터 레드 블랙 트리 의

삽입 방식을 살펴보도록 하겠습니다 먼저 이 삽입에 천체 큰 그림을

살펴보며 삽입하기 전 단계는 레드 블랙 트리아 속성을 만족한 상태입니다

그러면 이제 삽입을 하게 되면 이 삽입 방식은 일반적인 바이너리 서치

트리와 동일합니다 그래서 삽입을 한 후에 혹시 이 레드 블랙 트 위의

속성을 위반 하지 않았는지 그 여부를 확인 해야 되요 만약에 레드 블랙

트리 의 속성을 위반했다 면 그렇다면 이 구조를 제 조정을 해줘야 됩니다

그래서 재조정을 한뒤에 다시 레드 블랙 틀의 속성을 모두 만족할 수

있도록 바꿔줘야 되는거죠 그래서 삽입은 이런 단계를 거쳐서 이루어

진다고 보시면 될 것 같구요 그러면 새로운 값을 삽입을 할 때에

그 노드의 색깔은 뭐가 되냐 삽입하는 노드의 색은 항상 레드입니다 자 그럼

이제 부터 간단한 예를 통해서 어떻게 삽입이 동작하는 지를 살펴보도록

하겠습니다 오심을 추가를 해보죠 그러면 지금 아무것도 없기 때문에 이

위치에 52 생길 겁니다 자 여기 이렇게 52 추가가 됐습니다

삽입되는 노드의 색을 항상 레드 라고 했기 때문에 지금 50에 색깔의 는

레드 구요 그 다음에 노드를 삽입을 할 때에 존재하지 않는 자녀 자녀

없음을 나타내는 인 일로 드가 자동적으로 항상 추가가 되요 삽입을

할 때 같이 추가가 됩니다 그 때인 1 노드의 색은 블랙 으로 고정이

되기 때문에 그렇게 고정을 해 줌으로써 자연스럽게 2 3번 속성

모든 일로 드는 블랙 이어야 된다라는 이승봉 속성을 완벽하게 됩니다 지금

그런데 이 상태를 보면 이 50 의 루트 노드 잖아요 그러면 루트 노드는

레드 블랙 트리 의 이번 속성 에 따르면 플레이어 야 되는데 지금

이렇게 래드 기 때문에 이번 속성을 위반한 상태입니다 그럼 이런 경우에는

레드를 블랙 으로 바꿔 주면 해결이 되는 거죠 자 이렇게 루트 노드의

색깔을 블랙 으로 바꿔 줬고 이제 이 레드 블랙 트리의 모든 속성을

만족하게 됩니다 그래서 잠시 정리하고 넘어가면 새로운 노드를 삽입할 때마다

그 노드의 색깔은 레드 라고 했기 때문에 그래서 이제 레드 를 삽입한

위에 리튠 노드는 블랙 이어야 한다 라는 이 이번 속성을 위반을 했다면

그 때는 그 루트 노드의 색깔을 블랙 으로 바꿔 주면 해결이 된다 이렇게

이해를 하시면 되겠습니다 자 그럼 이제 이 상태에서 21

삽입을 해 볼게요 먼저 20과 51 비교를 합니다 그럼 22 더 작기

때문에 왼쪽으로 빠져서 이제 여기엔 1 노조가 있으니깐 이것도 자녀가

없다는 의미 니까 이 위치에 20 을 넣어 주면 될 겁니다 그러면 이제

여기에 22 추가됐고 레드 플랙 트리의 모든 속성을 만족을 하게

됩니다 자 그럼 이 이 타이밍에서 왜 새로 삽입하는 노드는 레드 인지에

대해서 살펴보도록 하겠습니다 그 이유는 삽입한 후에도 5번 속성을

만족하기 위한 건데요 이 5번 속성은 다시 한번 복귀를 해보면 임의의

노드에서 자손 릴 노드들 까지 가는 경로 들의 블랙 수는 모두 같다 이게

레드 블랙 트리오 번 속성 이었죠 자 그러면 이 왼쪽에 레드 블랙 트리가

있습니다 이 레드 블랙 트리는 5번 속성을 만족하고 있는 상태에요 그리고

이 레드 블랙 트리의 보기좋게 릴로 들을 1 그려졌습니다 그럼 이상태에서

이제 새로운 노드를 삽입을 했더니 그 삽입된 위치가 여기라고 해볼게요

그러면 삽입 후에는 이런 모습이 됐습니다 자 이제 이 상태에서 임 1

노드와 200 연일 노드를 비교를 해볼게요 자유글 레드 블랙 트리에서

인 일은 노드의 조상 노드가 얘기하라 있다고 해 보겠습니다 그냥 임의로

아무거나 초상 하나를 고른 거에요 그러면 은이 조상 모드에서 이미리

노드 까지 오는 경로에서 의 블랙 수랑 애들을 삽입한 이후에 똑같은 그

조상에서 2일 노드 까지 오는 경로 혹은 1 노드 까지 오는 경로에서 의

블랙 쓰는 똑같잖아요 그러면 결국 삽입 후에도 경로 상에서의 플렉스의

아무런 영향을 끼치지 못했으니까 4 비프 이 상태에서도 5번 속성을

만족한다고 볼 수 있는거죠 그래서 이런 이유 삽입 후에도 5번 속성을

만족하기 위해서 새로 삽입하는 노드는 레드 가 되는 겁니다 이해가 되시죠

자 그러면 이제부터는 1 노드를 따로 표기를 하지 않을 거 거든요 따로

표기하지 않아도 삽입되는 노드는 일로 두 개가 항상 같이 따라오고 그 일로

드는 렉 이라는 사실을 기억 을 해주시면 좋을 것 같습니다 자 그럼

이제 이 상태에서 이 셀트 씹을 해 볼게요 바이너리 서치 틀의 삽입

기본적으로 동일하다 했기 때문에 시 꽈 50을 비교해서 12 작으니까

왼쪽으로 빠지고 칩과 의식을 비교를 해서 12 20 보다 작기 때문에

이제는 이 위치에 12 들어가게 될겁니다

자 그럼 이렇게 실이 추가가 됐을 때의 이게 레드 블랙 트리의 4번

속성을 위반을 하게 됐어요 4번 속성은 노드가 해 저라면 자녀들은

플레이어 야 되는데 지금 20 의 색깔이 래드 인데 이 렌즈의 자녀의

색깔 또한 레드 가 돼버린 거죠 그래서 이 4번 속성을 위반을 하게

된 겁니다 그러면 이제 이 문제를 어떻게 해결할 수 있을까 고민을 하게

되는데 이제 값은 다 빼고 색깔만 놓고 봤을 때 레드가 한쪽으로 몰려

있으니까 한쪽으로 몰려 있는 일에 다 하나를 반대편으로 옮겼으며 그래서

이런 형태로 만들어 주며 4번 속성을 위반한 것을 해결해 줄 수 있지

않을까 이런 생각이 드는 거죠 그런데 여기서 또 우리가 잊지 말아야 할

것은 이런 식으로 구조를 바꿔 준 뒤에도 바이너리 서치 트리의 특징

또한 유지가 되어야 된다는 겁니다 그러니까 이 바이너리 서치 트리의

특징은 모든 노드에서 자신의 왼쪽 서부터 리는 자신보다 작은 값들을

가지고 자신의 오른쪽 싸부 트리는 자신보다 큰 값을 가져야 된다는 2

특징 풍부한 유지가 되어야 된다는 거죠 그러면 지금 이런 형태에서 이런

형태로 바꾸어 주면서도 공시에 바이너리 서치 트리의 특징을

만족시키려면 여기에 있는 이 값들이 어떻게 배치가 해야 되냐면 이런식으로

배치가 되어야 됩니다 그러면 이렇게 구조적으로 여기서 이런 모습으로 바꿔

주게 될 때 바이너리 서치 트리 의 특징을 유지시키는 방법은 우리가 치는

영상 에서 봤던 것처럼 바로 계절입니다 2회전에 의미가 대단히

중요한데요 바이너리 서치 트리 해서는 회전을 시키면 그 구조를 바꿔

주면서도 여전히 바이너리 서치 트리의 특징을 유지 시킨다 라는 그런 특징이

있습니다 이게 바로 회전의 아주 중요한 특징이 되는 겁니다 그래서

이제 우리가 정리를 하며 지금 이 형태가 4번 속성을 위반 한 상태인데

그럼 이것을 해결하기 위해서는 레드가 이렇게 한쪽으로 몰려 있으니까 레드

하나를 이 쪽으로 넘겨 주면 해결이 될 것 같은데 이렇게 레드 하나를

넘겨줄 때 아이디어 리서치 트리의 특징 또한 유지하면서 넘겨 줘야 되기

때문에 그러면은 그 특징을 유지하기 위해서는 우리가 회전을 사용을 해야

된다는거 그러면 관건은 회전을 어떻게 사용할 지가 관건이 되는 겁니다 자

그럼 이상태에서 회전을 어떻게 쓰며 이 형태에서 이 형태로 바꿔 줄 수

있을까 고민해 보며 사실에 니 50을 기준으로 오른쪽으로 회전을 시키면

50은 아래로 내려오고 20을 위로 올라가면서 최종적으로 는 이런 모습이

됩니다 그러면 은 2 레드 플랙 색깔을 빼놓고 구조와 값만 놓고 보면

지금 이모습이 임무 수가 통일 하잖아요 그럼 이제 20과 이 50의

색깔만 바꿔 주면 최종적으로 이런 형태 의 모습과 동일하게 되는 겁니다

자 그런데 지금은 회전 후에 색깔을 바꿔 주는데 사실은 색깔을 먼저

바꿔주고 패전을 해도 통일 하거든요 그러면 올려 있는 레드를 반대편으로

옮겨 준다 라는 의미를 강조하기 위해서 전에 색깔을 먼저 바꿔 준

뒤에 회전을 하도록 하겠습니다 자 그러면 이 상태에서 20과 50에

색을 먼저 바꿔줍니다 이 두 개의 색깔을 바꿔 주며 이게 52 레드가

되고 22 블랙이 됐죠 그럼 이제 이 상태에서 50을 기준으로 오른쪽으로

이렇게 회전을 시켜 줍니다 그러면 은 50은 내려오고 20원 올라가게

되면서 최종적으로 이런 모습이 되는 거죠 그러면 우리가 목표로 했던 이

모습과 똑같아 치게 되었습니다 그리고 이제 이 상태는 이제 4번 속성을

위반한 게 해결이 됐죠 그래서 이 4번 속성을 포함해서 레드 블랙

트리의 모든 속성을 만족한다는 것을 확인하실 수 있습니다 자 그럼 에

정리를 하고 넘어가겠습니다 레드 를 삽입한 후에 4번 속성을 위 발을

했을 때의 그 위반의 형태가 삽입된 레드 노드가 부모의 왼쪽 자녀 고 또

부모들의 들면서 그 규모 또한 할아버지 왼쪽 자려고 그리고 삽입된

노드의 삼촌 그러니까 부모의 형제 조그 삼촌도 블랙 이라며 그림으로

치면 이런 모습입니다 일어 형태일 때 이런 형태를 k3 라고 하거든요 이런

k3 를 해결하는 방법은 뭐냐며 2 모와 할아버지의 색을 바꿔 준 뒤에

할아버지를 기준으로 오른쪽으로 회전을 하면 해결할 수 아 이렇게 정리를 할

수 있을 것 같고요 여기서 제가 왼쪽 왼쪽 오른쪽 이라고 명시한 부분을

왼쪽 오른쪽으로 바꿔서 이 내용을 적용을 해도 봉 일하게 성립이 된다

그렇게 이해를 하시면 될 것 같습니다 그러면 왼쪽 오른쪽 바꾸면 이

그림에서는 이 루트 노드를 기준으로 좌우로 바꿔 준 뒤에 해석하면 동일

하겠죠 자 그럼 이번에는 다른 케이스를 살펴보도록 하겠습니다 지금

이 상태에서 40을 추가를 해 보겠습니다 그러면 이제 이 위치에

사실 추가가 될 거예요 이렇게 사실이 추가가 되고 나서 보니까 레드 두

개가 연속으로 있기 때문에 4번 속성을 위반을 했습니다 그러면 이

4번 속 등을 해결해야 되는데 지금 보시면 얘도 앞에 키스와 비스타

잖아요 한쪽으로 이렇게 레드가 몰려 있습니다 그럼 이 4번 속성을 위반한

것을 해결하기 위해서는 이렇게 몰려있는 레드 하나를 한쪽으로 이렇게

넘겨 줘야 되는데 i 너 리서치 트리아 특징 또한 유지하면서 넘겨

주려면 마찬가지로 여기서 더 회전을 사용해야 됩니다 그럼 이제 이 회전을

어떻게 사용을 할 지가 관건이 에요 그래서 최종적으로 이런 형태로 어떻게

만들어 줄 수 있을까 이게 이제 문제의 핵심 이거든요 그럼 이

케이스를 살펴 보며 이게 앞에서 봤던 k3 와 살짝 다른 점은 여기가

삽입된 노드 이 삽입된 노드를 기준으로 할아버지까지 가는 경로가

꺾여 있다는 점이에요 그러니까 이노 2에서 이 할아버지 노드 까지 가는

경로가 이렇게 꺾여 있다라는 거죠 아까 앞에서 봤던 k3 의 경우에는

이 위치가 아니라 이 위치에 있었기 때문에 이때는 경로가 이렇게 쭉 뻗어

있었거든요 근데 지금은 경로가 이렇게 꺾여 있는 상태인데 그러면 얘를

어떻게 해결해 줄 수 있나 꺾인 부분을 펴 줘서 k3 와 같은 형태로

만들어 준다면 그러면 그 때부터는 k3 와 같은 방식으로 해결이 가능할

것 같습니다 그러면 이렇게 꺾여 있는 부분을 펴 주기 위해서 20 을

기준으로 왼쪽으로 회전을 합니다 이렇게 왼쪽으로 회전을 하게 되며

20은 아래로 내려오고 40을 위로 올라가게 되겠죠 그래서 이제 이런

모습이 되었습니다 그럼 이 모습은 이제 케이스 3 의 형태가 된

거잖아요 이제 2 케이스 3 을 해결하는 방식으로 똑같이 해결 해

주면 됩니다 그러면 먼저 40과 50 의 색을 바꿔 주죠 이 두 개의 색을

바꿔 주며 이제 50이 레드가 되고 사실이 블랙이 됐습니다 이 상태에서

50을 기준으로 오른쪽으로 회전을 시켜야 이렇게 회전을 시키면 50은

내려오고 40은 올라가게 되면서 이런 모습이 됐고 최종적으로 우리가

기대했던 이런 모습과 동일한 모습이 되는 거죠 그럼 이제 이 상태는 자본

속성을 포함해서 이제 4번 속성을 해결한 거니까 자본 속성을 포함해서

레드 블랙 트리 의 모든 속성을 만족한다고 볼 수 있습니다 자 그래서

여기서 정리하고 넘어가며 레드를 삽입을 한 후에 4번 속성을 위반했을

때 그 위반한 의 형태가 이번에는 400대 레드 노드가 부모의 오른쪽

찬 여의고 부모는 또 레드 면서 할아버지의 왼쪽 자녀 이곳도 삽입된

노드의 삼촌 그러니까 부모의 형제 조 2 삼촌의 색깔은 블랙 일대 그러니까

그림으로 치매는 이 모습이고 이런 케이스를 케이스 푸 라고 합니다 이런

케이스 툴을 해결하는 방식이 어떻게 되냐 부모를 기준으로 왼쪽으로 회전을

시켜서 k3 의 형태로 만들어 뜬 뒤에 이제 이 k3 의 방식으로 해결

해 주면 된다 이렇게 이해를 하시면 될 것 같아요 그리고 얘도 마찬가지로

오른쪽 왼쪽 왼쪽 이라고 되어 있는 이 부분은 오른쪽 왼쪽을 바꿔서 이

내용을 적용해도 동일하게 성립이 됩니다 그리고 이렇게 바꿔 된다면

그림으로 치면 은 이 루트 노드를 기준으로 좌우로 이렇게 바꿔서

적용하면 되는 거구요 자 그럼 다시 돌아와서 또 이번에는 다른 케이스를

살펴보도록 할게요 지금 이 상태에서 30을 삽입을 하게 되며 파이널에서

치트 리마 똑같은 방식으로 삽입을 한다고 했잖아요 그러면은 30과 21

비교해서 32 더 크니깐 오른쪽으로 빠지고 39 50 을 비교해서

30에서 찾기 때문에 이제 이 위치에 32 삽입이 될 겁니다 그럼 이렇게

삽입을 하고 나서 보니까 레드 블랙 트리 의 4번 속성을 위반 했습니다

지금 이렇게 레드가 2개 연속으로 있으니까 4번 속성을 위반을 한 거죠

근데 이걸 해결을 해주고 싶은데 아까 앞에서 살펴보았던 두가지 케이스와는

다르게 레드가 한쪽으로 몰려 있지 않아서 옮겨서 해결할 수는 없습니다

그러면 이 문제를 어떻게 해결할 수 있을까 곰곰히 생각을 해보며 결국 이

부분에서 4 권 속성을 위반한 것을 해결 하면서도 동시에 이미 만족하고

있는 다른 속성들을 위반하면 안되는 거잖아요 그런데 그런 다른 속성들

중에서 5번 속성이 제일 까다로운 속성 이기 때문에 이 5번 속성을

계속 만족시키면서 도 여기 이 문제를 해결할 수 있는 방법을 생각해 내면

되는 겁니다 그러면 우리가 아까 5번 속성과 관련된 특징을 살펴볼 때

자녀의 색깔의 둘다 같으면 부모와 자녀의 색깔을 바꿔줘도 5번 속성을

그대로 유지한다는 그런 특징을 봤어 짠 에요 그러면 그 특징을 여기

활용할 수 있을 것 같습니다 그래서 20과 50을 블랙 으로 바꿔주고

이제 21 레드 로 바꿔 주는 거죠 그러면 이런 형태가 되면서 이제 이

부분에서 4번 속성을 위반 했던 문제의 해결을 했구요 그러면서도

여전히 이 형태는 5번 속성을 만족하고 있는 형태인 겁니다 하지만

이 루트 노드가 레드가 됐기 때문에 이번 속성을 위반을 하게 됐어요 이번

속성을 루트 노드를 블랙 해야 되는데 지금 레드가 된거죠 그래서 이걸

해결하기 위해서 이 10월 블랙 으로 바꿔주면 됩니다 그럼 최종적으로 이런

모습이 됐고 이 형태는 레드 블랙 트리의 모든 속성을 만족을 하게 되는

거죠 자 그래서 이 내용을 정리를 하며 레드 를 삽입한 후에 4번

속성을 위반했을 때 그 형태가 400대 레드 노드의 부모 돌의

들면서 부모의 형제 삼촌도 레드 라며 그래서 그림으로 치면 일어 형태인

거죠 사실 이 형태 말고도 400대 위치가 여기가 아니라 여기거나 여기가

아니라 여기거나 여기가 아니라 여기 더라도 옷 이런 형태의 해당합니다

그래서 이런 형태를 케이스 원 이라고 하구요 2 케이스 원을 해결하기

위해서 어떻게 해야되냐 부모와 삼촌을 모두 블랙 으로 바꿔주고 요

할아버지를 레드 로 바꾼 뒤에 이제 할아버지 에서 다시 확인을 이어서

시작을 하면 됩니다 여기서 중요한게 할아버지 에서 다시 확인을 해야

된다는 거예요 할아버지의 색깔의 레드 로 바뀌었는데 만약에 그 할아버지가

루트 노드 였다면 블랙 으로 바꿔 줘야 되는 거구요 할아버지의 색깔의

레드 로 바뀌었는데 생일 그 할아버지가 부모가 있고 그 할아버지의

부모 또한 내 더라면 다시 또 4번 속성을 위반하게 되는 거기 때문에 꼭

할아버지 에서 다시 확인을 해줘야 된다는 거 이게 케이스 원을 해결할

때 중요하다는 것을 기억 을 해주시면 좋을것 같습니다 자 그러면 지금까지

배웠던 내용들을 바탕으로 레드 블랙 트리 의 삽입을 예제를 통해서

살펴보도록 하겠습니다 자 이 상태에서 인스턴트 80을 하면 이 위치에

추가될 겁니다 이렇게 82 추가됐고 레드 블랙 트리 의 속성을 위반 하지

않았기 때문에 바로 이어서 41 추가를 해 보도록 하겠습니다 그럼

40 은 이 위치에 추가가 되는데요 이렇게 사심 을 추가한 뒤에 4번

속성을 위반을 하게 됐습니다 그러면 어떤 케이스 로 위반을 하게 됐냐

살펴보니까 사실에 부모도 레드 고 사실에 3000 도내 되기 때문에

케이스 원의 상태로 위반을 하게 된거죠 그러면 이 때는 부모와 삼촌을

블랙 으로 바꿔주고 할아버지는 레드 로 변경을 해줍니다 그러니까 30과

80원 블랙 으로 바꿔주고 이 50원 레드 로 바꿔 주는 거죠 이렇게 바꿔

준 뒤에 할아버지 노 실에서 다시 확인을 꼭 해봐야 됩니다 그런데 50

에서 확인을 했더니 모든 속성을 만족을 하기 때문에 그럼 이제

인스턴트 40은 상황에 종료가 되는 겁니다 자 그럼 이 상황에서 35를

삽입을 하며 이 위치에 추가가 되는 거거든요 이렇게 추가를 하고 보니까

여기서 4번 속성을 위반을 한 것을 확인할 수 있어요 그럼 어떤 케이스로

위반 했는지 살펴보면 애드가 이렇게 한쪽으로 몰려 있고 그리고 이

할아버지 노드 까지 가는 이 경로가 벗겨 있기 때문에 케이스 큐에 상태인

것을 알 수 있습니다 그럼 케이스 투에 상태일 때는 이것을 해결해 주기

위해서 먼저 k3 에 상태 쭉 뻗어있는 k3 의 상태로 만들어 줘야

되거든요 그러면 40 을 기준으로 오른쪽으로 회전 을 해주면 이제

꺾이지 않고 쭉 뻗는 형태가 됩니다 그래서 오른쪽으로 회전 을 해주면

이게 40은 아래로 내려오고 30원 위로 올라가게 되면서 이제 이런

모습이 되는거구요 이제 k3 의 상태가 됐죠 쭉 뻗은 형태가 됐습니다

그럼 이제 케이스 쓰릴 때 해결 방식을 적용해 보면 30 과 50 의

색을 먼저 바꿔줍니다 그러면 30일 레드가 되고 35 는 블랙이 됐구요

이제 이 30일 기준으로 왼쪽으로 회전을 시킵니다 그러면 이 30원

아래로 내려오고 35 를 기준으로 얘는 위로 올라가게 되면서 이런

형태가 되는 거죠 이제 이 상태에서는 레드 블랙 트리의 모든 속성을 만족을

하게 됩니다 그럼 이제 여기서 25를 추가를 해 볼게요 바이너리 서재

트리의 3일 하는 방식과 동일하기 때문에 추가된 위치는 여기가 될거구요

그럼 이렇게 추가를 해 놓고 보니까 4번 속성을 위반 했습니다 그럼 어떤

케이스로 위반 했나 살펴보면 케이스 원 의 상태로 위반 했죠 왜냐하면

삽입된 노드의 부모 와 3000 모드 레드 있기 때문이죠 그러면 케이스

원의 해결 방식을 적용해보면 부모와 삼촌을 블랙 으로 바꿔주고 할아버지는

레드 로 변경을 해 주겠습니다 그래서 이렇게 색깔을 바꿔 주고 나서

할아버지 였더니 35 에서 확인을 또 해 봐야 됩니다 근데 35 에서

확인을 했더니 레드가 이렇게 연속적으로 부기가 있기 때문에 4번

속성을 위반한 상태구요 그러면 어떤 케이스로 위반 했는지 살펴보며 레드가

이렇게 한쪽으로 몰려 있고 35 를 기준으로 할아버지 까 이렇게 갔을

때에 이 경로가 꺾여 있기 때문에 케이스 프의 상태인 것을 알 수

있습니다 그러면 예를 해결 하기 위해서는 먼저 k3 의 형태로 바꿔

줘야 되는 거죠 그러면 이 50을 기준으로 오른쪽으로 회전을 시키며 이

50과 함께 80은 아래쪽으로 내려 오고 2 35 와 함께 얘네들은 위로

올라가게 됩니다 그리고 이 40 은 원래 35에 오른쪽 자려 했는데 35

가 위로 올라가면서 35에 오른쪽 자녀가 이제 50이 되거든요 그래서

이 42 붕 뜨게 되는데 근데 오시리 아래쪽으로 내려오면서 50 의 왼쪽

자녀가 비계 되니까 2 40 은 50 의 왼쪽 자녀로 붙으면 되는 겁니다

그래서 표 종적으로 50을 기준으로 오른쪽으로 회전하며 이런 형태가

되구요 그러면 이제 이 형태는 4번 속성을 위 발한 케이스에 상태가 됐기

때문에 k3 를 해결하는 방식으로 해결 해 주면 됩니다 그럼 먼저

20과 30 의 색을 바꿔 주고요 이 두 개의 색을 바꿔 주는 거죠 그래서

이제 21 레드가 되고 35 는 블랙이 됐습니다 이제 이 상태에서

20 을 기준으로 왼쪽으로 회전을 시켜 주는 거죠 그러면 어떻게 되냐면

이식과 함께 10은 아래 쪽으로 내려오게 되고 이 35 와 함께

35에 오른쪽 서버 트리는 위로 올라가게 됩니다 반면에 이 35에

왼쪽 서버 트리 애는 35 가 이렇게 위로 올라가게 되면서 35에 왼쪽

작년에 이제 22 되어 있기 때문에 그러면 원래 35에 왼쪽 서브 트리

는 붕 뜨게 되는데 이제 20에 아래로 내려오면서 이 시대 오른쪽

자료가 비계 되기 때문에 이제 그럼 에 얘네들은 20에 오른쪽 자녀로

붙으면 되는 겁니다 그래서 최종적으로 회전 후에 결과를 보면 이런 모습이

되는거죠 그럼 이 형태는 레드 블랙 트리의 모든 속성을 만족을 하게 되는

겁니다 어떻게 이해가 잘 되시나요 그래서 이 예제를 차근차근 잘 따라와

주시면 예제 블랙 트리에서 삽입이 어떻게 동작하고 어떤 경우에 구조가

바뀌면서 균형이 맞춰지는 지를 이해하실 수 있을 겁니다 네 오늘

준비한 영상은 여기까지구요 이제 다음 시간에는 레드 블랙 트리에서 삭제가

어떻게 이루어지는지를 살펴보도록 하겠습니다 끝까지 봐 주신 모든 분들

정말 최고 싶구요 그러면 다음 영상에서 또 뵙도록 하겠습니다

감사합니다