BJ.29 이진탐색트리(binary search tree)를 설명합니다~ 트리를 순회하는 방법들, 이진탐색트리의 삽입/삭제/검색 동작도 설명합니당 :) - ko

네 반갑습니다 오늘 이 영상을 끝까지 보신 후에 이진 탐색 트리 의 기본

개념과 트리를 순회하는 여러 방식들을 알게 되구요 그리고 이진 탐색

트리에서 삽입 삭제 검색하는 방식을 알게 됩니다 자 그럼 오늘도 고고씽

먼저 이진 탐색 트리의 기본 개념부터 살펴볼게요 이싱 탐색 트리 영어로는

바이너리 소스 트리 라고 하는데요 얘는 어떤 거냐 며 이 트리의 있는

모든 노드가 다음과 갖춘 특징을 가집니다 어떤 특징인 야 이 트리의

각각의 노드는 그 노드를 기준으로 왼쪽 서 버튼 있잖아요 그 노드의

왼쪽 소프트리 는 그 노드의 값보다 작은 각 들만 가지게 되구요 그리고

그 노드의 오른쪽 서 버튼 있잖아요 그 오른쪽 썩어 트리는 그 노드의

값보다 큰 딱 등만 가진다 이런 특징을 가지는 추리가 이진 탐색 트리

라고 보시면 되겠습니다 그래서 왼쪽 그림을 보시면 먼저 이 루트 노드

한번 볼게요 1 루트 노드의 22 라는 값이 있잖아요 22 라는 값을

기준으로 오른쪽 서브 트리의 있는 모든 값들을 보면 50 30 사실 이

모든 게 20 이라는 값보다 크잖아요 그리고 반면에 20 이라는 노드의

왼쪽 서버 트리를 볼게요 그러면 5 35 10 17 얘네들이 모두 이

10보다 작은 값들이 잖아요 그래서 20 이라는 노드를 기준으로 왼쪽

서브 트리의 있는 노드들은 모두 이 10보다 작은 값들을 가지고 있고

오른쪽 서부 털의 있는 노드들은 모두 20 보다 큰 값을 가지고 있다는

것을 볼 수 있습니다 그런데 이런 책 찌니 이 루트 노드의 만 그런 것이

아니라 이틀에 있는 모든 노드가 같은 특징을 지닌다 는 의미에요 그래서

하나하나 살펴보며 가령 5번의 경우에 이 5번 왼쪽 사보 틀이나 3 밖에

없는데 이 삼은 5 보다 작은 거잖아요 그리고 반면에 오른쪽 서브

트리의 는 15 10 17 있어서 애가 모두 보다 탕 값이 믈 확인할

수 있습니다 그러면 이번에는 50을 기준으로 왼쪽 서브 트리 는 34

10 이라는 값을 가지고 있어서 얘는 5 10보다 작은 값이 잖아요 그리고

5시를 오른쪽 서부터 리는 없기 때문에 한번 따로 확인할 게 없고요

이번에는 15번 노드를 한번 살펴볼까요 15번 노드의 왼쪽 서버

트리는 10이라는 노드를 가지고 있는데 얘는 15 보다 작은 값을

가지고 있죠 그리고 오른쪽 소프트리 는 17일 라는 값을 가지고 있는데

얘는 15 보다 큰 값을 가지고 있죠 마찬가지로 30분 노도 살펴보면 총

10분 노드 뇌 축사 부터 리가 없으니까 일단 제끼고 오른쪽 서브

트리를 살펴보면 이 42 라는 값은 30부 같은 값이 이기 때문에 30번

노드 역시 오른쪽 서버 트리는 3 10보다 큰 땀만 가진다는 것을

확인할 수 있습니다 그 외에 3번 10번 17번 48 을 왼쪽 오른쪽

아무것도 없기 때문에 따로 확인할 것이었고 그래서 결국 지금 보시는 요

트리에 있는 모든 노드 모든 노드들은 자기 자신의 왼쪽 서버 트리의 는

자기 자신보다 작은 값들 많이 있고 자기 자신의 오른쪽 소프트리 에는

자기 자신보다 큰 것들만 잇다는 것을 확인할 수 있습니다 그래서 이런

특징을 가지는 트리를 이진 탐색 트리 영어로는 바이너리 서치 트리 라고

한다 이렇게 이해를 하시면 될 것 같아요 이게 이진 탐색 트리 의 핵심

이구요 모든 것은 이것을 기준으로 진행을 하기 때문에

요 특징을 잘 끼어 카고 이해하시는 게 대단히 중요합니다 자 그래서 이진

탐색 트리의 이런 특징을 바탕으로 여러가지 동작들을 해 볼 수 있는데요

먼저 이진 탐색 트리의 최소값을 찾는다 며 이 최소값은 바이너리 서치

트리의 가장 왼쪽에 있습니다 왜냐하면 은 모든 노드는 자기 자신의 왼쪽에는

자기 자신보다 작은 것들을 가지고 있기 때문에 최소값은 찾아가려면 루트

노드를 기준으로 계속 왼쪽 왼쪽으로 가면 되는 거거든요 그래서 이태리

같은 경우에는 최소 값이 3이 될 거구요 반면에 이 이진 탐색 트리에서

최대값을 찾으려면 그 트리의 가장 오른쪽으로 찾아가면 됩니다 이

파이널이 사치 캐리의 특징 2 각 노드의 오른쪽은 자기보다 큰 것들만

가지기 때문에 계속 그런 쪽으로만 가면 이 바이너리 서치 트리의

최대값을 만날 수 있는거죠 그래서 이 루트 노드에서 오른쪽으로 계속 가야

되는데 지금은 루트 노드를 기준으로 오른쪽으로 갈 수 있는게 딱 한번

밖에 없었어요 그래서 이 경우에는 이 52 이 바이너리 서치 트리 에서는

최대 값이 된다 그렇게 이해를 하시면 될 것 같습니다

자 그러면 이번에는 이 파이널이 쌓지 트리를 순회하는 방법 여기서 뒤

내라는 것은 무슨 말이냐면 이 바이너리 sc 트리에 있는 모든

노드를 한번씩 방문하는 것을 의미합니다 그런데 이렇게 순회하는

방식에는 여러 가지 방식이 있는데요 바이너리 서치 트리 해서는 주로

사용되며 수준의 방법이 뭐냐면 이 노트를 우리말로는 중이 순이라고

합니다 얘는 어떻게 종적을 하냐며 출발은 항상 루트 노드에서 시작을

하죠 그러면 이 루트 노드를 기준으로 왼쪽으로 계속합니다 왼쪽으로 계속

갖다가 더 이상 왼쪽 서브 트리 가 없으면 그때 현재 노드 를 방문하고

그래서 값을 출력 을 한다던지 그 노드에서 해줄 일들을 한 뒤에 그

다음에 그 노드의 오른쪽 서브 트리 로 가서 오른쪽 부터 해서 다시 긴

5도 트래버스 를 하는 식으로 그런 식으로 동작하는 방식을 이루어 더

들여 볼수 라고 해요 말로는 무슨 말인지 잘 이해가 안 되실 거라서

왼쪽 그림을 통해서 한번 살펴보도록 하겠습니다 출발은 항상 루트 노드에서

시작을 하겠죠 그러면 20번 노드에서 출발하는데 일단 왼쪽으로 가고 다시

그럼 5번 노드에서 또 왼쪽으로 갑니다 그럼 3번 노드 해봤어요 근데

3번 노드에서 왼쪽이 없잖아요 그러면 이제 2 3번 노드를 방문 하는

겁니다 그래서 2 3번 이라는 값이 출력을 해 주고 그 다음에 또

오른쪽으로 가야 되는데 오른쪽이 없어요 그럼 이제 3번 오대산에 해줄

것이 더 이상 없기 때문에 2 3번 노드에서 이 노트에 벌써 를 맞추고

이제 올라옵니다 그러면 이 5번 노드 입장에서는 이 5번 노드의 왼쪽 서브

트리의 대한 수 내가 끝난 거 잖아요 그럼 이제 5번 노드를 방문을 합니다

그래서 5라는 값을 출력 을 해주고 이제 이어서 오른쪽 서버 털이 로

가는 거죠 그래서 15 분노 들어갔는데 25분 노드에서 다시 또

왼쪽 소프트리 를 갑니다 그래서 10분 노드의 왔어요 근데 10분

노드는 왼쪽이 없잖아요 그러면 결국 이제 10번 노드를 박물 합니다

그래서 10 이라는 값을 출력을 해 주고 그다음에 10분 노드의 오른쪽

소프트리 로 가야 되는데 오른쪽이 없기 때문에 결국 20번 노드에 대한

주는 끝난 거거든요 그럼 이제 거꾸로 올라옵니다 그러면 15 * 노드로

다시 돌아왔어요 15분 노드 입장에서 보면 25번 노대의 왼쪽으로부터 레

대학 시내가 끝난 거기 때문에 이제 15분 노드를 방문 해 주고 결국

15 라는 값을 출력해 줍니다 그렇게 출력을 해 주고 이제 10억원 노드의

오른쪽 서브 트리를 가는 거죠 17번 되어 봤는데 17번 노드의 왼쪽 이

없어요 그럼 이제 27번 오더를 방문해 해주고 17회 라는 값을

출력합니다 6 17 여 오른쪽으로 가야 되는데 오른쪽이 없기 때문에

결국 17에 대한 이론도 트래버스 는 끝이 난 거고 이렇게 거꾸로

올라옵니다 그러면 10억원으로 다시 올라왔는데 15분 기준에서 보면

15번의 오른쪽 서버 트리에 대한 순으로 끝난 거니까 결국 이제 15번

에 대한 수 뇌도 끝인 거죠 그러면 다시 15분에서 이렇게 5번으로

올라갑니다 마찬가지로 5번 해서도 오른쪽 서브 트리의 대한 순응 가

끝난 거기 때문에 결국 5번의 되었음에도 끝난 거라서 다시 이렇게

올라가요 그럼 20분으로 올라왔는데 20번 기준에서는 20번 노드의 왼쪽

소프트리 에 대한 순응을 끝난 거니까 이제 20번 노드를 방문 합니다

그래서 22 라는 값이 출력을 해 주고 다시 오른쪽 서브 트리를

확인하고 가야 되겠죠 50번 5 들어왔고 50번 노드의 왼쪽 있기

때문에 사실 왼쪽으로 갑니다 30번 5 들어 왔어요 근데 30분 노

데려오면 주기 없죠 그럼 이제 30분 노드를 방문을 하는 겁니다 이렇게

30 이라는 것을 써 주고 그 다음에 이제 38 오른쪽 서브 트리 로 가야

되는데 오른쪽 서브 트리 가 있으니까 일단 이렇게 내려가요 40번 오더

왔습니다 40번 오더라 왼쪽에 없어요 그럼 이제 자기 자신의 방문을 하고

자식 이라는 값이 써 줍니다 그리고 40은 오른쪽으로 가야 되는데

오른쪽이 없죠 그럼 이제 사실에 대한 순애는 끝난 거기 때문에 이제 거꾸로

올라 옵니다 그래서 30분 노드로 다시 올라왔는데 이제 30분 노드는

오른쪽 서브 트리의 대한 순애 까지도 끝나는 거잖아요 그러면 결국 30분에

대학 t 너도 끝난 거라서 다시 또 올라가죠 그러면 이제 다시 50번 5

들어왔는데 50분 노드 입장에서는 50번 노드의 왼쪽 서브 트리의 대한

수 내가 끝난건 일단 이제 자기 자신을 방문을 합니다 그래서 50

이라는 값이 써 주고 그 다음에 이제 50번 의 오른쪽 서버 트리로

가야되는데 없잖아요 그러면 결국은 50번 노드에 대한 수요도 끝난 거죠

그러면 다시 이렇게 올라옵니다 이제 20분 오도로 다시 돌아왔어요 20번

노드 입장에서는 20번 노드의 오른쪽 서 부터 d 까지 도 다수 뇌가 끝난

겁니다 그 말은 즉 20분 노드는 루트 노드 니까 전체 이 바이너리

서치 트리에 대한 순위가 끝났다는 말이 되는 거죠 그래서 이렇게 내가

끝이 난 뒤에 2 출력 순서를 딱 봐보세요 이 바이너리 서치 트리에

있는 노드들의 값들을 순서대로 방문을 한 거잖아요 그래서 좀 깔끔하게

정리를 해보면 이노 트럭을 쓰라는 것은 바이너리 서치 트리에 있는

값들을 순서대로 방문을 하게 된다는 특징이 있다 그래서 이걸 그림으로

쉽게 표현하며 지금 이렇게 일찍 써있습니다 여기는 출력 순서 라고

했는데 노드 방문 순서라고 봐도 될 거에요 그러면 이 바이너리 서치

트리에 있는 각각의 노드를 일직선 상위로 이렇게 점사를 따라서 이렇게

투영시켜 보면 그 투정 되어 있는 순서대로 그 순서대로 방어를 하게

된다는 것을 알게 됩니다 이게 이 노트에 발생해 특징이다 라는 것

그렇게 이해를 하시면 될것 같구요 사실 e 로드 트래버스 는 바이너리

서치 툴이 에서만 쓸 수 있는게 아니라 일반적인 트리 에서도 쓰일 수

있는 개념이 에요 그러니까 일반적인 트리 에서도 그 틀에 있는 노드를 한

번씩 방문하기 위해서 이루어 트래버스 가 사용될 수 있습니다 그리고 이

이름도 체력을 수 말고도 여러가지 쓰는 방법이 있는데요 대표적으로

프리오더 와 포스터 보드가 있습니다 얘도 잠시 살펴보고 넘어갈게요

프리오더 들어갈 때는 뭐냐면 우리말로는 전의 순회 인데요 얜 현재

노드를 무조건 먼저 방문합니다 그리고 왼쪽 서버 트리스 내가 끝나면 오른쪽

서부터 주시네요 이런식으로 동작을 하는 거에요 그래서 예를 들어서

살펴보면 항상 루트 노드에서 먼저 시작하죠 그러면 일단 20 을 먼저

방문을 하는 겁니다 그래서 이렇게 20 을 적어 주고 그다음에 왼쪽 한

다음에 바로 얘를 박물 해요 그래서 이렇게 5번이 출력을 하게 됩니다

비우고 나서 다시 왼쪽으로 가요 그 다음에 예를 바로 방문 해요 그래서

3번을 출력을 하게 되는 거구요 그 다음에 더 이상 방문할 것이 좌우

아무것도 없기 때문에 끌어올 나오겠죠 거꾸로 올라와서 이번에는 제

오른쪽으로 갑니다 그리고 나서 예를 일단 먼저 박물 해요 그래서 15를

출력을 하게 되고 그리고 나서 다시 왼쪽으로 가서 바로 10번을 또 방문

해요 이렇게 출력을 해 주고 10번을 기준으로 좌 우가 아무것도 없기

때문에 그럼 이제 이런 식으로 올라 오겠죠 그러고 나서 오른쪽으로 또

박물 합니다 그래서 바로 예부터 출력을 해 줘요 시체를 출력을 하고

17도 좌우가 아무것도 없기 때문에 그럼 거꾸로 흘러 겠죠 그리고 15

에 대한 수 너도 이제 끝이 났으니까 다시 올라오고 마찬가지로 5번 에

대한 손에도 끝이 났으니까 다시 올라옵니다 그리고 이제 20 을

기준으로 오른쪽으로 가야 되겠죠 오른쪽으로 가서 얘를 일단 방문을

해요 그래서 50을 출력을 해 주고요 그 다음에 50의 왼쪽으로 갑니다

그래서 30일 일단 바로 박물 해요 이렇게 출력을 해 주고 30의 왼쪽은

없기 때문에 그러면 이제 오른쪽으로 갑니다 41 바로 방문 해요 얘를

출력을 해 주고 사실 왼쪽 오른쪽 따 없기 때문에 이제 거꾸로 올라오는

거죠 그러면 30 에 대한 처리가 다 끝난 거니까 얘도 다시 꼴로 올라오고

그 다음에 50에 오른쪽이 없기 때문에 그럼 50도 선애가 끝이 나서

이렇게 거꾸로 올라오는 겁니다 그래서 이제는 출력 순서가 이런식으로

되는거구요 이게 프리오더 드려보겠습니다 그러면 이제 포스터도

틀어 벌써 를 살펴보며 얘는 왼쪽 무조건 간 다음에 왼쪽에 끝이 나면

그 다음 오른쪽으로 또 무조건 가고 이 두개가 모두 끝이 나면 그 현재

노드를 박물 하는 방식이에요 그래서 예를 통해서 살펴보면 얘도 일단 루트

부터 먼저 시작을 하겠죠 루트 노드에서 일단 왼쪽으로 먼저 가요

먼저 간 다음에 3번 노드에서 왼쪽에 없잖아요 그럼 오른쪽도 없잖아요 그럼

이제 3번 노드를 방문하는 것도 그래서 이렇게 3번을 출력을 해 줘요

그리고 이제 3번 모드에 대한 순회 가 끝났으니까 이제 올라오죠 올라와서

이번에 왼쪽 에 대한 것이 끝났으니까 이제 5번을 기준으로 오른쪽으로

갑니다 오른쪽으로 가서 다시 또 왼쪽 있으니까 왼쪽으로 가요 10번 오드

까지 왔는데 10분 노드에서 왼쪽 오른쪽 다 없잖아요 그럼 이제

10번을 방문하는 겁니다 그래서 이렇게 10번을 출력을 해 주고 그

다음에 이제 그럼 올라 오겠죠 15번 노드로 다시 올라와서 이번에 로

오른쪽으로 일단 가요 오른쪽으로 가서 17번 노드를 방문했는데 얘도

왼쪽으로 아무것도 없기 때문에 그럼 이제 17번 노드를 방문을 합니다

그래서 이렇게 출력을 해 주고 다시 이렇게 올라와요 15분 노드에 대한

오른쪽 처리가 끝났기 때문에 이제 15분 을 방문합니다 그래서 이제

10억원을 출력을 해 주고 그러고 나서 이제 15분 에 대한 전체

순위가 끝났으니까 다시 또 거꾸로 올라옵니다 5번 노드에 대한

오른쪽부터 리가 끝나고 올라 온 거니까 이제 5번도 들을 방법 해요

그래서 이제 뭐 번 노드를 출력을 해 줍니다 그러고 나서 다시 또 꼴로

올라와요 20번 노드 까지 올라 왔는데 여기서 이제는 다시 오른쪽으로

또 가야 되겠죠 오른쪽 노 들어가서 이고 싶어 노드를 기준으로 왼쪽 서부

t&d 가 있기 때문에 또 내려갑니다 그리고 30분 노드를 기준으로 왼쪽은

없죠 그러면 이번에는 오른쪽으로 바로 가요 그래서 40분 5 들어왔는데

왼쪽 오른쪽이 다 없기 때문에 이제 40분 노드를 방해 합니다 그래서

40번 출력을 해 주고 팔리다 했으니까 이제 다시 올라오죠 그러면

30번 노드를 기준으로 30번 의 오른쪽 소프트리 에 대한 쓰니까

끝나기 때문에 이제 30분 노드를 방문 해요 그래서 30번 출력을 하고

그러면 30분 노드에 대한 승리가 끝났으니까 다시 올라오고 그러면

50번 노드를 기준으로 다시 오른쪽 서부터 이걸 봐야 되는데 오른쪽

소프트 리가 없잖아요 그러면 결국 오른쪽 소프트 리가 없으니까 이제

자기 자신의 방문을 합니다 그래서 50을 이렇게 출력을 해요 그러면

결국 오심에 대한 수요도 끝난 거라서 이제 이렇게 꼭 들러 5 겠죠 그러면

20번 노드를 기준으로 오른쪽 서버 트리에 대한 수요도 다 끝나서 올라

온 거니까 이게 드디어 20번 노도 방문을

합니다 이제 22 라는 값이 출력을 하게 되는 거죠 어렵지 않죠 그래서

이런 식으로 포스터도 트래블 쓰는 동작을 한다 이해를 하시면 될거

같습니다 자 그럼 이제 수뇌 에 대해서는

살펴봤으니 까 다시 돌아와서 노드의 써클 애써 우리말로는 후임자 라고

하는 개념이 있습니다 이건 뭐냐면 어떤 임의의 노드에서 큰 5도에

각보다 는 큰 노드들 중에서 가장 값이 작은 노드 예를 그 노드의

소스에서 혹은 후임자 라고 부르게 됩니다 예를 들어서 자 20에서 필슨

뭐가 되냐 20원 지금 여기 있잖아요 그럼 예약석 센서로 뭐가 되냐 며

10보다 큰 값들이 있는 노드들 중에서 가장 작은 노드를 찾는 겁니다

그러면 얘기가 되는거죠 그래서 이 실에서 3에서는 30이 됩니다 그럼

이번에는 17의 석세스 않은 뭐가 될까요 17 이렇게 퓨웅 재료 본

다음에 그 다음에 요 쪽에 있는 것들이 오른쪽에 있는 것들 중에서

가장 작은 값을 찾으면 되는 거잖아요 그러면 22 되는 거죠 그래서 17화

속에서는 22 되는거구요 이번에 10s 센서를 찾아보겠습니다 20에서

센서는 또 이렇게 쭉 선을 그어 준 다음에 예 오른쪽에 있는 부분이겠죠

큰 값들 중에서 가장 작은 다 바로 15 분이죠 실외 석세스 는 15가

됩니다 그럼 이번에는 바이너리 서치 트리 해서 노드의 패다 쎄서 우리말로

나선 인자 라는 개념이 먼저 살펴볼게요 이 개념 낚아 석쇠 사랑은

반대되는 개념인데 요 en 어드 큰 노드 보다 값이 작은 모두들 중에서

그 중에서 가장 값이 큰 노드를 그 노드의 패더 쎄쎄쎄 라고 부릅니다

그래서 예를 들어서 20번째 프라다 3 서는 뭐냐며 얘를 기준으로 이제는

작은 값들이 니까 작은 것은 여기에 있죠 이 중에서 가장 카피 니까

17일 되는거죠 그래서 20% 더 세스는 17 되는거구요 이번에는

10의 필요도 센서를 찾아보겠습니다 10은 여기 있잖아요 예 보다 작은

값이 여기에 있는거고 여기를 기준으로 이정록 에서 가장 튼 노드를 찾는

거니깐 요가 되는 거죠 그래서 결국 10f 레더 3 서는 뭐가 되구요

사실 애플의 덧셈을 뭐가 되냐 이외 왼쪽에 있는 영역에서 가장 값이 큰

것 그러면 저 산은 32조 그래서 사실 애플의 더 세서 는 32 된다

그렇게 이해를 하시면 될것 같습니다 자 이제 그러면 이진 탐색 트리에서

삽입 삭제 검색이 어떻게 되는지를 살펴볼 건데요 이진 탐색 트리 의

특징 있잖아요 그러니까 이미 의 노드에서 왼쪽 서버 트리는 자기보다

작은 딱 둘만 있고 오른쪽 버터링 자기보다 큰 커플만 있다라는 요 사실

이 특징을 잘 기억만 해주시면 삽입 삭제 검색이 되게 쉽게 이해가 되실

수 있을 거에요 자 그럼 이제 예를 통해서 한번 살펴보겠습니다

자인 썰도 의식을 하게 되면 어떻게 되냐 일단은 아무것도 없는 상태이기

때문에 50이라는 노드 생성 을 해주면 되겠죠 그래 이런식으로 이제

50이라는 노드를 생성 해줬습니다 얘가 이제 루트 노드 같았구요 이

상태에서 이 솔트 70 을 하면 어떻게 되냐 그러면 먼저 70 검

50을 비교를 해야 되겠죠 그런데 75 50 보다 크기 때문에 이

50에 오른쪽으로 빠져야 될겁니다 그래서 최종적으로 는 이런 식으로

트리가 형성이 될 거에요 이제 이 상태에서 인술 또 90을 하면 어떻게

될까요 그러면 다시 루트 노드에서 출발 하겠죠 90은 50 보다 크기

때문에 오른쪽으로 갈 거고 그럼 다시 70 이란 91 비교를 하는데 92

70 보다 크기 때문에 이젠 이 자리에 92 생성이 될 겁니다 자

이렇게 구식이 추가가 됐구요 이 상태에서 다시 인설 더 99를 하면

어떻게 되냐 그럼 50 이란 99로 먼저 비교를 해야 되겠죠 근데 99가

더 큽니다 그럼 이쪽으로 와요 그럼 72 라고 다시 99 를 비교합니다

99가 더 큽니다 이쪽으로 와요 구실이란 99 를 비교합니다 99가

더 큽니다 그럼 이쪽으로 입니다 즉 90의 오른쪽에 99가 생성이 되겠죠

그래서 이런 형태를 띠게 될 겁니다 이 상태에서 이제 80 에 추가를

하게 되면 루트 노드 와 81 비교해서 82 더 크니깐 오른쪽으로

보고 거기서 다시 82 70 보다 크기 때문에 더 오른쪽으로 빠지고 또

다시 또 82 라쿠 11 비교를 하는데 92 더 크기 때문에 이번에

왼쪽으로 빠져야 될겁니다 그래서 현재 이런 상태가 됐구요 여기서 이제

30일 넣어보겠습니다 그러면 50과 30일 비교를 하는데 52 더

크잖아요 그럼 왼쪽으로 빠져야 되겠죠 이 자리에 32 들어가게 될겁니다

여기서 다시 40 을 넣으면 어떻게 될까요 그러면 다시 40 걸 루트

노드의 값과 비교를 하는 4 52 더 큰 2탄 왼쪽으로 빠져야 되고요

30과 40을 비교하는데 사실이 더 큰 2타 이번에는 오른쪽으로 빠져서

이 위치에 생성이 될 겁니다 여기서 다시 쏠트 이식을 하게 되면 이식과

50을 비교해서 52 더 크니까 왼쪽으로 빠지고 20과 30일

비교해서 32 더 크니까 이번에도 사실 왼쪽으로 빠져서 아비치 22

생성이 될 겁니다 이런식으로 생성된 상태에서 이번에 삭제를 해 보도록

하겠습니다 이 4짜 라는 것은 사실 결국 삭제를 하려면 삭제하려는 노드가

있는지 검색을 해야 되잖아요 그래서 일차적으로 먼저 검색에 일어나고 그

삭제하려는 것이 트리의 있으면 그때 삭제를 하게 되는 겁니다 그러니까

결국은 삭제가 검색을 동 말한다는 것 그래서 삭제를 잘 이해하면 검색은

당연히 자연스럽게 이해가 된다는 것 요거를 기억해 주시면 좋을 것 같아요

자 20을 한번 사체를 해보겠습니다 그러면 먼저 또 루트 노드에서 출발을

하겠죠 20 걸 루트 노드 인 50과 비교를 하는데 22 작자 나요

아프리카 왼쪽으로 빠지고 다시 20과 32 비교를 하는데 22 30 보다

작기 때문에 또 왼쪽으로 빠집니다 근데 여기서 이제 20 을 발견

했잖아요 그럼 예를 이제 치워 주면 되는데 지금 예는 리프 노드 라서

아물어 자녀가 없기 때문에 얘는 지우는게 쉽습니다 그냥 이렇게

날려주면 되요 그러면 여기서 날려 준다는 말은 구현 상으로는 이삼십

노드의 왼쪽 차일드 왼쪽 차일드 를 원래는 20 이라는 노드를 가르치고

있었는데 이젠 아무것도 가리키고 있지 않다는 너를 대입을 하게 되는 거죠

그래서 자녀가 업로드를 사퇴를 할 때는 삭제될 노드 를 가리키던

레퍼런스를 가리키는 것이 어떤 처리를 해주면 되는 거예요 방금 보신

이런식으로 말이죠 자 그래서 사체를 했더니 이런 형태가 됐습니다 이

상태에서 이제 t l 30 을 해보겠습니다 그러면 30 을 찾으러

가야 되잖아요 다시 루트 노드는 필요로 합니다 35 10보다 작죠

그러면 왼쪽으로 빠지게 되구요 그런데 이제 여기서 30 을 찾게 된 거죠

그러면 이번 얘를 치워 주게 되는데 예를 주어 주려고 보니까 자녀가

하나가 있어요 이렇게 자녀가 나가 있는 상태에서는 어떻게 주어질 수

있냐면 이 30에 부모 노드는 50 있잖아 여기 52 바로 이 30일

자녀 노드 를 가리키도록 바꿔주면 됩니다 그래서 다시 정리를 하며

자녀가 하나의 노드를 삭제하는 경우에는 삭제될 노드 여기서 32조

삭제 달 노드를 가리킨다 레퍼런스 얘를 의미합니다 이 래퍼 라스를

삭제될 로드 예조 삭제될 노드의 자녀 자녀가 하나뿐인 경우입니다 이 자녀를

가리키도록 레퍼런스를 바꿔주면 되는 겁니다 그래서 삭제 다운로드의 자녀를

가르치는 레퍼런스를 변경을 한다 이렇게 이해를 하시면 될거 같아요

그러면 최종적으로 는 이러한 모습이 되겠죠 자 이 상태에서 딜리트 50

을 해보겠습니다 그럼 지금 루트 노드를 삭제를 해야 되는거 잖아요

근데 얘는 보면 자녀가 두 개 요 그럼 이 경우에 어떻게 동작을 해야

되냐 보통 이 경우에는 꼬리 투 노드가 아니더라도 이렇게 자녀가 개인

경우에는 이 자녀가 두 개의 노드를 삭제하려고 할 때 그 삭제할 노드를

기준으로 가장 간단한 방법은 뭐냐면 왼쪽 이면 왼쪽 오른쪽이 며 오른쪽

하나를 골라서 여기서 오른쪽에 할게요 오른쪽을 기준으로 오른쪽에 서 가장

작은 값을 50에 자리로 올려주면 됩니다 그러면 이 오른쪽에서 현재

가장 작은 것은 72 잖아요 그럼 그 70을 2 50 짜리로 올려주면

되는거죠 그래서 다시 정리하며 자녀가 둘이 노드를 사퇴를 하게 될 때는

사태를 노드의 오른쪽 지금 우리는 오른쪽 이라고 전해 줘 삭제될 노드의

오른쪽 서버 트에서 제일 값이 작은 모든 이 모두가 삭제될 노드를

대치하게 만들면 되는 거에요 만약에 오른쪽 서브 트리 가 아니라 왼쪽으로

전했다 며 철재 될 노드의 왼쪽 써 로트리 해서 제일 값이 큰 모드가

삭제된 노드를 대체하도록 하면 되겠죠 그렇게 해야만 하게 바이너리 써지

트리의 특징 2 그대로 유지가 될 테니까요 그래서 여기서는 결국 70을

이 자리로 올리게 되고 그러면 어떻게 되냐면 이런 형태로 트리가 만들어지는

겁니다 에러 지자 좀 더 이쁘게 만들면 요런 모습이 되겠죠 이

상태에서 85 를 추가해 보겠습니다 85 랑 70 이런 비교를 하게 되면

85 가 더 크잖아요 그럼 이제 이쪽으로 오게 되고 여기서 85 가

더 작은 2타 그럼 왼쪽으로 빠지게 되고 여기서 다시 85 가 더 크니까

이번에 오른쪽으로 빠져서 이 부분에 85 가 들어가게 될겁니다

이 상태에서 70을 지워 볼게요 일단 70 을 찾아야 되는데 공교롭게도 또

이제 루트 노드 인거죠 그러면 이 루트 노드를 삭제를 하게 되는데

그러면 우리가 카페 서정 했잖아요 삭제될 노드를 기준으로 오른쪽에 있는

값들 중에서 가장 값이 작은 값을 찾아서 개를 대체 시킨다고 우리 가정

했잖아요 그러면 70 을 기준으로 오른쪽에 있는 노드를 중에서 가장

값이 작은 것을 e82 이거든요 얘를 이제 이 쪽으로 올려 줘야 되는

겁니다 그래서 결국 80 n 이 위로 올라가서 이제 이 자리에 82 되고

애가 왼쪽은 40 오른쪽은 91 찬열을 가지게 된다 대신 aj 90

은 원래 81 가르쳤지만 이제 82 2 자리로 왔기 때문에 더 이상 81

가리키고 있을 순 없고 대신에 82 원래 가르키고 있었던 85를 이제

90 가르치게 된다 이렇게 이해를 하시면 되겠습니다 그래서 결국 여전히

상황에서 핵심은 자녀가 둘인 노드를 삭제를 할 때는 삭제된 노드의

오른쪽도 로트리 해서 제일 값이 작은 노드가 삭제로 노드를 대체할 수

있도록 한다 이렇게 이해를 하시면 되겠습니다 그래서 결국 딜리트 70

을 하게 되면 이런 모습을 띄게 되구요 얘를 다시 예쁘게 만든 요

이제 이런 형태가 되는 겁니다 그래서 결국 삭제를 할 때는 핵심이 되는 건

뭐냐면 삭제를 하고 나서도 여전히 바이너리 서치 트리의 특징 2 유지될

수 있도록 레퍼런스 조정만 잘 해주면 된다는 것 요거만 잘 기억을 해

주시면 될 것 같습니다 자 그러면 이진 탐색 트리의 시간

복잡도 는 어떻게 되는지 살펴보도록 하겠습니다 먼저 테스트 케이스 부터

살펴볼게요 삽입 같은 경우에는 가령 여기다가 백을 치고 논다 고 했을 때

대기 90 보다 크기 때문에 위치에 102 들어가게 되죠 그러면 이거는

상수 시간에 처리가 되기 때문에 이렇게 처리를 해 줬구요 그다음

딜리트 의 경우에도 살펴보면 이 루트 노드를 바로 지워버리면 얘를 지우고

이 87 이제 루트 노드 로 쓰면 되는 거니까 얘도 3 수시간 반으로

끝나게 됩니다 그리고 검색이 경우에도 만약에 구심을 찾는다고 하면 루트

노드에서 바로 찾을 수 있기 때문에 얘도 상수 시간 마디로 끝나게 되죠

그래서 데스 특히 쓰인 경우에는 삽입 삭제 검색 모두가 3 수시간 받은

끝난다는 것을 알 수 있습니다 그러면 이번에는 에버리지 케이스를 살펴 보면

이제 일반적인 경우를 살펴 보는 건데요 바이너리 서치 트리에서

일반적이라고 하면은 트레이에 있는 노드들이 어느 정도 균형을 맞춰서

퍼져있는 그런 형태로 의미하게 됩니다 그러니까 는 임의의 각 노드에서 왼쪽

서버 트리와 오른쪽 소프트의 높이 차이가 그렇게 크게 차이가 나지 않는

거죠 어느정도 밸런스가 잡혀 있는 그런 상태에서 이 시간 복잡도 라고

어떻게 될 것인가 이것을 분석하는 건데요 시간 복잡도 라는 것이 우리가

앞에서 배웠던 것처럼 젊 근접 방식을 통해서 분석을 하기 때문에 결국 이

트리의 놈들의 수가 무한 들어갔을 때 어떤 형태를 띠게 될까 이걸 분석을

하는 거거든요 그러면 결국 이 삽입 삭제 검색 이라는 것이 루트 노드에서

시작을 해서 오른쪽 서브 트리를 선택하든 후 왼쪽 서브 트리를

선택하든 선택한 쪽만 집중을 하고 선택하지 안쪽은 신경을 쓰지 않으면

되기 때문에 결국에는 젊 근접 방식에서 생각을 해보면 그 사이즈를

절반씩 줄여 나가는 걸로 이해를 할 수 있습니다 그리고 그렇게 사이즈가

절반씩 출연하게 되면 결국 이 에버리지 케이스에서 삽입 삭제 검색

모드 길고 로그인을 띄게 되는 거죠 이게 사실은 좀 더 구체적으로 증명을

해야 되는데요 일단 이런 식으로 이해를 하셔도 우리는 없을 것

같습니다 이번에는 뭘 스케 있어요 최악의 경우를 생각해보면 최악의

경우에 일단 바이너리 서치 트리가 한쪽으로 이렇게 편안히 되어 있어야

돼 그리고 이 상태에서 이를 넣는다고 치면 그러면 이를 저장해야 되는

위치는 이끄 치거든요 요부분 이어 가지고 그러면 이 모든 노드를 한번씩

다 확인을 해줘야 되요 그래서 이 때 또 세탁 인해 되는거구요 그 다음에

딜리트 같은 경우에도 만약에 이를 삭제한 더 해볼게요 그러면 루트 노드

로부터 출발해서 욕까지 한번씩 다 확인 해봐야 결국 이 마지막에서

만나게 될 거니까요 그럼에도 결국 실험 목적 또 가 3 타인의 되는

겁니다 그리고 검색도 마찬가지로 만약에 이번에는 아예 존재하지

않을수도 예를 들어서 일을 찾는다 고 해 볼게요 그러면 루트 노드 로부터

출발해서 이 끝까지 다 확인을 해 봐야 되는 거잖아요 것까지 다 확인을

했는데도 이 일이 없음을 확인했기 때문에 이런식으로 만약에 검색을 하게

된다면 얘도 마찬가지로 이 트리의 있는 모든 노드를 확인을 해야 되서

시가 목적은 세트 해야 됩니다 자 그래서 방금 보신 내용을 바탕으로

이진 탐색 트리의 장점부터 한번 살펴볼게요 먼저 이진 탐색 트리의

장점은 삽입 삭제가 위험하다는 겁니다 예를 들어서 이 상황에서 지금 20

이라는 값을 넣는 더 붙이면 그냥 이 위치에 노드 하나 만들면 되는 거겠죠

그렇게 연결만 잘 시켜주면 될겁니다 만약에 30일 삭제로 한다고 해

보겠습니다 그럼 예를 삽질을 하게 되면 얘는 이런 식으로 그냥 연결만

해주면 되는 거라서 그래서 삽입과 삭제가 되게 유연 하다는 장점이

있구요 래퍼 라스 문제 조정해 주면 되는 거니까요 그 다음에 또 어떤

장점이 이냐 값의 크기에 따라서 좌우 서브 트리 가 나머지 기 때문에

400 삭제 검색 이 고통은 그러니까 일반적인 케이스인 거죠 이런 경우에는

따르다 그래서 아까 2번째 케이스 인 경우에는 비고 로그인이 시간 북적

되기 때문에 모든 노드를 다 확인할 필요가 없는거죠 그래서 이런 경우에

삽입 삭제 검색이 일반적인 케이스는 빠르다는 그런 장점이 있구요 그리고

값에 순서대로 쓰 내가 가능하다는 장점이 있습니다 우리가 앞부분에서

이루어 트래블 쓸 배웠죠 그래서 이 바이너리 서치 트리에 있는 각

노드들의 값들을 기준으로 순서대로 순회를 하고 싶을 때 크게 가능하다

그러니까 정렬된 형태로 접근이 가능하다 그런 장점이 있습니다 하지만

이진 탐색 트리의 단점이 있는데요 아까 앞에서 보셨던 건데 2월 스트

케이스 인 경우에는 삽입 삭제 검색 모두 세타 n 그러니깐 모든 소리의

있는 노드를 방문 해 줘야 되는 그런 단점이 있는 거죠 그러니까 이런

극단적인 케이스가 아니더라도 바이너리 서치 트리가 구조적으로 한쪽으로

편향이 되면 될수록 삽입 삭제 검색 등등 여러 동작들을 수행 시간이

악화된다는 그런 단점이 있어요 그래서 2월 스캔 상황에서 여러 동 적들의

성능이 악화되는 이 문제를 해결하기 위해서 스스로 균형을 잡는 이진 탐색

트리 가 개발되고 사용됩니다 대표적인 예로 avl 트리 가 있고 레드 블랙

트리가 있어요 그래서 얘네들은 워스트 케이스에 상황에서도 삽입 사택 검색이

모두 비골 로그인으로 처리가 됩니다 그러니까 성능이 개사기 된거죠 이

내용은 다음 영상을 통해서 소개 드리도록 하겠습니다

네 오늘 이렇게 바이너리 설치 트리에 대해서 설명을 드렸는데요 생각했던

것보다 설명해야 될 양이 많아지고 좀 고생을 했던 것 같습니다 지금 목도

좀 상태가 안좋은데 그래서 혹시나 영상을 보시다가 불편하셨다면 양해의

말씀을 드리구요 다음 시간에는 방금 말씀드렸던 것처럼 avl 트리 와

레드 플랙 트에 대한 내용들을 다루어 보도록 하겠습니다 자 끝까지 봐 주신

여러분들을 정말 최고 오시구요 저는 그럼 다음 영상을 준비 하러 가볼게요

감사합니다