BJ.30 균형을 빡세게 유지하는 AVL 트리는 이진탐색트리의 단점을 어떻게 극복했을까요? AVL 트리의 동작방식과 장단점을 살펴봅니다 :) - ko

네 반갑습니다 오늘 이 영상을 끝까지 보신 후엔 avl 트리 해 개념과

특징을 알게 되구요 그리고 이 트리가 어떻게 스스로 균형을 잡으면서

동작하는 지를 이해하게 됩니다 자 그럼 오늘도 곳인 먼저 avl 트리

의 개념과 특징 부터 살펴볼게요 avl 트리 라는 것은 이진 탐색

트리의 1동 입니다 자 복습을 한 번 해보면 일단 이 진철이 라는 것은

트리의 모든 노드가 자녀 노드를 최대 2개 가지는 트리를 이진 트리 라고

하죠 그럼 요기서 이진 탐색 트리 라는 것은 뭐냐 이 트리는 이진 트리

인데 이진 트리의 있는 모든 노드가 그 노드의 왼쪽 버튼 이해는 자기보다

작은 값들 만 가지고 그 노드의 오른쪽 서브 트리의 는 자기보다 큰

탑 들면 카 지는 그런 특징을 가지는 이진 트리를 이진 탐색 트리 라고

한다 우리가 이것을 앞의 두 번의 영상을 통해서 배웠습니다 그러면

avr 튀는 뭐냐 며 이 이진 탐색 트리의 한 종류인데요 예 특징은

스스로 균형을 잡는 다는 거예요 그런데 이때 어떻게 스스로 균형을

잡는 야 갤러 스펙터 를 통해서 균형을 유지 를 합니다 그럼 이

밸런스 팩트와 먼지를 좀 더 자세히 살펴볼게요 어떤 노드에서 갤런

스펙트라 는 것은 뭐냐 며 이미 에도 x 에 대해서 그 노드 액스 의 왼쪽

서버 트리 의 높이와 큰옷 x 의 오른쪽 소프트의 높이 차이를 구했을

때 a 높이 차이를 그 노드의 x 의 밸런스 팩트 라고 합니다 이해가

되시나요 이 어지러이 50이라는 노드의 밸런스 펙 털 어떻게 되냐면

왼쪽 서버 틀의 높이를 먼저 구합니다 여긴 이제 일인 거죠 그리고 그

다음에 오른쪽 서버 트리의 높이 올 거에요 있다느니 가 됩니다 그러면

왼쪽 서브 트리의 높이 4 일이고 오른쪽 서부터 레인 오케이 있기

때문에 높이 차를 빼 보며 이제는 - 1인 거잖아요 그러면 이 50 의사의

변론 스펙터 는 - 일이 되는 겁니다 이해가 되시나요

그러면 이제 avl 트리는 어떤 특징을 가진 야 며 이 트리의 모든

노드에 밸런스 캐릭터는 - 이거나 0 이거나 일이다 이런 특징을 가지는

이진 탐색 트리 를 avl 트리 라고 한다 그렇게 이해를 하시면 되겠습니다

그래서 왼쪽에서 살펴보면 아까 이제 50 살펴 봤죠 50 같은 경우에는

이 왼쪽 서버 트리는 높이가 일이고 오른쪽 서버 트리는 높이가 입니까

이래서 이럴때면 - 일이라서 얘 이제 왼쪽 서버 트리와 오른쪽 서버 트리의

높이 찾아 1인 거구요 30 에서도 한번 살펴 볼까요 30 은 왼쪽

서부터 리는 없으니까 - 그리고 오른쪽 버튼 1개의 있으니까 이게

없는거 잖아요 그럼 - 1에서 0 을 빼면 결국 - 일이니까 얘도 벨라

스펙터 가 - 1인 것을 알 수 있습니다 논어 70도 밸런스 팩터를

구해보면 2 왼쪽 서브 트리의 높이가 0 이고 오른쪽 서버 트리는 높이가

일이기 때문에 0에서 이럴때면 - 이리 줘 그 다음엔 5도 90도

살펴보면 왼쪽부터 리는 노드가 하니까 높이가 0이고 오른쪽도 부터라도

높이가 0 이기 때문에 여기서 0 을 빼면 결국 0인 거잖아요 그래서 이

90에 벨라 스펙터 도 영 이라는 것을 확인할 수 있습니다 나머지 이런

리프 노드 들은 왼쪽 때부터 리와 오른쪽 서버 트리가 없기 때문에 높이

차가 달 0 1 거고 그러면 결국은 지금 보시는 이 트리의 있는 모든

노드들의 ls 팩트 는 - 일이거나 0 이거나 일이다 라는 걸 확인할 수

있고 그래서 왼쪽에 트리는 avl 트리 라는 것을 확인하실 수 있습니다

# 그리고 여기서 다시 한번 짚고 넘어가면 avl 트리는 바이너리 서치

트리 그러니까 이진 탐색 트리의 한 종류라는 것 그래서 왼쪽 그림에서

보시면 모든 노드에서 그 노드의 왼쪽 서버 트리는 자기보다 작은 값을

가지고 있고 그 노드의 오른쪽 서버 트리는 자기보다 큰 값을 가지고

있다는 것을 보실 수 있습니다 자 그럼 이 avl 트리는 어떻게

균형을 잡는 야 처리에 삽입 혹은 삭제가 발생한 후에 만약에 어떤

노드에서 그 노대 병원 스펙터 가 - 1 0 일이 아니라면 그러니까 는

사비 포가 삭제 후에 어떤 노드에서 왼쪽 서버 트리와 오른쪽 서버 틀의

높이 차가 이를 넘어서 더 차이가 나게 벌어졌다 며 그런 노드가 생기면

그때는 균형을 맞추는 작업을 수행하게 됩니다 이 때 어떻게 균형을 맞추는

작업을 수행하게 되면 당연히 벌어졌던 높이 차이를 줄이는 형태로 균형을

맞추게 됩니다 자 그래서 av 에 트리가 어떻게 통

작하는 지그 동작하는 방식을 예를 통해서 살펴보도록 하겠습니다 자인

썰도 50 을 하게되면 노드를 하나 만들고 이제 이 노드는 루트 노드가

될 겁니다 그리고 여기에 50 이라는 값이 이제 들어가 있겠죠 그래서 이런

상태가 됐고 이 상태에서 이제 인쇄할 때 70을 합니다 자 우리가 앞에서

설명했던 것처럼 avl 트리는 기본적으로 바이너리 서치 트리즈 이진

탐색 트리 기 때문에 얘는 결국 바이너리 서치 트리에서 사례를 하는

것과 일단은 동일하게 동작합니다 자 그러면 70 과 50 값을 비교하면

72 더 크니까 이제 이 위치에 72 들어가게 될 겁니다 자 이런식으로

추가됐고 근데 추가가 된 뒤에 뭘 해줘야 되냐면 지금은 이제 이진 탐색

트리 중에서도 avl 트리 를 만드는 과정이기 때문에 갤러 스펙터 를 확인

해 줘야 됩니다 그럼 여기 이렇게 70 에 추가가 됐기 때문에 오심을

기준에서 보면 모두가 하나가 큐브가 된 거니까 50 의 왼쪽 서브 트리와

50 의 오른쪽 서브 트리를 비교를 해 줘야 되거든요 그러면 지금 5시

매매 축들이 는 아무것도 없기 때문에 이때 높이는 - 일이 되고 50 의

오른쪽 버튼은 높이는 영이 되서 결국 - 길이 50 에 밸런스 팩터 가

되는 거잖아요 그러면 - 일은 av 의 처리가 밸런스 팩터 로써 가질 수

있는 값의 이기 때문에 그럼 여기서 따로 테리를 재조정할 필요가 없는거죠

그럼 여기서는 이제 확인 작업이 끝난 겁니다 자 그래서 이제 이 상황에서

인스턴트 90 을 해보겠습니다 기본적으로 바이너리 서치 트리의

삽입과 똑같이 동작하는 했잖아요 자 그래서 90 가 50을 비교를 하는데

92 더 크니까 오른쪽으로 빠지고 사실 90 가 71 비교하는데 92

더 크니까 이제 이 위치에 92 생성이 되겠죠 그래서 이런 식으로

생성이 된 다음에 지금 우리는 avl 트리 를 맞는데 했다네요 그러니까

여기서 더 밸런스 팩터를 확인을 해 봐야 됩니다 지금 현재 이 빛의

노드가 추가가 되기 때문에 이제 여기서부터 밸런스 팩터를 확인 해

보면 되겠죠 자 그러면 먼저 7시 4 밸런스 팩트 확인을 해 보며 70 의

왼쪽 서브 트리의 는 아무것도 없고 오른쪽 서브 트리의 는 하나가 있기

때문에 왼쪽 서버 틀의 높이는 - 일이고 오른쪽 서브 트리 는 높이가

0 이어서 - 이래서 0 을 빼면 최종적으로 - 되고요 그러면 2 -

일은 av 에 트리에서 가질 수 있는 값이 이기 때문에 70원 이제 통과를

합니다 쉘 세븐 이제 통과를 했고 그 다음 이제 오심을 확인 해 주는데

50 의 왼쪽 서브 트리 나 아무것도 없잖아요 그런데 오른쪽 소프트리 를

보면 은 얘는 높이가 일이에요 그러면 왼쪽 소프트리 에는 아무것도 없었기

때문에 - 일이고 오른쪽 버튼은 높이가 일이었으니까 말러 실에서 1을

빼면 - 이거 되잖아요 저 50에 밸런스 패턴은 - 2 가 된다는

것이고 이것은 avl 트리 에 특징을 만족시키지 않는 현상이 발생을 한

거죠 뭘 하는 순간 이렇게 된거냐 로 90이라는 노드를 추가를 하게 된

순간 이렇게 된거죠 그럼 이제 이 상황에서 는 제 조정을 해줘야 됩니다

균형을 맞춰줘야 되는 거죠 그럼 이 상황을 잘 보면 이 노드의 4 변론

스펙터 가 - 2 가 나왔기 때문에 이 노드에서 지금 균형이 깨진

거잖아요 그러면 은 50을 기준으로 어떻게 균형이 깨져 냐 오른쪽

오른쪽으로 균형이 깨진 합니다 즉 오른쪽으로 왼쪽으로 지금 트리가 편

왕이 된 상태라고 볼 수 있는거죠 그래서 이 상황에서 얘를 어떻게

구조를 제 조정해 주면 다시 균형 잡힌 그러니까 높이 차가 최대 1

차이가 나게 만들 수 있을까요 여기서 중요한 부분은 뭐냐 며 지금 우리가

만들고 있는지 avl 트리는 이진 탐색 트리의 한 종류라는 겁니다 즉

무슨 말이냐면 이제 균형을 잡아줄 건데 균형을 재조정 한 뒤에도 이

바이너리 서치 트의 특징은 그대로 유지가 되어야 된다는 점이죠 그러면

이 바이너리 서치 트리의 특징 이 뭐냐 우리가 계속 반복해서 확인하는

것처럼 이 바이너리 서치 트리는 모든 노드에서 자신의 왼쪽 서버 트리는

자기보다 작은 값을 가지고 자기의 오른쪽 서버 트리는 자기보다 큰 값을

가지는 거라고 했잖아요 그러면 지금의 이 구조에서 어떻게 재조정을 해주면

바이너리 서치 틀의 특징을 그대로 유지하면서도 노비 차를 다시 줄일 수

있을까요 곰곰히 생각을 해 보면 결국 이 72 가운데에는 있어야 됩니다

그저 70은 가운데로 계속 있으면서 70의 현재 위치를 살짝 바꿔주면 될

것 같다는 생각이 듭니다 어떤 식으로 오냐 며 이렇게 70 의 위치를 위로

올려주면 되는거죠 여기까지 요 이 70을 50 위로 올려주면 어떻게

되냐 이런 형태의 구조가 될 겁니다 그래서 보시면 이렇게 70을 51

올려 줌으로써 이제 70 의 왼쪽 자녀는 50이 되고 70에 오른쪽

찬열은 92 됩니다 이걸 예쁘게 정리하면 은 이런 모양이 되죠 이런

모양이 되는 순간 이제 이 높이 차이는 더 이상 2개 이상으로 차이가

나지 않죠 70 을 기준으로 보면 밸런스 팩터 가 0이 되는 이렇게

이브에 트리의 특징을 만족하도록 바뀌었다는 것을 확인하실 수 있습니다

그래서 걔네 쉽게 설명 드린다 고 2 70을 이렇게 위로 올림으로써

바이너리 서치 트리의 구조를 만족하면서 동시에 avl 트리 에

특징도 만족할 수 있도록 바꿨다 이렇게 설명을 했는데 이걸 이제

일반적으로 교관 4 에서는 어떻게 설명을 하냐면 아까 원래 이런 구조

했잖아요 이걸 이런식으로 로터 헤드 시킨다 라고 얘기를 해요 왼쪽으로 로

테이트 시켜서 결구 이 구조를 이런식으로 만들었습니다 그래서

왼쪽으로 이렇게 노 테이트 시켜준다 이렇게 얘기를 합니다 어쨌든 다시

정리하면 이 70을 위로 올려 줌으로써 이제 있 우리는 av 에

트리의 특징을 만족한 의 형태가 됐구요 그러면서 동시에 바이너리 서치

트리의 특징도 유지하게 되는 거죠 자 그럼 예를 이제 좀 더 이쁘게

가운데로 옮겨 보겠습니다 자 이런 상황에서 인써트 20 을 해보겠습니다

얹어 20권 루트 노드 인 71 비교를 하는데 72 더 크죠 그럼

60은 왼쪽으로 빠지고 그럼 다시 이식과 50을 비교를 하는데 52 더

크기 때문에 이 위치에 22 들어가게 될 겁니다 그래서 이 위치에 이제

22 생성이 되구요 이제부터 밸런스 팩터를 뻑 확인을 해 봐야 되겠죠

혹시 av 에 트리의 특징인 깨지지 않았는지 확인을 해 봐야 됩니다

그러면 지금 이 위치에 추가가 됐기 때문에 벨런스 팩트를 확인 해봐야

되는 부분을 여기서 또 되겟죠 왜냐하면 은 20여개 추가 됐으니까

높이 의 영향을 받는 부분은 여기서부터 일 테니까요 그럼에 50에

밸런스 팩트 를 구해보면 지금 왼쪽 서버 트리는 노드가 하나가 있고

오른쪽 서버 트리는 노드가 아무것도 없잖아요 그러면 왼쪽 소프트의 높이는

0 이고 오른쪽 서버 트리는 아무것도 없으니까 높이가 - 일인데 0에서 -

이럴때면 일이기 때문에 이 50에 밸런스 패턴 일이어서 데이브 에 툴의

특징을 만족하고 있습니다 자 그 다음에 이제 70 을 확인을

해봐야겠죠 왜냐면 70에 왼쪽에 이제 20 이라는 노드가 추가 됐으니까 2

71 왼쪽에서부터 트리 의 높이 에도 영향을 줬을 수도 있기 때문에 이

70도 확인을 해봐야 되는 겁니다 그러면 70에 밸런스 팩터를 보여

보며 이 왼쪽에서부터 리는 높이가 일이고 이 오른쪽에서 보트린은 높이가

0이죠 그럼 이래서 0 을 빼면 은 일입니다 즉 70에 밸런스 패턴의

일이고 얘네 이브에 트리의 특징을 깨지 않기 때문에 그럼 현재 지

처리에 구조는 av 에 트리의 특징을 모두 만족하고 있다고 볼 수 있기

때문에 따로 구조를 바꿀 필요가 없는 겁니다 그럼 이제 여기서 인스턴트

60 을 해보겠습니다 사실 루프 노드에서 이 채식과 육식을 비교합니다

62 더 작기 때문에 왼쪽으로 빠질 거고요 60 가 50을 비교하는데

62 덕소 그러면 이부분의 60 의 생성이 될 겁니다 자 그럼 이

상황에서 다시 또 100원 스펙터 를 확인 해 봐야 되겠죠 지금 여기에

축가가 된거 기 때문에 여기서부터 또 밸런스 팩트를 확인하는 겁니다 그러면

은 50에서 왼쪽에서 보트린은 이거 고 오시네 오른쪽 서버 트리는 이

거라서 좀 더 높이가 0 0 이기 때문에 여기서 영화 빼면 06 얘

내부의 추리의 특징을 만족하 줘 그러면 오심에 대해 환경이 끝났으니까

이제 70을 확인 합니다 자 그럼 70s 의 밸런스 패턴은 먼저 왼쪽

서버 트리는 높이가 일이구요 오른쪽 소프트리 높이가 0입니다 이래서 0

을 빼면 일이라서 71 밸런스 패턴은 일이기 때문에 얘도 lv 에 트리의

특징을 만족합니다 그럼 현재 이 구조도 마찬가지로 av 에 트리의

특징을 모두 만족하기 때문에 따로 구조를 조정해 줄 필요가 없습니다

여기서 다시 인설 때 30 을 해보겠습니다 그러면 채식과 30일

먼저 비교를 하죠 32 더 작기 때문에 왼쪽으로 빠질 거 구요 50가

30 을 비교해서 32 더 작기 때문에 또 왼쪽으로 빠질 겁니다

20과 30일 비교를 하는데 32 더 크기 때문에 이게 이 위치에 32

들어가게 될 거에요 자 이렇게 32 추가가 됐습니다 그리고 이제부터 또

밸런스 팩터를 확인 해야 되겠죠 지금 1 비치의 추가가 됐기 때문에

여기서부터 밸런스 팩트를 확인을 합니다 왜냐하면 노드 추가 여기 니까

이제 높이에 영향을 받기 시작하는 부분에 20부 파이기 때문인 거죠

그러면 20에 밸런스 팩트를 먼저 빼보면 20m 왼쪽 더 보트린은

아무것도 없으니까 - 일이고 20 의 오른쪽 서부터 리는 노드 하나가

있으니까요 해 줘 그러면 - 이래서 0 을 빼면 - 일인데 얜 avl

tree 특징을 만족한 이까 얘는 괜찮습니다 그럼 이제 계속 거꾸로

올라가는 거죠 이제 50에 밸런스 팩트 를 확인해보면 50m 왼쪽 서버

트리는 높이가 일이구요 50 의 오른쪽 소프트리 눈높이가 용입니다

그럼 이래서 0 을 빼면 일이기 때문에 오심에 밸런스 팩터 도

일이어서 얘도 avert 특징을 만족을 합니다 그러면 이제 마지막으로

70 을 기준으로 확인해볼게요 70에 밸런스 팩트 를 구해보면 얜 왼쪽에

서버 트리는 높이가 이구요 오른쪽에서 보트린은 높이가 0 입니다 그럼 이해

사형을 빼면 이잖아요 그럼 이 70에 밸런스 팩터 는 이 가 나왔기 때문에

얘는 avl 트리 특징을 깨 버린 거죠 자 그러면 이 70 을 기준으로

어떻게 균형이 때 드는지를 분석을 해야 되는데요 보시면 왼쪽 서버

트리는 높이가 이였고 오른쪽 소프트리 높이가 이용이 얻자 나요 그 다음에

이 왼쪽 서버 트리에서 모피 2 를 만들게 된 경로는 이 이렇게 되는

경로인 거 잖아요 그럼 결국 왼쪽 왼쪽으로 기울어져 있다고 보시면

됩니다 그래서 70 을 기준으로 요기 를 기준으로 균형이 깨졌고 왼쪽

왼쪽으로 편이 된 상태라고 그렇게 보시면 됩니다 그러면 왼쪽에 왼쪽으로

편향된 이 상태를 어떻게 조정을 해주면 되느냐 지금은 노드가 많지만

결국 71 기준으로 편향이 된 이 세 개의 노드에 우선 집중을 해 주면

됩니다 이 세 개의 노드를 기준으로 재조정 만 해주면 되는 거거든요

그럼에 어떻게 제조 적을 하면 될까 지금 보시면은 얘만 깍 때 내서 보면

이런 식으로 지금 기울어져 있는 거잖아요 그래서 지금 높이 차가 2

가 난 것처럼 보이기 때문에 이 높이 차가 이건 않은 것을 높이 차가 더

적게 1 2 하부 차인 하게끔 바꿔주면 되는 거라서 그러면서 동시에

또 바이너리 서치 트리의 특징을 만족할 수 있도록 바꿔주면 되는

거라서 이거 앞에서 이미 해봤던 거잖아요 이 상황에서 는 얘만 이렇게

위로 올려주면 되는거죠 왼쪽 그림을 기준으로 설명을 하며 이 50을 위로

이렇게 올려 주면 되는 겁니다 자 그래서 50을 이렇게 70 위로 올려

주게 되며 51 이 위치에 오게 되구요 이제 5 실에 오른쪽 찬열의

72 되고 50 의 왼쪽 짜면 22 됩니다 그러면 기존의 원래 5 실에

오른쪽 잘렸다 60 은 어떻게 되냐 얜 70 의 왼쪽 자녀가 60을

가르치면 되는 거죠 원래 이 70 의 왼쪽 자녀는 2 50 을 가르치고

있었는데 5시를 이렇게 위로 올라가면서 70 의 왼쪽 자녀는 이제

비어 있게 되는 거잖아요 그렇게 비어있는 자리에 원래 50 의 오른쪽

자녀 였더니 60을 2 70 의 왼쪽 자녀가 가리키게 만들면 되는 겁니다

어렵지 않죠 그래서 결국은 똑같습니다 카페 했던것은 비슷한데 지금 이런

형태로 표현이 되어 있었잖아요 이런 형태로 편향되어 있는 것을 어떻게

하면 av 에 2d 의 특징을 만족할 수 있도록 높이 차를 줄일 수 있나

그러면서 동시에 바이너리 서치 트리의 특징을 깨지 않을 수 있나 이거는

생각을 해보며 지금 이런 형태에서 중간값을 이렇게 위로 올려서

최종적으로 는 이러한 형태를 만들어 주면 그러면 얘는 바이너리 서치

추리의 특징을 만족하면서 도 동시에 avl 트리 에 특징도 만족시킬 수가

있게 되는거죠 그래서 저는 이야기 쉽게 설명하려고 이 가운데 위치 니노

2 얘가 이제 이 3개의 값들 중에서 는 중간 값을 거니까 얠 이렇게 위로

올려 줘서 이런 형태로 만들어 주면 된다고 이제 설명을 했지만 교사의

서해 펨 대로 이제 설명을 하면 이런 식으로 평양이 되어 있을 때 얘를 제

조정하기 위해서 오른쪽으로 이렇게 로 테이트를 시켜 주면 된다고 얘기를

합니다 그래서 오른쪽으로 이렇게 로 테이트를 시켜주며 이제 가장 위에

있는 이제 아래로 내려오게 되면서 지금 아래와 같은 요런 모습을 띠게

되는 거죠 자 어쨌든 다시 정리를 하면 50 이라는 값을 위로 올려

줘서 구조를 재조정을 한다 그러면 내가 지금 약간 보기 어려우니까

예쁘게 다시 조정을 해 보며 이런 형태로 트리가 이제 만들어 줄 거에요

자 예를 이제 가운데로 쪼끔 더 보겠습니다 이 상태에서 이제 딜리트

이심을 해보도록 하겠습니다 지금 avl 트리는 바이너리 서치 트리

항공료 라고 하기 때문에 기본적으로 삭제도 바이너리 cm 트리에서 삭제

하는 거랑 똑같아요 그러면은 먼저 50과 21 비교를 합니다 그런데

22 더 작으니까 뇌는 쪽으로 빠지게 되고 여기서 이제 20 을 찾게

되잖아요 그럼 a21 이제 상태를 해주고 20 짜리를 뭔가로 메꿔 줘야

되는데 그 20에 오른쪽에 있다 이 30일 위쪽으로 올려 주면 되겠죠

그러면 최종적으로 이런 모습이 됩니다 원래 30 자리에는 이제 비어 있게

되는 거고요 그러면은 이제 삭제가 발생을 했으니까 avl 트리 에 특징

2 깨지지 않았는지 확인을 해봐야 되잖아요 그러면 어디서 부터 확인을

하면 되냐면 이 자리에 32 있던게 사라진 거니까 여기서부터 밸런스

팩터를 확인 해야 되는 거죠 그러면 먼저 삼 11 밸런스 팩트 를

확인해보면 30 의 왼쪽 서부터 리에는 아무것도 없고 오른쪽 서브

트리의 도 이제 이따가 없어졌기 때문에 둘 다 그러면 얘는 높이가 -

1 - 2 되는 거라서 30에 100원 스펙트럼의 0이 되는 거고요

그러면 이 부분에 대한 확인은 끝이 났죠 이제 그러면 루트 노드 까지

거꾸로 올라가면서 확인을 하는 거니까 이제 50에 3 밸런스 팩터를 또

확인을 해 봐야 됩니다 당연하겠죠 왜냐면 여기에 있던게 사라지면서 2

50 의 왼쪽 서버 트리 의 높이에 영향을 줄 수 있기 때문인 거죠 자

그러면 50 의 왼쪽 4 보트린은 노드가 딱 하나 있기 때문에 높이가

0 이구요 50 의 오른쪽 4부 트리는 지금 보시는 것처럼 일이기

때문에 0에서 이렇게 되면 최종적으로 - 일이 나와서 50에 배면

스펙트럼은 - 이라는 것을 알 수 있습니다 그러면 이노 2에서도 avl

트리 의 특징을 만족하는 거니까 그러면 전체 트리도 av 에 트리의

특징을 만족하고 있는 거죠 자 그래서 삽입이 든 삭제된 사비를 끝나거나

삭제가 끝난 뒤에 항상 avl 트리 에 특징 2 깨지지 않았는지 밸런스

팩터를 확인함으로써 점검을 해 줘야 되요 그러면 지금부터는 속도감 있는

진행을 위해서 균형 잡기가 발생한 경우에만 밸런스 팩트를 보여드리도록

하겠습니다 그러니깐 기본적으로 삽입 삭제할 때는 항상 배변 스펙터 를

확인을 해야 되지만 이제 지금부터는 너무 자세하게 설명을 하진 않구요

실제로 밸런스가 깨져서 트리를 재료적 해줘야 되는 상황일 때만 역시 적으로

밸런스 팩터를 확인하도록 하겠습니다 자 그럼 이제 빠르게 진행을 하기

위해서 10 55 65 를 차례대로 한번 넣어보겠습니다 그러면 10부터

넣으면 먼저 10과 51 비교를 하는데 52 더 큰 이터 왼쪽으로

빠지고 다시 10과 30일 비교를 하는 데 실이 더 작기 때문에 이쪽에

12 생기겠죠 이 쪽에 힘이 생기고 나서 당연히 30가 50에서 밸런스

팩트를 확인해봐야 됩니다 그런데 확인해봐도 따로 밸런스 깨지지 않았기

때문에 지금부터는 벨라 스펙터 확인하는 부분은 빨리 스킵을 하고

넘어가는 거에요 자 그럼 이번에는 55 를 넣어보면 먼저 50가 55를

비교를 하면 55 가 더 크니까 오른쪽으로 빠지고 70 가 5 10월

비교를 하면 55 가 더 찾기 때문에 왼쪽으로 가지고 55 와 61 비교

하면 또 55 가 더 작기 때문에 이번 위치에 55 가 생성이 될

겁니다 그리고 나면 60 70 50 에서 밸런스 팩트 확인을 해봤는데

따로 균형이 깨지는 않았기 때문에 이제 바로 이어서 65 를 넣어

보도록 하겠습니다 그러면 50과 65 를 비교해서 60억 아토피가

오른쪽으로 빠지고 65 와 71 비교를 해서 65 가 더 작기 때문에

왼쪽으로 빠지고 60 과 65 를 비교해서 65 가 더 크기 때문에

이제 이 위치에 60억 생성이 될 겁니다 그리고 나서 밸런스 팩터를

60에서 70에서 50에서 확인하지만 따로 균형이 깨지지 않았기 때문에

이것도 이제 넘어가겠습니다 자 그럼 이 상황에서 딜리트 30 을

해보겠습니다 사태 라는 것도 바이너리 서치 트리에서 삭제하는 것과

기본적으로 똑같다고 했죠 그러면 먼저 50과 30일 비교를 하는데 오시게

더 크니까 왼쪽으로 빠지고 여기 위치해서 30 을 발견했습니다 그러면

이제 이 30일 삭제를 하게 되는 거잖아요 30 월 삭제해 주고 나서

지금 보시면 30 의 왼쪽 자녀의 12화 많이 있기 때문에 이 10월

이제 30 에 차례로 올려 줘야 됩니다 그러면 이제 12 위치에 있게

되는 거죠 여기서 이제 밸런스 폐를 어떻게 확인을 해야 되냐면 원래 이

위치에 10의 있다가 이 위치에 통에 삭제가 된거 기 때문에 그러면은 이

위치에서부터 높이에 영향을 받게 되는 거잖아요 원래 이 위치에 있던 12

사라진 거니깐요 그래서 이제 실내 밸런스 팩트를 구해 보도록 할게요

20에 밸런스 이펙터는 보시면 왼쪽에 서버 트리 아무것도 없고 그래서

높이가 - 일이죠 그리고 오른쪽 4부 트리 해도 아무것도 없습니다 그래서

높이가 - 일입니다 그러면 최종적으로 이 시대 밸런스 패턴을 0이 되는

거고 얘 av 의 트리의 특징을 만족합니다 그럼 이제 이어서 50에서

의 밸런스 팩트를 벗고 해 봐야 됩니다 그러면 50m 왼쪽 서버

트리는 이렇게 있는데 걔는 높이가 0이죠 그리고 5 실에 오른쪽 서브

트리 가 있는데 얘는 높이가 입니다 그러면 0에서 1을 빼면 - 2 가

되서 50에서 밸런스가 깨져 버린 거죠 그럼 이제 얘는 재조정을 해줘서

이 높이 차를 다시 추려 줘야 됩니다 그럼 이때 이제 어떻게 줄이는 야

먼저 50을 기준으로 어떤 형태로 밸런스가 깨져 있는지를 확인 해야

돼요 지금 그러면 50을 기준으로 왼쪽 허버트 리는 높이가 0 이고

오른쪽 거버 트리는 높이가 이라서 밸런스가 깨진 건데 그러면 이

50이라는 입장에서 밸런스가 어떤 식으로 깨져 냐 2 50 의 오른쪽

버튼 의해서 높이 2 를 만들게 된 경로를 찾아 보면 이런 형태로 오른쪽

서브 트리의 높이가 2가 된 거잖아요 그래서 이 경우에는 오심 을 기준으로

오른쪽 왼쪽으로 편향된 상태라고 볼 수 있습니다 그러니까 이런 식으로

편향이 되어 있는거죠 그러면 얘를 어떻게 조정을 해줘야 다시 높이 차를

줄일 수 있을까요 일단은 지금 이 세 개의 노드에 만 측정을 해 봅시다 이

세 개의 노드 만 따로 떼서 그려보면 얘는 지금 이런 형태를 띄고 있는

거잖아요 그러면은 역시 이 부분도 재조정을 해줄때 바이너리 서치 트리의

특징을 깨지 않으면서도 동시에 av 에 트리를 만족하도록 높이 차를

줄여야 되는 거거든요 그러면 2 3 개의 값 중에서 일단 가운데 크기의

값을 가지는 것은 이 60 입니다 2 62 지금 가운데 값을 가지기 때문에

예 위치 가지 가운데에서 바꿔서 나는데요 그러면서도 동시에 avl

트리 특징을 만족하려면 결국 가전 아래쪽에 있는 이 60을 가장

위쪽으로 올려 주면 됩니다 그래서 최종적으로 아래와 같은 이런 형태로

만들어 주면 바이너리 사체 트리의 특징도 유지하고 avl 트리 에

특징도 만족시킬 수가 있는 거죠 근데 지금 예 같은 경우에는 좀 특징 2

뭐냐면은 50을 기준으로 어떻게 표현되어 있냐면 오른쪽 왼쪽으로

편하게 되어 있는 거잖아요 그래서 가장 아래쪽에 있는 것을 가장 위로

올려 줘야 되는 상황이 거에요 앞에서 봤던 것은 높이 적으로 봤을 때의

가운데 있는 것을 한 단계 위로 올려주면 됐던 거지만 지금은 가장

아래에 있는 것을 가장 위로 올려야 되기 때문에 두 단계를 위로 올려야

되는 거죠 그래서 얘를 지금 전에 설명하기 편하게 이렇게 한번에 설명

했지만 실제로 구현해 관점에서 혹은 교과서대로 fm 대로 설명하면 어떻게

해줘야 되냐면 60을 50 위로 올리면 되는데 9 10의 관점에서 주

단계를 통해서 이 작업을 해줘야 됩니다 그러면 첫번째 단계로 뭐냐면

이 60을 50과 74회 를 올려줍니다 그러니까 무슨 말이냐면

지금 이런 구조로 되어 있는데 이 구조를 fm 대로 설명하면 요트 게

있잖아요 이 두개를 오른쪽으로 회전 시켜서 일차적으로는 이런 형태로

만들어 줍니다 그래서 이걸 먼저 해보며 지금 60을 이 빛을 올렸죠

61 이치로 올려주면서 원래 이 위치에 있을 때 60 에 왼쪽 자녀

했다니 55 는 여전히 이제 60 의 왼쪽 자녀가 됐는데 62 원래 위치에

있을 때에 오른쪽 자녀 노드 예는 이제 72 가르켜 두게 됩니다

왜냐하면 이제 60이 위로 올라갔기 때문에 이제 60에 오른쪽 차려

노드는 최 12 되었기 때문이에요 그래서 어쨌든 이런 식으로 일차적으로

구조를 재조정 해주고요 그래서 일차적으로 조정된 이 모양을 예쁘게

정리를 하면 요런 모양이 되구요 자 그러면 이 상태에서 두 번째 단계로

다시 한번 60을 50 위로 올려야 됩니다 그러니까 이제 정리를 하면 이

거에요 원래 처음 모양은 이런 모양이 없고 여기서 얘를 맨 위로 올리는

과정을 에펨 대로 설명할 때 두 번에 걸쳐서 진행을 한다 했습니다 그래서

아래쪽이 2개 노드를 오른쪽으로 로 테이트 시키는게 1차 고요 그래서

지금 이런 모양으로 만들어 졌죠 이 상태에서 2차로 해줘야 되는 게

뭐냐면 다시 한번 예를 임의로 올려줘 여기서 이 위로 올려 준다는 것은

에펨 으로 말하면 이번엔 왼쪽으로 로 테이트를 시켜 된다는 말이고 그러며

최종적으로는 어떤 모양이 되냐면 이런 모양으로 만들어 주게 되는 겁니다

그래서 이제 두 번째로 해줘야 되나요 작업을 이제 해보는 거죠 그래서 이제

60을 50 위로 올려 주도록 하겠습니다 그러면 62위 7 까지

올라가게 되고 이제 60 의 왼쪽 자녀는 52 데모 60에 오른쪽

찬열은 아까 앞에서 조정 있기 때문에 여전히 70이 됩니다 그러면 원래 이

위치에서 6실 왼쪽 자녀는 옷이 보였었는데 60 이제 위로 올라가면서

2 55 는 오신 의 오른쪽 자녀가 되게 됩니다 그러면 이제 이 모습을

예쁘게 정리를 하며 최종적으로 이런 형태가 되는 거죠 이렇게 바꿔 주고

나서 보며 이 트리는 lvl 트리의 특징도 만족하고 여전히 바이너리 서치

트리의 특징도 만족하고 있다는 것을 아실 수 있습니다 자 이제 57 을

넣고 또 90을 삭제를 해 볼게요 먼저 57 을 넣으며 60 가 57

비교하는데 50p 리더 작으니까 왼쪽으로 빠지고 50가 57 을

비교하는 데 57 더 크니까 오른쪽으로 빠지고 55 57 을

비교하는 데 57 더 크니까 이 위치에 57일 들어가게 될 겁니다

그리고 나서 우 15 50 60 에서 밸런스 팩트 확인을 해 봐야 되겠죠

밸런스 팩터를 확인해봐도 균형이 깨진 게 아무것도 없었기 때문에 바로 이제

넘어가겠습니다 이제 90을 삭제를 해 볼게요 그러면 먼저 육식과 90을

비교를 하는데 92 더 크니까 오른쪽으로 빠지고 90 가 71

비교하는데 92 더 크니까 또 오른쪽으로 빠졌습니다 여기서 이제

90 을 발견한 거죠 그럼 현재 90 리프 노드 니까 그냥 바로 삭제를 해

주면 됩니다 삭제를 해 주고나서 밸런스 팩트를 확인을 해 봐야 되겠죠

이 위치에서 삭제가 됐기 때문에 높이에 영향을 줄 수 있는 위치는

여기서부터 여서 70에서 밸런스 팩트를 확인하고 또 60에서 밸런스

팩트를 확인을 했지만 둘 다 밸런스가 깨지지 않았기 때문에 구조를 조정할

필요가 없는 거죠 그래서 최종적으로 는 이런 형태의 트리가 됐습니다 이제

딜리트 60을 해볼게요 2 60 을 찾아야 되는데 60 2층 루트 노드의

있잖아요 그럼 예를 이제 삭제를 해줘야 되는 겁니다 그러면 계속

설명을 드리지만 이 상태라는 것은 파이널에서 제트 리 해서 삭제하는

것과 똑같다고 했잖아요 그러면 일단 61 삭제를 해 주고 나서 지금

60은 자녀가 이기 때문에 육신의 오른쪽 서브 트리 해서 가장 작은

값을 60에 자리에 올려 주면 된다고 했잖아요 그러면 여기서 가장 작은

값은 65기 때문에 60 월의 60 에 차례로 올려 주면 됩니다 그러면

은 65 는 이제 60 차례로 옮기게 되고 원래 65 가 있던 자리는 이제

비워 줘야 되는 거죠 자 그러면 원래 65 가 있던 차례는 이렇게 비워

지게 되고 원래 62 있던 자리에 이제 60억 올라왔어요 그러면 이제

여기서 밸러 스펙터 를 어떻게 보여야 되냐 최종적으로 보면 이 위치에

있던게 삭제가 탱 거기 때문에 그러면 삭제가 됐을 때 높이에 영향을 받을

수 있는 것은 여기서부터 잖아요 그래서 7 10부터 밸런스 팩트를

확인을 해 봐야 됩니다 그러면 70의 왼쪽 서브 트리의 는 아무것도 없고

그래서 높이가 - 일이죠 그리고 최 실의 오른쪽 소프트리 해도 아무 것도

없기 때문에 얘도 높이가 - 이리해서 이 채식을 밸런스 팩터를 0이 되고

얘는 av 에 트리의 특징을 만족합니다 그러면 이제 60 의

밸런스 팩트를 확인을 해 봐야 되겠죠 그러면 60 의 왼쪽 서버 트리는

높이가 이고 65 에 오른쪽 소프트리 는 높이가 0 이기 때문에 얘는

밸런스 팩트가 이거 돼서 얘는 균형이 이제 깨져 버리게 된 거에요 그러면

이제 균형을 맞춰주는 작업을 해줘야 되는 겁니다 자 그러면 65 에서

어떤 식으로 밸런스가 깨져 있는지 먼저 확인을 해봐야겠죠 65 에서

밸런스가 왼쪽 오른쪽으로 깨졌다는 것을 볼 수 있습니다 즉 65 를

기준으로 왼쪽 오른쪽으로 편향이 된 상태인 거죠 그러면 얘도 이제 구조

조정을 해줘야 되는데 이 3개만 때 놓고 딱 보면 지금 이런 형태로

평양이 되어 있는 거잖아요 그러면 얘를 바이너리 서치 트리의 특징을

유지하면서도 높이 차를 주려면 가장 아래에 있는 얘를 가장 위로 올려주면

됩니다 그러면 이 구현에 관점에서 얘도 정석대로 라며 먼저 55를 51

5 올린 후 그러니까 여기까지 일차적으로 먼저 올린 뒤에 그렇게

구조를 잡아 주고 나서 다시 한번 이 55를 65 b 로 올리는 식으로

그러니까 여기 위까지 올리는 식으로 균형을 잡아 줘야 하는데요 지금은

개념적으로 속도감 있게 진행을 하기 위해서 50으로 한번에 65 위로

올려서 그러니까 이런 식으로 한번에 올려서 좀더 빠르게 균형을 맞춰

주도록 하겠습니다 원래는 fm 대로 라면은 이 두 개를 왼쪽으로 돌려

주고 그래서 이런 구조를 먼저 만들어 준 뒤에 다시 한 번 이런식으로

오른쪽으로 돌려서 그러니까 여기서는 이런 식이 겠죠 오른쪽으로 돌려서

최종적으로 이런 형태를 만들어 줘야 되는데 지금은 이제 빠르게 진행을

하기 위해서 그냥 한번에 2위까지 2 올려서 준영을 잡아 주도록 하겠습니다

그러면 55를 2b 로 한번에 쭉 올리면 어떤 모양이 되냐 55 가

여기까지 올라왔기 때문에 이제 50 의 왼쪽 자녀 노드는 50이 되고

50 의 오른쪽 자녀 노드는 65 가 됩니다 그러면 원래 55 에 오른쪽

자녀 노드 였다고 17은 누가 가르쳐 해야 되냐면 기존의 50으로 위로

올리기 전에는 65m 왼쪽 자녀 노드가 55 했는데 이게 50 어이

위까지 올라가 쓰니까 이제 65m 왼쪽 자녀는 비어 있게 되는 거잖아요

그러면 이제 이에 비어있는 60 의 왼쪽 자녀 노드를 기존의 55 에

오른쪽 차렸던 2 57 을 가리키도록 바꾸어 주면 되는 겁니다 그래서

지금이 들쭉날쭉한 이 모양을 예쁘게 정리를 하면 이런 식의 모양이 되는

거죠 자 이 상황에서 이제 삭제 2개를 해 보겠습니다 먼저 57

삭제를 하게 되면 이제 좀 더 빠르게 해 볼게요 예를 이제 삭제를 하면

되는 거죠 이렇게 삭제를 하고 나서 65 와 55에서 밸런스 팩트를

차례대로 확인하는데 두다 균형이 깨지지 않았기 때문에 이제 바로 다음

단계로 넘어가서 70 을 삭제를 하면 얘를 이제 삭제를 하게 되는 거죠

예를 사퇴를 하고 나서 이제 다시 65 와 55에서 차례대로 밸런스

팩트를 확인을 하게 되는데 여전히 균형이 깨지지 않았기 때문에 또 로

구조를 조정해 줄 필요는 없고 최종적으로 이런 모양이 됩니다 이

상황에서 21 삽입을 하게 되면 위치 22 들어 가게 되거든요 그러면 21

놓고 나서 이제 밸런스 펠트를 확인을 해 봐야 되죠 그러면 지금 이 위치에

삽입 있기 때문에 밸런스 팩터를 확인하는 것은 여기서부터 해줘야

됩니다 그러면 10에서 밸런스 팩트를 확인을 했더니 - 일이 나와서 avl

트리 의 특징을 만족을 했구요 50에서 또 밸런스 팩트를

확인해봤더니 이때 2가 나왔어요 그러면 얘는 균형이 깨진 거잖아요

그러면 이제 이 50을 기준으로 밸런스를 새로 잡아 줘야 됩니다 그럼

야지 50을 기준으로 어떤 때 균형이 깨져 있는지 살펴 보면 왼쪽

오른쪽으로 균형이 깨진 상태 자네요 그러니까 왼쪽 오른쪽으로 편향이 된

상태이기 때문에 얘를 해결해 주려면 어떻게 해주면 되냐 지금 이 세계를

기준으로 구조를 조정해주는 거기 때문에 가장 아래 두개 있는 20을

가장 위로 올려주면 됩니다 그래서 이런 모양으로 만들어 줘야 되는 거죠

그런데 최종적으로 22 가운데가 올 거고 왼쪽을 10 오른쪽이 52 될

겁니다 그럼 완성된 형태는 20 15 10 이런 형태가 되는 거죠 그리고

나서 여기서 끝이 아닙니다 여기서 균형이 완성이 됐다 고 끝이 아니에요

지금 이 에 위치해서 밸런스 팩트를 확인해서 조정을 해 주기 때문에 옷이

뭐 에서도 밸런스 팩트를 확인을 해줘야 됩니다 그래서 최종적으로

55에서 밸런스 팩트를 확인해봤더니 왼쪽 버터 리는 높이가 일이 오른쪽

소프트리 는 높이가 0이니까 이래서 0 을 빼면 최종적으로 이 55 에

밸런스 팩트 이렇게 되는거죠 그래서 얘 밸브의 트리의 특징을 만족하기

때문에 여기서는 이제 구조조정을 따로 해줄 필요가 없는겁니다 지금은 균형이

깨지지 않았지만 어떤 경우에서는 여전히 균형이 깨져 있을 수도 있기

때문에 우리 토 노드 까지 밸런스 팩트를 다 확인을 해줘야 된다는거

이걸 꼭 기억을 해 주시면 좋을 것 같아요 자 그래서 이제 정리를

하겠습니다 avert 에서 400 혁재 를

한다는 것은 기본적으로 avl 트리 가 바이너리 서치 트리가 한 경력이

때문에 루트 노드에서 적절한 위치 카지 찾아가서 그 위치에서 삽입 혹은

삭제해 주면 되는 거구요 하지만 그렇게 해주고 나서 av 에 트리의

특징 2 해주지 않은 좀 확인을 해 줘야 되기 때문에 삽입 혹은 삭제가

발생한 위치에서부터 루트 노드 로 거꾸로 올라오면서 밸런스 팩트를

확인을 해 주고요 만약에 밸런스 팩트를 확인을 했더니 균형이 깨졌다면

재조정을 해줘야 된다는 거 이 과정을 루트 노드 까지 꺼꾸로 올라오면서

해줘야 된다는 거 이것만 잘 챙겨주면 avl 트리 가 어떻게 통 작

하는지를 제대로 이해 하실 수 있을 거에요 자 끝으로 avl 트리 에

시간 복잡도 와 장단점을 살펴보도록 하겠습니다 이 avl 트리는

기본적으로 바이너리 서치 트릭이 때문에 베스트 케이스와 해 브리즈

케이스는 같습니다 하지만 뭘 스 케이스가 바이너리 서치 트리의 비해서

개선이 된거예요 바이너리 서치 트리의 3월 스트 케이스는 삽입 삭제 검색

모드 비고 앤 이었다며 이제 lvl 트리는 균형을 되게 엄격하게 맞춰주기

때문에 최악의 경우에도 삽입 삭제 검색 의 시간 목적 또는 5로 그의

바이너리 서치 트리의 비해서 이런 장점이 있다라는 것을 기억 을

해주시면 좋을것 같구요 하지만 단점이 있는데 엄격하게 트리의 균형을

유지하기 때문에 삽입 삭제를 할 때마다 추리의 균형을 확인하고 만약에

균형이 깨졌다면 처리 구조를 재조정하는 이를 리츠 운로드 까지

올라가면서 반복적으로 하기 때문에 차벽 삭제를 할 때마다 시간이 꽤

소요된다는 그런 단점이 있습니다 그래서 이 문제를 이라는 것이 레드

블랙 트리 인 거구요 그래서 우리는 다음 시간에 레드 블랙 트리에 대해서

살펴 볼 거고 레드 블랙 트리와 av 에 트리를 비교하는 것은 다음 시간에

같이 정리하도록 하겠습니다 자 오늘 영상의 여기까지구요 최근에 제가 목이

대단히 안좋아 가지고 한도가 영상을 올리지 못했습니다 그래서 영상을 좀

더 자주 올려 드려야 되는데 그렇게 하지 못해서 죄송하다는 말씀을 드리고

싶구요 그리고 트리와 관련해서 실제로 배경도 개발을 할 때에 이 트리를

실제로 구현하거나 셀리 그렇게 많지는 않지만 그래도 컴퓨터 공학의 기본적인

개념이고 기술 관련 문서를 일다 보면은 여러번 트리 라는 내용이

투쟁을 하기 때문에 그리고 실제로 다음번에 다루게 될 레드 블랙 트리

같은 경우에는 잡아 싶을 c 샵 뭐 이런 곳에서 많이 쓰거든요 얘를

이해하고 있으면 좋을 거 같다는 생각이 들어서 여러개 차에 걸쳐

설명을 하고 있구요 알고 계시면 분명히 앞으로 기술 문서를 읽거나

관련 코드를 볼 때 도움이 될거라 생각을 하기 때문에 이 부분도

관심있게 계속해서 봐주시면 좋을 것 같습니다 자 끝까지 봐 주신 모든

분들 정말 최고 오시구요 저는 그럼 다음 영상 레드 블랙 트리를 준비하러

가보도록 하겠습니다 감사합니다