Transcript for:
자료구조 03분반 10주차 - 해시 테이블을 통한 데이터의 적재

[음악] 자 수고하세요 여러분 반갑습니다 고려대학교 2023학년도 1학기 자료구조 03분반의 10주차 수업을 시작하도록 하겠습니다 저는이 강의를 맡고 있는 유용재구요 모두 반갑습니다 자 양해의 말씀을 먼저 하나 구하자면 원래 당초에이 영상이 11주차 영상과 동시에 올라가는 것이었습니다 근데 제가 아시다시피 건강 문제로 인해서 이렇게 영상을 찍는데 좀 문제가 있었습니다 목소리가 잘 안 나와서 그래서 부득이하게 요렇게 10주차 영상이 지금 업로드 된 것에 대해서 수강생 여러분의 양해를 진심으로 구하도록 하겠습니다 자 이번 주에 다룰 내용은 해시 테이블을 통한 데이터의 적재가 되겠습니다 뭔가 좀 새로운 키워드다라는 느낌이 드는 분들이 많이 계실 거예요 맞습니다 우리 이제까지 해시 테이블 얘기를 한 적이 없었고요 오늘 처음 하는 겁니다 처음 하는 건데이 해시태그를 굉장히 단순해 보이지만 굉장히 중요한 또 활용도가 높은 자료구조가 되겠습니다 해시태그이 뭔지 어떻게 데이터를 적재 그 원리를 살펴보기로 하고요 그 전에 저희가이 균형잡힌 트리 파트가 양이 좀 많다라고 말씀을 드렸어요 그래서 지난주 9주차에 살펴보았던 avl과 rb에서 조금 더 많은 내용들을 볼 필요가 있습니다 한 주에 모두 다를 수는 없기 때문에 그래서 남은 균형잡힌 틀의 내용들 먼저 살펴보고 그 뒤에 해시 테이블 내용으로 오늘 수업을 마무리해 보도록 하죠 자 오늘 말씀드린 대로 균형잡힌 트리와 관련된 내용을 먼저 살펴보도록 하겠습니다 저희가 avl 트리에 대해서 이론적으로는 바삭하게 배웠습니다 그 점 복습 한번 해 볼 건데 이론적으로 배웠는데 우리가 실제로 파이썬에서 어떻게 avh를 구현할 건지에 대해서는 못 살펴봤다라는 거죠 그래서 그 부분을 좀 챕터에서 살펴보기로 하겠습니다 코드가 좀 길어요 미리 말씀드리자면 코드가 좀 긴데 여러분 중간고사 봐서 이제 아시잖아요 우리 강좌에서는 코드를 외우거나 흐름을 암기하거나 그럴 필요가 전혀 없다고 코드 전반을 보고 아 avl이 이런 식으로 균형을 조정하는 걸 파이썬은 이렇게 하는구나라고 받아들일 수 있으면 또 돌려볼 수 있으면 되는 겁니다 결국 중요한 건 응용과 이해다라는 말씀을 다시 한번 드리고요 쉽게 얘기해서 우리 코드 봤던 거에서 빈칸 뚫어서 그걸 채워라 이런 건 안 나오는 거 알고 계시죠 자 두 번째 세 번째 챕터에서는 조금 생소할 수 있는 비트리에 대해서 보도록 하겠습니다 미안합니다 자이 비트리의 경우에는 똑같이 균형을 위한 틀린 건 맞아요 맞는데 아예 균형을 잡는 방식이 다릅니다 그리고 데이터를 쌓아 나가는 원리도 뭔지 그리고 어떻게 삽입을 수행하는지 정도만 단순하게 우리 avl과 레드 블랙을 깊이 있게 배웠기 때문에 비트리는 좀 가벼운 마음으로 살짝 다루도록 하고요네 번째 다섯 번째가 중요합니다 오늘의 중심 토픽이라고 할 수 있는요 해시 테이블이 뭐고 어떻게 데이터를 적재하며 또 핵심 문제라고 할 수 있는요 충돌을 해시 테이블은 스스로 어떻게 해결하는지 살펴보기로 하지요 자 플래시백을 해보도록 하겠습니다 avl 추리가 뭐였더라 avl3는 이진 탐색 트리 중에서도 스스로 균형을 조절하는 트리의 일종이었습니다 우리가 이진 탐색 트리가 있을 때 이진 탐색 트리가 가지는 필연적인 문제가 뭐라고 했더라 그냥 다짜고짜 데이터를 삽입하면 이런 식으로 트리가 형성될 수 있다라는 거죠 데이터가 4개면 여러분 상식적으로 어떤 트리를 팔아 이렇게 좌우로 쭉쭉 뻗어 나가서 로키가 좀 작은 트리를 희망하잖아 근데 이렇게 되면은 거의 데이터의 수 노드의 수랑 높이랑 정비를 하게 돼 버린다라는 거죠 이러면 안 된다라는 겁니다 그래서 우리가 이진 탐색 트리에서 핵심적인 건 균형 균형을 잡는 것 다시 말해서 이렇게 한쪽으로 휜 기울어진 트리가 아니라 화살표 친 것과 같이 어느 정도 좀 좌우가 균형 잡혀 있고 균형이 잡혀 있다는 건 다시 말해서 무슨 말 높이가 좀 큰 팩트하다라는 말 컴팩트한 높이를 가지는 드릴을 만들고 싶다라고 했습니다 그걸 위한 방안 중 하나 시초 호격이라고 할 수 있는 방안이 바로 avl 트리였다라고 말씀을 드렸고요 자요 avlte의 경우에는 노드를 삽입하는 거 자체는 잊은 탐색 트리에 그것을 그대로 따른다라고 말씀 되었습니다 그래서 89라는 노드를 자주색만 있는 상태에서 새로운 노드 89를 삽입하려고 했을 때 이진 탐색 3의 논리를 그대로 따른다라고 말씀을 드렸어요 41보단 크니까 오른쪽 45보다 크니까 오른쪽으로 82보다 크니까 오른쪽으로 가서 여기에 89를 자리잡게 된다라는 거죠 자 근데 핵심은 뭐야 이렇게만 하면 이진 탐색 트리랑 다를 바가 없어요 얘가 왜 특별하냐 왜 굳이 avl 이젠 탐색 틀이냐이 친구는 자가 균형 조정의 과정을 거친다라고 말씀을 드렸습니다 그래서 어떤 식으로 균형을 나름대로 판단을 한다 우리가 삽입된 노드 89가 제가 지금 체크한 대로 삽입이 되었죠 그러면 여기서부터 거꾸로 옆으로 올라가서 루트 노드에 이르기까지 균형이 심하게 깨진 곳이 있는지를 보자라고 말씀을 드렸습니다 균형이 그냥 깨진 것도 아니고 심하게 깨진거다 그거 판단 ef라는 값으로 판단을 했고요 얘는 아노피 빼기 우높이라고 말씀을 드렸습니다 좌 서브 트리의 높이 빼기 우서브 트리의 높이인데 자꾸 높이 높이 하면은 0부터 시작인지 1부터 시작했는지 헷갈리니까 내가 뭐라고 얘기했죠 가장 깊은 노드의 스텝 수라고 편의상 얘기를 했습니다 그래서 82를 기준으로 좌측과 우측의 깊이를 비교하면 80이 좌측에는 아무것도 없으니까 0이 깊이가 되고요 80이 오른쪽에는 89만큼 한 스텝을 갈 수 있으니까 1이 돼서 82기준 밸런스 벡터는 마일이 된다라고 얘기했습니다 자 마찬가지로 계산하면 45는 왼쪽은 0 오른쪽은 2니까 마리가 되고 41은 왼쪽은 하나 둘 셋 오른쪽은 하나 둘 셋 그래서 밸런스 벡터가 빵이 드는데 41까지 갈 필요도 없이 우리가 지금 뭐를 마주했어요 밸런스 팩터가 심하게 깨지면 여기서 멈춰야 된다니까 심하게 깨진다의 기준은 2에 도달하냐입니다 마이너스 2도 2입니다 절댓값으로는 그래서 절댓값이 2에 도달하는지를 판단해서 뭐 이에 도달해 그러면은 절대 두 눈 뜨고 볼 수가 없는 상황이다라는 거죠 그래서 우리가 어떤 식으로 조절을 했다 결국 이런 제가 금쪽이라고 이렇게 쉽게 쉽게 얘기를 했었죠이 금쪽이 다시 말해서 트리 균형의 문제를 일으키는요 친구는 결국 4가지 패턴 중 하나일 수밖에 없다라고 말씀을 드렸습니다 어떻게 이렇게 왼쪽으로만 두 번 뻗어 나가는 왼쪽 왼쪽 금쪽 좀 있다가 얘를 ll 금쪽이라고 얘기할 겁니다 왜 왼쪽으로 왼쪽으로 뻗었으니까 또 오른 오른 금쪽이가 있겠고요 왜 놀은 금쪽이가 있겠고요 오른 왼 금쪽이가 있겠습니다 이걸 벗어날 수는 없습니다요 밖에 것은 우리가 애초에 순열 조합의 원리에 따라 생각할 수가 없지요 그리고이 두 4가지 경우 중에서 지금 여러분 왼쪽에서 목도하고 있는 경우는 어떤게 있음요 케이스죠 오른 오른 금쪽 그래서이 오른 오른 금쪽이를 균형하기 위해서는 보통 시중고서라든지 학습자료에서는이 로테이션 가지고 설명을 하는데 우리 강좌에서는 좀 편하게 봤다고 말씀을 드렸습니다 어떻게 소개해 드렸어요 결국 균형이 안 잡힌게 문제 아니냐 그러면 이렇게 돼 있지 말고 이렇게 돼 있으면 좀 덧나냐 그러기 위해서는 82가 어디로 가야 된다 위로 가야 돼 45 89가 이렇게 가야 되는 건 당연한거다 이진 탐색 트리에 원리에 따라 끝 이렇게 우리가 금쪽의 균형을 조절할 수 있었다라는 거 여러분 기억하고 계실 겁니다 연습 문제도 많이 풀어 봤지요 자 그러면은 얘를 우리가 직접 구해 봅시다 자 근데 직접 구현하기 위해서는 일단 뭐라고 우리가 구조를 짜야 될까 자 크게 우리가 두 클래스를 좀 생각해 볼 필요가 있겠어요 자 얘를 파이썬으로 짠다고 굉장히 머나먼 과정입니다 거의 몇십 줄 써요 근데 여러분이 쓰는 거 아니잖아 우리 슬라이드로 슉슉 편하게 볼 거잖아 자 코드를 볼 건데 어차피 클래스는 두 가지로 구성될 수밖에 없을 것 같습니다 어떻게 notrass랑 abl 클래스로 나누어서 살펴봐야 되겠다라는 거죠 어 왜 굳이 둘로 쪼개요 그게 여러모로 편해요 자 노드 같은 경우에는 말 그대로 노드를 독자적으로 가리키는데만 클래스가 쓰입니다 즉이 친구는 생성자가 뭘 가지고 있어야 될 것 같아 일단가 40일 45 이런 걸 저장해야 될 거 값을 가져야 되겠고요 또 개별 노드기 때문에 뭘 가지겠어 왼쪽 자식 오른쪽 자식도 가지겠죠 자 그 여기서 하나 정도 더 생각할 수 있는데 그게 뭔지는 조금 있다가 직접 보기로 하고요 자 그 다음에 avlc에서는 뭐를 하면 될까 실질적으로 모든 것을요 avl 트립 메서드에서 다 수행하면 되는 겁니다 왜 노드 혼자 존재에서는 절대 avl이 될 수가 없어요 노드와 노드가 모여서 avl이 이루어져야 그 abl-e가 형성이 되어야 우리가 노드를 삽입하든 제거하든 연결하든 할 수 있다라는 거지 그래서 대부분의 작업 과업들은 avl의 메소드에서 할거다라는 겁니다 여기까지 이해됐다면 다음 슬라이드로 넘어갈 수 있을 것 같아요 파이썬 문법은 입각해서 abl 트리를 구현할 건데요 제가 여러분 편의상 구분이 쉬우라고 또 들여쓰기 헷갈리지 말라고 이렇게 노드 클래스랑 ava 클래스를 구분해서 써 드렸습니다 요거는 노드 클래스 안에 있는 코드다라는 의미고요 앞으로이 슬라이드 뒤에 볼 모든 코드는 다 av를 그만큼 대부분의 과업들은 avl 클래스에서 할거다라는 거 기억을 해 두시고요 자 클래스 노드 한번 볼까요 생성자만 만들면 끝이에요 진짜 끝인데 노드가 무엇을 가진다고 얘기했어요 당연히 47 53 이런 값을 가져야 되겠고요 그리고 왼쪽 자식과 오른쪽 자식은 일단 처음은 몰라 노드를 처음 배정할 때 모를 수도 있다라는 거죠 다만 좀 있다가 늘어나이 노드를 삽입하고 제거하는 과정에서 자식이 생길 수 바뀔 수도 있으니까 레프트 라이칸을 일단 비워두도록 하겠습니다 자 그 다음에 제가 뭔가 하나 더 있는데 스포를 안 드렸죠 바로바로요 하이트 하이트 값을 노드가 따로 가지는 것이 좋겠습니다 자 화이트 값을 노드가 가지는게 왜 좋을까 왜 좋을까 하고 생각을 해보니 우리가 어차피 요런 식으로 avl을 계속 만들다가 끊임없이 뭐를 체크할까요 여러분 기억납니까이 밸런스 벡터를 체크하면서 avl의 균형을 유지하는 것 그게 바로 핵심이라니까 자 그런데이 밸런스 벡터를 체크하기 위해서는 왼쪽 서브 트리에 뭐 높이를 알아야 되고요 오른쪽 서브 트리에 높이를 알아야 됩니다 다시 말해서이 왼쪽 서브 트릭과 제가 좌랑우가 한자로 맨날 헷갈려가지고 한글로 쓰겠습니다 맨날 그 네모가 들어가는지 공짜가 들어간지 헷갈려 좌랑우 서브 트리의 높이가 있다라고 했을 때 결국 뭐예요 제가 지금 체크한요 노드에 높이를 안다면은 우리가 결국 좌 서브 트리의 높이를 아는 거죠 자 노드의 높이라고 하니까 좀 생소한 분들이 있을 텐데 사실 노드 자체에는 높이란 얘기를 하지 않습니다 제가 노드의 화이트라는 건 사실상 뭐라는 의미냐면 그 노드를 루트로 가지는 트리의 높이를 의미하는 겁니다 다시 말해서 제가 지금 체크 표시한요 노드의 높이라는 건이 체크 표시한요 노드를 루트로 가진 다시 말해서 아써그 트리의 높이가 되겠다라는 겁니다 그 하이트를 내가 속성으로 가지고 있으면 나중에 자유자재로 꺼내 먹을 수 있지 않겠느냐 즉 레프트의 화이트 라이트의 하이츠를 꺼내 먹어서 줄을 빼면 이게 BF 아니 겠느냐 그래서 노드의 화이트를 속성화시키자라는 겁니다 그렇게 이해해 주시면 좋을 것 같아요 다음으로 자 말씀드렸습니다요 코드 지금부터 점점 난도가 올라갈 텐데이 코드를 처음 봐서 바로 이해할 수는 없을지언정 아이 라인이 왜 있구나 요게 이래가지고 균형화를 수행하는구나를 이해한다면 여러분 잘 아시는 겁니다 우리 자료구조를 처음 배우는 사람들이니까 자 avl 트리도 생성자를 정의할게요 자 근데 노드를 이렇게 잘 정리해 놨으니 사실 avr 트리는 클래스 속성이 아니죠 인스턴 속성 인스턴 속성을 따로 가질 필요가 있을까요 어차피 노드와 노드가 이어져서 avl이 만들어지는 거니까 우리가 avl 틀이라고 하면은 이런 식일 거 아니야 이런 avl층이겠지요 그리고 여기에 50이 있다라고 했을 때 왼쪽에 30이 들어가 오른쪽에 70이 들어가고 60 90 요런 식으로 우리가 abl3가 전개될 건데 결국 그러면 2ablg 제가 지금 메모친요이 avl3를 구분 짓는 건 뭐예요 야 너라고 부를 때 뭐라고 불러주면 돼 잘 생각해 봐 야 50 불러주면 되는 거 아니에요 빠른 거는 어차피 50으로부터 정의가 돼요 50의 레프트가 30이고요 50의 라이트가 70입니다 또 그 70의 라이트가 60이고요 그 70에 70의 레프트가 60이고요 70의 라이트가 90입니다 그럼 결국 우리가 약 52루트인 avl 2라고 부르면 그만인 거 아니냐라는 거죠 그래서이 avl3가 가져야 할 인스턴 속성으로 유일한 건 사실 루트 밖에 없습니다 이진 탐색 트리가 보통 그래요 우리가 다른 인진 탐색 트리도 마찬가지지만 스키 avl의 경우에는요 루트 이게 바로 서로 다른 abh를 구분짓게 만드는 즉 이름표를 불러 줘라고 할 수가 있다라는 거죠 결국이 루트 루트 값을 우리가 생성자에서 초기화 해주는게 가장 좋겠습니다 다만 맨 처음 만들 때는 그냥 넌으로 했다가 나중에 우리가 루트를 선언해 주면 되겠죠 자 그리고 주의해야 될 거 여러분 루트를 왜 너로 했겠습니까 avl이 처음 만들 때는 아무것도 없는 상태로 출발하자라는 거예요 노드가 없어 노드가 없는데 루트가 어떻게 있어 그래서 노드도 없고 루트도 없는 상태에서 시작했다가 av의 원소 하나를 바꿔 50 그러면 걔가 바뀌자마자 루트가 된다는 거 그리고 나서 신나게 60도 넣고 70도 넣고 하다가 어이구 금쪽이가 돼 버렸네 그러면 조정이 이루어지면서 루트가 바뀌잖아요 그럴 때마다이 루트 제가 지금 동글뱅이 처리한 루트 값을 내가 직접 DIY 식으로 바꾸자라는 겁니다 이걸 써놨죠 새로운 노드를 삽입할 때마다 avl 루트 노드가 달라질 수 있다 그거 매번 우리가 보여 줘야 된다 점 루트를 이용해서 바꿔 주어야 한다 간직하고 다음 슬라이드로 갑시다 자 높이를 반환하는 하이트 메소드 지금부터는 계속 메소드 정의입니다 왜 어차피 클래스 두 개라고 했는데 너도 클래스는 이미 끝났어요 avl 클래스만 완성하면 되는데 생성자 다음에 뭐 너 알겠어요 계속 메소드 만들면 되겠죠 여러분 무슨 메소드 등장하겠습니까 우리 슬라이드 안 넘겨도 대충 느낌 와 무슨 메소드가 있겠어 밸런스 팩터 계산 안 했잖아 밸런스 벡터 계산하는 메소드 하나 있을 거고 그리고 나서 금쪽이들 교정해 줘야 된다며 왼쪽 왼쪽 금쪽이 교정해주는 lr메소드 있어야 돼요 오른쪽 오른쪽 왼쪽에 있어야 될 거야 그렇게 몇 개 구현하면 끝이에요 100줄까진 안가 그러기 때문에 우리가 좀 쉽게 쉽게 보자라는 겁니다 참고로 편의를 위해서 삽입만 한번 구현해 보도록 하겠습니다 저희 강좌에서는 요정도로 avl의 삽입까지 구현해보는 정도로 챕터 1을 마치도록 할게요 자 화이트 메소드인데요 뭔가 좀 수상하긴 해요 아니 노드가 분명히 화이트 속성을 가지고 노드에서 내가 하이트를 라이브로 즉 다이렉트로 불러오면 되는 건데 왜 하이트메소드가 따로 있지라고 생각하는 분들이 있을 거예요 그냥 그러려니 하고 일단 갑시다 자 메소드 자체는 일을 이해하기는 어렵지 않아요 화이트라는 메소드가 정의가 되는데이 친구가 뭐를 인자로 받는다 제가 지금 똥글뱅이 치는 대로 노드를 인자로 갚는다라는 겁니다 다시 말해서 측정 노드 내가 지목한 어떤 노드의 높이를 반환하는 겁니다 노드의 높이라는 거 생소하게 여기지 말라고 했죠 그 노드를 루트로 가지는 트리의 높이다라고 얘기를 했습니다 예를 들어서 10 20이면 순서가 거꾸로 됐죠 라고 했을 때 30이라는 노드의 높이를 우리가 뭘로 정의하느냐이 세모친 트리에 높이라고 정의하자라는 겁니다 그러면 뭐라고 했어 우리 편의상 노드가 하나뿐이면 높이가 0이다 그 뒤에 1이다라고 정의를 했죠 그래서 1로 정의하자라는 건데 자 왼쪽 보시면 흥미롭게도 노드가 너닐 때도 우리가 화이트 값을 반환합니다 리턴 뭐 -1이라고 반환을 하는데요 -1이라는 걸 어색해 보이지만 상식적으로는 합당합니다 왜 노드가 하나뿐이면 높이가 0이라며 그럼 그 하나마저 없으면 높이가 얼마야 0보다도 작은 -1이 나죠 그래서 i를 반환하는 거고요 그렇지 않다면 노드의 화이트를 반환하라는 건데 여기서 눈치 빠른 수강생들은 캐치 하셨을 겁니다 아 노드의 화이트가 있어도 입에서도 있어요 왜 이걸 못 팔아요 노드의 화이트는 노드가 존재해야 반응할 수 있는 값입니다 근데 노드가 없어요 없는데 어떻게 반환해요라는 거죠 그래서 우리가 아 내가 bf를 개선하다 보면 간혹가다가 오른쪽은 트리가 주렁주렁 풍성 풍성 달려 있는데 왼쪽이 텅 비어 있는 경우가 있을 수 있다는 거죠 이런 경우에도 하이트를 돌려내긴 돌려내야 될 거예요 그래서 우리가 너희인 경우에도 -1을 반환할 수 있도록 하이츠 메소드를 따로 정의한다 괜히 그런게 아니다라는 겁니다 이거 피할 수도 있어요 이런 메서도 정의 안 하고 갈 수도 있는데 그러면은이 부분이 너무 많아집니다 만약에 왼쪽이 비어 있다면 만약에 오른쪽이 비어 있다면 그 실천하나 그래서 우리가 애초에 비어 있어도 바로 반환해주는 하이튼 메소드를 별도로 구해야 된다라고 이해하시면 좋겠습니다 막상 살펴보니까 점점 별거 아니죠 자 더 별거 아닌 것들을 두 가지 살펴보겠습니다 밸런스 벡터 메소드를 볼 건데요 화이트 함수를 메소드를 구현한 이상 얘는 껌 까진 아니고 한 껌의 절반 정도예요 자 밸런스 벡터라는 거는 결국 뭐냐면 왼쪽 서브트린 높이 빼기 오른쪽 서브 트리 높이라고 얘기를 했는데 우리 서브 트리 높이가 곧 노드의 높이라고 암묵적으로 정의했잖아 그래서 리턴을 요렇게 해주면 됩니다 왼쪽 자식의 오른쪽 자식의 결국 주어진 노드 인자로 주어진 노드의 BF 값이 되겠다라는 겁니다 어 자식이 없으면요 괜찮지 방금 전에 마이너스 1이라고 정의했죠 그렇게 BF 메소드를 순식간에 정의할 수가 있다라는 거고요 실제 삽입을 위한 전초전이라는 의미에서 제가 인서트 데이터 메소드를 정의했는데요 자 여러분 인서트가 두 줄이 끝이에요 이게 말이 됩니까 avl에서 가장 난해한게 뭐예요 우리 삭제도 그런 안 하기로 했잖아 삽입만 구현하기로 했잖아 그만큼 avl에서 정말 제가 좀 구수한 표현을 쓰겠습니다 더럽게 더럽게 까다로운게 바로 인서트인데 그 두 줄만은 되겠습니까 안 되거든요 두 줄만에 안 돼요 인서트 굉장히 길어요 긴데 인서트 데이터는 인서트가 아닙니다 이게 무슨 소리냐 자 우리 밖에서 시선을 돌려 보자라는 거죠 우리 열심히 지금 av에 내부에서 메소드를 뚝딱하고 있는데 이걸 실제로 쓰는 일반 사용자 입장에서 생각을 해봐 자 일반 사용자 입장에서는 어떻게 활용을 할 것 같아요 우리 생성자에서 아무것도 정의 인자 안 받았던 거 기억나죠 avl 이용해서 트리 1이라고 정의를 하겠습니다 1번이라고 제가 확실히 쓸게요 자 트리원을 avl이라고 정의를 한 다음에 밖에서는 어떤 식으로 avlt를 구성할까요 31에다가 삽입을 하겠죠 어 너 삽입할 거야 뭘 삽입할 거야 그럼 32 루트에 쏙 들어갈 거고요 31에 그러면은 52 35른쪽에 쏙 들어갈 겁니다 다시 말해서 밖에서 사용자가 직접 avl 개최 라이브로 삽입할 때는 뭐만 받아요 여러분 잘 보세요 3의 명칭과 함께 삽입할 노드 하나 값만 받치고 즉 받는게 뭐야 인자로 갖는 거는 데이터 하나 밖에 없다라는 겁니다 자 근데 뭔가 이상해요 이제 밖에서 시선을 다시 안쪽으로 돌려서 내부자 시선에서 살펴볼게요 우리 내부자가 자 데이터만 받아 가지고 avl 트리에 값을 넣을 수 있을까요 이거 없어요 이거 왜 없느냐 데이터만 봤잖아요 그러면은 어디에 어떻게 넣을지가 꼬이게 됩니다 다시 말해서 우리가 실제로 안에서 삽입을 할 때는 우리가 뒤에서 보여드리겠지만 요거 셀프와 함께 노드 데이터 요렇게 해야 인서트가 정상적으로 가능해요 이거 왜 그러냐면은 우리가 이진 탐색 트리의 원리를 생각하면요 노드가 필요할 수밖에 없다라는 거 여러분 공감하실 겁니다 자 50이 떡하니 있어요 30이 있어요 70이 있습니다 제가 90을 넣으려고 해요 90을 넣으려고 하면은 내가 어떤 과정을 거쳐서 넣게 되냐면 일단 루트 노드의 방문을 합니다 속도 계십니까 오냐 나는 50이다 저는 90인데요 그래도 왜 오른쪽으로 계십니까 오냐 나 70이다 전 90인데요 오른쪽으로 이거 뭐예요 제기적으로 노드를 위해서부터 아래로 쑥쑥 가면서 계속해서 인서트를 제기 호출하는 거거든 그러면은 호출할 때마다 뭐가 바뀌어 로드가 바뀌기 때문에 실제 삽입 메소드 실제 삽입 함수인요 인서트는 노드를 안 받으면 안 돼요 그냥 관만 띡 받아 가지고 루트에다가 쏴줄 수가 없는 구조라는 거예요 결국 노드가 반지 있어야 한다라는 건데 우리 바깥에서 구태여 어느 노드의 몇 번 넣고 그렇게 얘기해요 밖에서는 그냥 30로 출신과 이렇게 한다니까 그렇기 때문에 깨서 쉽게 꺼낼 수 있는 인서트 데이터 메소드랑 실제로 불러와지는 인서트 메소드는 근본이 다르다 그래서 인서트 메소드 실제로 제기적으로 호출되는 메소드에는 노드까지가 지목이 되고 밖에서 쉽게 쓰는 메소드는 노드 없이 데이터만 지목을 한다요 부분이 가장 까다로운 포인트 중에 하나입니다이 뒤는 문법적으로 까다롭기보단 그냥 기글이 길어요 길일 뿐이지 별로 까다롭지 않습니다 중요한 건 아 주께서는 군만으로 넣으니까 노드를 지목 안 하지만 실제로 제기적으로 슉슉 내려가면서 노드를 집어넣을 때는 노드 인자도 필요로 하니까 그래서 인서트 데이터가 해야 할 일은 말 그대로 전초전 밖에 없고 뭐 루트로부터 시작해서 인서트를 소환하는 일 밖에 없다 그래서 얘가 인서트를 소환하는데이 두 메소드가 다르다는게 극명히 보여 왜 인서트 데이터는 내가 하나밖에 없거든요 데이터밖에 없었어 근데 얘가 인서트 불러올 때 인자를 노드 하나 데이터 하나 이렇게 다르다라는 겁니다 자 그러면 실제 인서트는 어떻게 돌아가냐 그것부터는 오히려 쉬워요 오히려 깔끔해 왜 이젠 탐색 트리의 원칙을 준용하기만 하면 되거든 자 근데 여기 함정이 있어요 제가 1/2이라고 말씀드렸죠 왜 이분의 1일까 뒤에 하프가 더 있어요 인서트에서는 딱 하나 조심해야 되는데 뭐 균형이 깨지는 경우를 조심해야 한다라는 겁니다 일단 균형 깨지는 거 무시하고 그냥 헛 헤프 이오 슬라이드에서는 그냥 집어넣을 겁니다 뭐에 입각해서 이진 탐색 트리의 원리에 입각해서 자 루트부터 시작을 해요 어 새로 삽입될 너 놈 너 새내기 너 루트보다 크냐 크면 오른쪽으로 하고요 아 작냐 그럼 왼쪽으로 가겠다라는 있습니다 그게 바로요이 부분에 있어요 자 만약에 너드가 너니예요 그러면은 보이지 않는 곳에 새로운 노드를 넣으라는 거기 때문에 사실상 그냥 노드 자체를 반환하면 됩니다 새 노드 여기 있습니다 하고 던져주면 된다라는 거죠 다만 그게 아니라 어 너 내가 지목한 노드보다 작아 그러면은 여기에 들어가라라는 거고요 자 괜히 노드 넌을 먼저 체크한게 아니다라는 걸 알 수가 있어요 왜 이렇게 가서 가서 가다가 새로운 자식으로 추가될 수가 있죠 그 경우가 바로 노드는 러닝 경우가 되겠습니다 아 왼쪽 오른쪽 왼쪽 오른쪽 슉슉 가다가 비어 있어 그럼 여기가 내가 있어야 할 곳이고라는 의미에서 노드가 반환된다라는 겁니다 그게 아니야 그러면 계속해서 제기적으로 인서트를 수행하라는 겁니다 만약에 지금 받은 데이터가 지금 받은 데이터는 어디 있어요 우리가 지금 받은 데이터 즉 바깥에서 받은 데이터는 dapaa 있죠 그리고 왼쪽 좌변에 보이는 노드 데이터는 뭐 비교할 대상입니다 다시 말해서 새로 들어올 데이터는 그냥 data기 때문에 얘가 더 크다라는 거는 뭐 비교대상보다 크다는 그래서 우측으로 가야 한다라는 뜻입니다 반대의 경우에는 좌측이 되겠죠 그렇게이 부분을 구성할 수가 있겠습니다 원론적으로 가볍게 보는게 중요하다라고 말씀을 드렸어요 자 그러고 나서 이렇게 매번 제기적으로 호출한 뒤에 꼭 잊지 말고 해줘야 할게 뭐냐 자 여러분 노드를 새로 삽입을 했어요 그러면은 그 과정에서 트리의 높이가 변동될 수밖에 없다라는 거죠 그러면 그 각각의 노드를 어떻게 해줘야 되는 화이트를 갱신해줘야 한다는 그게 바로 여러분이 보시는 핫 퍼스트 하프의 마지막 줄이 되겠습니다 노드의 화이트를 매번 갱신 시켜라 어떻게 자 여러분 노드의 화이트라는 거는 사실 얘도 이런 식으로 정의할 수가 있어요 아 세지 말고 결국 왼쪽에 있는 놈 화이트 오른쪽에 있는 놈 화이트 둘 중에 더 무거운 몸을 따라가면 되는 거 아닙니까 예를 들어 여기가 7층이고 여기가 3층이에요 그럼 얘는 뭐예요 높이가 8이겠죠 그렇기 때문에 왼쪽 오른쪽 좀 더 무거운 놈의 + 1이 바로 새로 갱신된 노드의 화이트가 되겠다라는 겁니다 자 근데 뭐라고 했어요 금쪽이 체크하는게 중요하다니까 내가 잘나가다가 밸런스 팩터 꼬인의라고 하는 경우에는 우리가 Roll rl 중 하나의 금쪽이 솔루션을 도입을 해줘야 한다라는 거죠 자 그런데 그런데요 제기적으로 호출되는 방향이 굉장히 중요합니다 자 내려갈 때 다시 말해서 우리가 이진 탐색 트리의 원리에 입각해서 오른쪽 왼쪽 오른쪽 왼쪽 하는 거는 어떤 순서대로 했어요 루트부터 시작해서 점점 아래로 내려가는 식 위에서부터 아래로 톱에서부터 바텀으로 우리가 제기적 삽입이 이루어졌다라는 거죠 자 근데 여러분 생각을 해봐 우리 실제로 보수하는 거 우리 avl3를 보통 보수한다라고도 얘기합니다 재건한다라는 거죠 avl3의 밸런스 벡터를 찾아서 어 여기 깨졌잖아 금쪽이 찾는 과정은 어떤 식으로 우리가 전개가 돼요 거꾸로 전개가 된다라는지 다시 말해서 삽입은 삽입 대로 요렇게 위에서부터 아래로 제기적으로 내려가면 돼 다만 우리가 재건하는 즉 밸런스 벡터가 절대값이 2에 도달하는지를 찾는 과정은 밑에서부터 순차적으로 올라간다라는 거죠 근데 그 순서 내가 신경 안 써도 알아서 구현이 돼 놀랍게도 왜이 코드만 따라가면 결국 제기적으로 인서트를 불러 불러 불러 불러 주세요 하다가 아 부르고 나서 거꾸로 올라가게 됩니다 그게 스택이가 재귀의 원리였잖아요 스택이 맨 마지막에 넣은 원소부터 빠져나가는 것처럼 재귀도 사고 파고 파고 들어가다가 마지막으로 실행되고 있던 것부터 탈출한다라고 얘기를 했잖아 그게 바로 요거예요 인서트 하는 거는 위에서 아래로 갖다가 어 인서트 다 했어 그러면은 밸런스 벡터 체크하는 건 아래에서부터 지가 알아서 한다라는 겁니다 재규하려고 하니까 요렇게 단순하게 코드가 직관적으로 작성이 되는구나라는 거예요 결국 내가 아래에서부터 위로 삽입한 바로 그 위치부터 루트까지 올라가면서 수나라도 밸런스 벡터가 한계를 초과하면은 바로 보수공사에 들어가자라는 겁니다 근데 제 말씀드렸죠 금쪽이의 케이스는 4가지 밖에 자 그런데 지금 첫 번째로 보고 계시는 지금 위에 제가 4개를 일부러 여러분 막 암기하지 말라고 바로 눈으로 이해하라고 이렇게 띄워 드렸는데요 기준에서 맨 왼쪽 첫 번째 사례를 볼까요이 친구의 경우에는 밸런스 벡터가 얼마인 겁니까 맨 윗로드 기준으로 밸런스 섹터가 2인 거예요 왼쪽이 높이가 2인데 오른쪽이 높이가 깊이가 0인 거니까 자 그래서 우리가 요렇게 2인 경우를 생각해 봤는데 사실 얘뿐만 아니라 뭐도 이해해요 이 친구도 세 번째로 보는이 친구의 경우에도 뒤에서 c로는 오른쪽으로 가긴 했지만 어쨌든 둘 다 왼쪽에서부터 뻗어나간 놈이기 때문에 2라는 밸런스 벡터를 가진다라는 거죠 근데이 둘은 결정적 차이가 있어요 왜 b의 시선에서 봤을 때 얘는 밸런스 벡터가 1이지만 얘는 밸런스 벡터가 마이너스 1이에요요 차이가 있다라는 겁니다 그래서 우리가이 밸런스 벡터를 판단할 때 다시 말해서 4가지 금쪽이 각각의 케이스를 구분해서 돌려야 될 거 아니야 ll 금쪽이랑 rr금쪽이랑 솔루션이 똑같겠어요 아니잖아 균형 잡는 방식이 다르단 말이지 그래서 우리가 4가지 금쪽이를 유형별로 완벽 mbti가 돼요 유형별로 완벽 분류를 할 건데 밸런스 벡터를 기준으로 분류하면 되게 깔끔할 것 같다라는 거예요 실제로 우리가 a랑 B 기준으로 밸런스 벡터를 다 개선하잖아 그러면 이 되고요 여러분 직접 계산해 보시면 나옵니다 이건 아주 어려운 내용은 아니에요 된다는 겁니다 오 세상에 이렇게 멋들어지게 4가지가 떨어질 줄이야 맨 민놈 기준으로 음수냐 양수냐 그리고 그 밑에 넘기준으로 음수냐 양수냐 비교하면 끝이다라는 거예요 그래서이 두 가지 제가 지금이 코치 키스 심으로 표시한요 두 가지가 바로 첫 번째 큰 이프문이 되겠습니다 둘 다 공통점은 뭐예요 보수공사가 되기로 결정된 a점 위로 올라가다가 여기서 고수해야겠다라고 판단하는 거잖아 그 점에서 밸런스 벡터가 둘 다 뭐예요 1보다 크다는 특징을 가지고 있어요 근데 특히 자기 왼쪽 자식이 밸런스 벡터가 양이면 ll 금쪽이고요 밸런스 벡터가 을이면 lr금쪽이에요 그렇게 구분을 하는 거고요 아랫단도 마찬가지입니다 어 보수공사가 시작되는 점에서는 음수라는 공통점이 있는데 B 즉 자기 오른쪽 자식이 밸런스 벡터가 양이면 아래를 금쪽이 음이면 아래금 쪽이라는 거죠 이렇게네 가지 케이스를 완벽 구분을 했다라는 겁니다 다음 슬라이드가 금쪽이에 대해서 우리가 솔루션을 제공하면 되는 겁니다 자 그런데 제가 위에 헷갈리지 말라고 올려 드렸어요 ABC 순으로 되어 있을 때는 애초에 a는 루트의 자격이 없었다라고 말씀을 드렸죠 b가 왕좌의 앉을 자극이 있다라는 점에서 우리가 b를 루트로 바꿨어요 아 그러면 우리가 방금 전에 이것만 앞으로 가볼까요 셀프 ll 노드라는 식으로 우리가 호출을 했거든요 그리고 나름대로 리턴까지 해 자 뭐를 기준으로 구출했어요 여러분이 노드는 a입니까 b니까 c입니까 위 다이어그램 기준으로 로드의 밸런스 벡터가 1보다 크다라고 얘기했기 때문에 우리가 지금 금쪽 솔루션을 호출하는요 노드는 뭐냐면 이게 중요합니다 여러분 제 일부러 강조 목이 죽겠는데 강조드리는 이유가 있어요 얘가 a라는 겁니다 그럼 지금부터 뭘로 생각하면 돼 아 a를 어디로 옮기고 1을 새로운 루트로 추대하고 이런 모든 것들은이 위쪽 노드가 호출한 노드다라는 기준으로 판단하면 되겠다라는 걸 그럼 ll만 설명드리면 다른네 가지는 순식간에 끝난 거야 자 ll 기준으로 즉 셀프 노드라는 인자를 받았는데 셀프는 어차피 국물인자이기 때문에 노드만을 받는다라고 말씀을 드렸어요 자이 노드가 결국 a다라는 겁니다 자 그럼 내가 최종적으로 새의 노드를 뉴로 반환할 거거든 새 노드를 반환한다 여러분 무슨 느낌이 듭니까 새 왕좌를 추대한다는 느낌이 가지죠 왜 원래 노드는 a자리였는데 그 새로운 노드의 자리를 바꾸겠다는 결국 뉴는 뭐예요 새로 추대될 루트가 되겠다라는 겁니다 자 새로 추재된 루트 뭐예요 abc 중 그거잖아 b라고 그러기 때문에 결국 뉴에 들어갈 놈은 뭐가 된다 지금 구왕좌의 왼쪽 자식 즉 노드래프트가 된다라는 것 이논이면 못 헤쳐나갈게 없어요 그럼 내가 이제 뭐 해주면 돼 아 그러면 구왕좌 즉 a의 왼쪽에 있어야 할 놈도 업데이트를 해야겠다라는 겁니다 왜 a의 왼쪽에는 원래 b가 있었거든요 근데 새로운 a 즉 내려갈 왕좌에서 내려갈 a의 왼쪽에는 이제 더 이상 b가 아니라 뭐가 있어 z가 있다라는 거죠 그러면요 z도 재설정 해 줘야 돼요 즉 우왕좌 a의 왼쪽에 있을 놈은 Z3 이건 틀릴 수도 있고 넌일 수도 있고 노드일 수도 있다고 말씀드렸습니다요 Z 부분의 경우에는 뭐가 돼야 된다 원래 있던 얘가 비슷해 내야 된다라는 겁니다 원래 있던 얘는 뭐에 뭐예요 b에 오른쪽 자식이죠 B B 새로운 왕자의 새로운 왕자의 있는 b의 오른쪽 자식이 바로 우노드의 레프트가 될 친구죠 이런 문법이에요 이게 어렵습니까이 어렵다고 해서 문제가 있다는게 아니에요 여러분 처음 보니까 어려울 수 있어요 어려울 수 있는데 결국 직독직해 하면은 모도를 사는 아니다라는 겁니다 아 구왕좌가 a고 세왕자가 b야 그럼 그걸 바탕으로 재편하면 되겠네 자 그러면 이런 질문을 할 수 있어요 얘는 왜 안 바꿔요 a의 오른쪽 자식도 위치 바뀌었잖아요 자 a의 오른쪽에서는 위치가 바뀌었으니까 높이는 달라졌을 수 있지만 어차피 a의 오른쪽 자식이라는 상대적 위치는 불변이에요 그러니까 이런 건 바꾸지 말자라는 걸 이런 건 그대로 가고 a의 왼쪽 자식 이런 건 대놓고 바뀌었잖아 그래서 이런 것들을 업데이트하면 끝난다라는 거 자 근데 흥미롭게도 c의 왼쪽 자식도 안 바뀌어요 cx 그대로거든 피해 오른쪽 자식도 y 그대로 있어 내가 이제 바꿀게 별로 없어요 나 이제 뭐만 바꾸면 돼 이게 오른쪽 자식만 바꾸면 돼요 b의 오른쪽 자식은 더 이상 z가 아니에요 z는 이미 업데이트 했잖아 그 대신 b에 오른쪽 자식은 새로 뭐가 들어간다 구왕좌가 들어가게 된다라는 그러면 새로운 왕좌의 오른쪽 자식에게는 뭐가 들어간다 우왕좌가 그거 지금 뭐예요 여러분이 보고 계신 코드의 넷째 줄이 된다는 거죠 뭐야 끝났네 아니 끝이에요 진짜 이게 끝이다라는 거죠 실제로 우리가 노드를 재편하는 과정도 l을 금쪽이랑 rr금쪽이가 제일 편하죠 실제로 그래서 코드도 ll과 rr이 제일 짧아요 그래서 먼저 보여드리는 겁니다 다만 이렇게 조정을 할 때 주의해야 될 거 아 화이트가 바뀌지 자 근데 발 보시면은 결국 하이트가 조정돼야 될 거는 뭐 밖에 없냐면은 노드랑 뉴 밖에 없다라는 거예요 왜 나머지는 어차피 높이 자체는 그대로 보전이 된다라는 거죠 자 잘 생각해 봐 이것도 헷갈리기 쉽습니다 시의 높이를 조정하는 구간이 지금 제가 처리한요 두 가지 중에서 하나도 없거든요 하이트를 갱신하는게요 두 줄밖에 안 되는데 c를 안 건드려요 b는 신왕좌 a는 구왕좌라서 둘 다 건드리는데 c의 높이를 안 건드리거든 c의 높이 업데이트 안 해도 돼 c의 높이는 뭐예요 이 세모 처리한 부분의 높이잖아 즉 우리가 눈으로는 높이가 이동한 것처럼 보이지만 c는 구조가 그래서 x도 y도 c도 높이는 업데이트 할 필요가 없다라는 거예요 결국 높이 바뀌는 것보다 원래 아래에 있다가 왕자로 뚫고 나온 B 그리고 원래 왕자였다가 갑자기 왕좌를 내려놓게 된 a요 둘의 높이만 좀 조정해 줄 필요가 있다는 것 그래서요 두 줄을 이용해서 높이를 조절해주고 세 왕좌를 반환하는게 ll의 끝입니다 자 그럼 좀 마음이 편해 왜요 힘든 과정을 거쳤으니까 rr은 레프트라이트만 바꾸면 돼 진짜로 농담이 아니고 정말로 레프트 라이트가 정말 뉴 노드 이런 거 하나 건드리고 레프트 라이트만 바꾸면 정확히 대칭형 rr 메소드까지 얻을 수 있다라는 괜찮아요 그나마 어려운 공급자면 lr 메소드가 될 텐데이 친구도 다 살펴보진 않겠습니다 흐름만 모자라고 얘기했어요 결국 중요한 건 뭐다 주왕좌와 신왕좌를 파악하는게 중요하다라고 말씀드렸습니다 구왕좌는 뭐예요 원래 a가 루트였어요 lr메소드 기준으로 a가 노트였습니다 근데이 구왕좌는 오른쪽 새 왕좌의 오른쪽으로 강등되고 그 대신 새 왕좌는 뭐가 된다 하단에 있던 c가 된다라는 겁니다 자이 친구는 어려울 수밖에 없어요 왜 ll이나 rr 같은 경우에는 구왕자 바로 밑에 신앙지가 있었거든요 근데 얘는 구왕자의 밑에 신앙자가 있어 근데 두려워할게 없다라는 거예요 자 결국 신왕좌 c는 어디 있어요 구왕과 모두의 즉 a의 뭐에 뭐예요 a의 왼쪽 자식아 아니 이게 첫째 주라니까요 집도 직행하면 되는 거예요 배정만 바꾼다 노드의 위치만 슉슉 바꾸면 되는 건데 그게 직독직해 하면 되는 코드다라는 겁니다 해석할 수 있다면 결국 여러분이 백지 상태에서도 시행착오를 거치면 작성할 수가 있어요 두려워하지 말라라는 차원에서 계속 말씀을 드리는 겁니다 이런 식으로 계속 바꿔주면 돼요 이렇게 하다보면 또 깨름칙한게 뭐냐면은 어 그렇다면은 부왕좌의 왼쪽에 오른쪽 자식 즉 다시 말해서 우리 구왕좌 기준으로 봤을 때 요 친구가 되겠죠 잠시 주석을 다시 달아 드리도록 하겠습니다 이런 식으로 우리가 라인 바이 라인으로 계속 갈 수 있다는 건데 가장 먼저 건드린게 뭐였더라 new 새로운 왕자가 될 시를 결정하는 일이었습니다 즉 원래 왕좌의 왼쪽 자식의 오른쪽 자식이 스케일 왕자가 된다라는 겁니다 자 그러면 두 번째는 어떻게 해석할 수 있어요 방금 전에 뭐라고 정의했어요 c라고 정의했지요 그러면 뉴의 레프트를 대입하겠다라는 거는 결국 clft를 대입하겠다라는 거예요 자 근데 시의 레프트는 뭐예요 왕이다라는 거죠 결국 y를 어디에 대입하냐 하면은 우리가 왕좌로 설정했던 거에 왼쪽에 오른쪽 즉 여기 자리에 y를 집어넣겠다라는 겁니다 이런 식으로 우리가 계속 코드를 구성할 수 있겠다라는 거예요 u의 어디 노드의 어디 레프트의 어디 라이트의 어디 이거를 계속 반복하면 우리가 궁극적으로 avlt를 구성할 수가 있겠다라는 거죠 밑에도 밑에도 그 밑에도 정확히 동일한 코드들입니다 ABC 기준으로 어디를 돌릴 바꿀까 어디에 오른쪽을 바꿀까 자 대표적으로 뭐를 신경 안 써도 되겠어요 a의 우측자식이 W 라는 거는 우리가 더 안 건드려도 돼요 왜 어차피 바뀐 뒤에도 a의 우측자식은 w니까 요런 거를 건드리지 말자라는 거예요 또 대표적으로 b의 왼쪽 자식이 x라는 또 그대로 보존되니까 그대로 보존되는 요소는 하체하고 바뀌는 것들 예를 들어 세 왕자로 c가 앉게 된다 그런 것들을 바꾸는게 총요 5줄이다라는 겁니다 a의 왼쪽 자식 누구 b의 오른쪽 자식 누구 그런 거를 바꾸자라는 겁니다 또 그 과정에서 높이 보존이 안 되는 것이 있다면 그게요 아래의 셋째 줄이 되겠다라는 거예요 lr은 이런 식이다라는 식으로 이해해 주는 것만으로 충분합니다 결국 이렇게 구현을 했다면 rl은 이라는 것도 우리가 캐치할 수 있겠습니다 자 요거를 다 합하면 우리가 avl3가 짠하고 나온다라는 거예요 진짜인가 우리 한번 보자라는 거죠 자 우리 챕터 1에서 지금껏 숨가쁘게 이렇게 코드들을 살펴봤으니까 실제적으로 잘 돌아가는지 다시 말해서 우리가 작성한 코드가 ava 트리를 잘 구현해내는지 확인 한번 하고 넘어가도록 하겠습니다 여러분이 지금까지 저와 함께 살펴봤던 코드를 오른쪽에 그대로 옮겨 놓은 겁니다 노드 클래스와 abl 클래스 두 가지가 있는데 노드 클래스의 경우에는 어떠한 생성자에서의 속성을 가지느냐 갑 과자식 우자식 그리고 셀프 하이트까지를 가진다라고 말씀을 드렸습니다 또한 avl의 대부분의 실질적인 메소드가 다 담겨 있다라고 말씀을 드렸는데 일단 avl을 생성할 때 자체는 우리가 루트 말고는 지정할게 딱히 없다라고 말씀을 드렸습니다 왜 트 하고 부를 때 각각의 틀을 구분지는 것 루트는 이렇게 부르기 때문에 루트를 속성으로 가진다라는 겁니다 그 뒤에 하이트를 따로 구해야 되는데 이거 이유가 있었죠 좌자 식이나 우자식이 없어 없더라도 반환을 해줘야 될 것 그래서 하이트메서드를 avl에서 따로 구현해줬다 그러면 밸런스 벡터가 훨씬 깔끔한 메소드로 귀결된다라고 말씀드렸고요 인서트 데이터와 인서트는 엄연히 갈랐습니다 밖에서 사용자가 편하게 데이터를 삽입할 때는 인서트 데이터지만 그 과정에서 실질적으로 대기 호출되는 거는 인서트 메소드다라고 말씀드렸고요 크게 두 파트로 인서트 메소드를 나누어 살펴보았습니다 위에서부터 제기적으로 아래로 계속 내려가는 실질 인서트 요건 이진 탐색 원리에 입각해서 크면 오른쪽 자식 작으면 왼쪽 다시으로 계속 계속 뻗어나가는 거였고요 그 과정을 다 마친 뒤에 아래에서부터 역으로 대규적으로 올라오면서 수선할 때가 있는데 그러면 금쪽 솔루션 4가지 중 하나를 적용한다라고 말씀드렸고 각 4가지 솔루션도 우리가 함께 살펴보았습니다 자 우리 그러면 이론적으로 이런 상황을 한번 실제로 코딩으로 구현을 해보죠 1 2 4 3 순으로 내가 트리에 노드를 넣는다 abl 틀의 노드를 넣는다라고 생각을 해 볼게 그러면 1을 넣어 그 다음에 일로 그 다음에 4를 이진 탐색 원리에 입각해서 이렇게 넣다 보니까 아이고 금쪽 상황이 터졌네 어떤 상황 rr 상황이 터졌다라는 거죠 우리 이거 어떻게 바꿔 원래 왕좌의 앉은 놈은 2였으니까 그래서 2가 애초에 왕좌의할수록 균형 잡히게 바꿔 주겠다라는 겁니다 그런 다음에 사물로 그럼 어디 가겠습니까 여기에 3이 위치하게 지역 이게 ablt에 끝입니다 더 이상 밸런스 벡터가 어그러지는 부분 없지요 자 그러면 우리가 실제로 열심히 구현한요 abl트리 코드가 1 2 4 3 순으로 삽입할 때 아래에 제가 그린 것과 같이 이론적인 것과 동일한 결과를 내는지 한번 보고 다음 챕터로 넘어가도록 하겠습니다 자 avl 틀이 일단 클래스 2개를 정의하고 출발해야겠죠 노드 클래스도 정의하고요 abless도 바르게 정의하도록 하겠습니다 그럼 avl 어떻게 만들어 av를 어떻게 만들어 이렇게 만들지 특히 인자로 집어넣을게 없었습니다 생성자에서 인자로 넓게 특별히 없었죠 처음에는 루트도 없이 아무것도 없는 허허벌판이니까 그렇게 뉴트리라 뉴트리를 이렇게 만들도록 하겠습니다 그 상태에서 삽입은 뭐 한다 인서트 데이터로 편리하게 한다라고 말씀을 드렸습니다 실제로 재기 호출되는 건 인서트지만 1 넣고 성능 좋네 2가 잘 들어가 있어요 그뿐 아니라 어 그럼 루트의 왼쪽 자식에도 좋네 일이 들어가 있고 루트의 오른쪽 자식에도 4 들어가 있고 루트의 오른쪽에 왼쪽 자식 해도 라는 겁니다 우리가 결국이 흐름 코드의 흐름 전반을 이해할 수 있다면 아 여러분이 균형 잡힌 트리를 진짜로 이런 실전 모든 차원에서 이해했구나라고 보셔도 과언이 아닐 것 같아요 다음 챕터로 가죠 자 다음 챕터는 b3에 대해서 조금은 가벼운 마음으로 살펴보겠습니다 비트리도 사실 깊이 다르다 보면 한도 끝도 없는 내용인데 저희 타시 분량의 한계로 인해서 비트리를 가벼운 마음으로 좀 보도록 하겠습니다 자 균형을 잡는 데는 여러 가지 방법이 있어요 avl3는 어떻게 균형을 잡았지 일단 삽입해놓고 위로 재건하면서 어 여기서 좌우 틀어진 거 아니야 밸런스 벡터를 이용해서 우리가 균형을 잡았다 또 레드 블랙 같은 경우에는 적극적 흑색을 내면서 규칙 깨졌는데 그러면 고수공사와 같은 방식으로 우리가 균형을 잡았다라는 거죠 다 굉장히 특색이고 독특한 방법으로 균형을 잡았는데 이번엔 또 굉장히 특이한 요런 방법으로 한번 균형을 잡아 보겠다라는 겁니다 어떻게 챕터 제목의 말씀드린 대로 모든 리프노드의 깊이가 같다 자 생각을 해봐 우리가 이젠 3는 아니든 뭐든간에 스리라면은 우리가 보통 균형이 안 좋다라고 하는 거는 이런 틀을 얘기하는 거거든요 이런 것들 이런 것들 막 틀이 그냥 엄청 안 맞잖아 근데 이거의 특징이 뭐예요 균형 안 잡힌 측 뭘까 리프노드 한번 체크해 보실래요 체크한 거 높이가 너무 달라요 왼쪽은 깊이가 되게 깊은데 오른쪽은 깊이가 되게 낫단 말이지 아 이거 애초에 균형의 핵심은 림프들이 깊이가 똑같은 거 아닌가라고 생각할 수 있다라는 거예요 그래서 우리가 비트리의 정신은 뭐냐면 모든 리스모드에 깊이가 같다면 2라고 생각한다라는 겁니다 여러분 왼쪽에 보고 계신 트리가 바로 3차 비틀이에요 3이 뭔지는 찾아 설명을 드리고요 3차 B 틀인데 얘 지금 보시면 리프 모드가 되게 괴랄하게 생긴 것들도 있어 35 38 이런 거 여러분 안 띄워져 있으니까 한 세트인 겁니다 제가 지금이 인터벌로 한게 한 세트예요 하나의 노드입니다 아니 하나의 노드의 데이터가 둘이나 있어 이것도 무슨 이상한 경우야라고 생각할 수 있지만 어찌됐든 모든 한결같이 깊이가 똑같다는 거죠 맨 위에서부터 한층 9층 내려왔다라는 점에서 깊이가 동일하니까 이런 식으로 균형을 유지하는게 이틀이다라는 겁니다 자 b7에는 이뿐만이 아니라 5가지 조건조 까다로워요이 친구 다섯 가지 조건을 모두 지켜야 되는데 첫 번째 조건은 우리가 쉽게 쉽게 봤어요 애초에 얘가 균형을 잡는 근간이 되는 깊이가 똑같은 m이 3이에요 3차 리틀인데 3차 비트의 경우에는 노드당 자식수가 2분의 m 가우스에서 m계 사이다라고 되어 있어요 자 그런데 가우스 기호가 뭐냐 이거 쉽게 얘기해서 버림이라고 생각하시면 됩니다 예를 들어 2분의 11 얘는 뭐냐면은 5.5의 가우스 기호 이잖아요 이거 가우스 기호라고 보통 얘기를 하는데 5.5의 대괄호라는 거는 뭐냐면 거리라는 겁니다 즉 소수점 이하는 버림 한 개 바로요 기후의 의미가 되겠습니다 양수기준입니다 자 노드당 자식 수는 2분의 m 가우스에서 n개라고 돼 있는데 2분의 m은 뭐예요 1.5 다시 말해서 노드당 자식수가 1개에서 세 개가 되겠다라는 겁니다 즉 자식이 많아야 세계 미니멈도 중요한데 맥시멈이 훨씬 중요해요 자식이 많아야 세계라면은 3차 비트리가 되겠다라는 겁니다이 친구 봐봐요 자식이 많아야 몇 개야 루트 노드의 자식은 하나 둘 셋 세 개잖아 많아야 세계 적으면 한 개나 두 개인게 3차 빛의 특징이 되겠습니다 자 그리고 세 번째 조건 자신로드 수는 데이터 수보다 1 많다는데 이거 이렇게만 보면 너무 어렵거든요 근데 쉽게 얘기해서 뭐라고 이해하시면 되냐면은 우리가 왼쪽 그림 기준으로 설명하자면 한마디로 정리가 돼요 순번 조건이 글로구만 까다로운데 그림으로 생각하면 굉장히 편합니다 여튼 주황색 보이시죠 이렇게 막대기 조그마한 막대기를이 선들이 다 옅은 주황색으로 되어 있잖아 엿은 주황색에서 자식이 태어난다라고 생각하시면 되겠습니다 근데 지금 보시면 아시겠지만 여튼 주황색이 어디 어디 있어 요런 식으로 4개의 수가 있으면 옅은 주황색이 하나 둘 셋 넷 다섯 개 있잖아 그래서 데이터 수가 n개라면 옅은 주황색은 n + 1개만큼 있어요 근데 모든 여튼 주황색에서 자식이 지금 바쁜 뿜어져 나와요 여튼 주황색 옅은 주황색 아래에서도 여튼 주황색 모든 여튼 주황색에선 자식이 무조건 뽑아져 나온다라는 겁니다 리프 제외 리프트 자식이 없으니까 그래서 리플을 제외한 모든 여튼 막대기에서 가식이 나온다라고 생각하면은요 원칙이 당연해집니다 왜 각 데이터의 왼쪽과 오른쪽에 모두 옅은 막대기가 위치하니까 그래서 막대기수 즉 자식수는 데이터 수보다 1 더 많다는게 그래서 존재하는 규칙이다라는 겁니다 다시 말해서 하나의 노드가 두 개 세 개네 개의 값을 가질 수도 있다라는 거예요 실제로 우리 당장 요거에 루트 노블 이거 전체가 하나의 노드라고 얘기를 했잖아이 친구는 데이터가 몇 개예요 두 개입니다 근데 자식수는 3개다라는 거죠이 + 1 규칙이 암기할 필요가 있는게 아니라 데이터가 두 개다 그럼 막대기가 세 개니까 막대기에서 뻗어져 나오는 자식도 그렇게 이해할 수 있겠다라는 겁니다 이렇게 세 개의 자식이 맥시멈으로 뻗어 트리가 뭐였다라는 겁니다 자 그러면 4 5번은 좀 쉬워요 4번 단일노드 내에서 데이터는 다시 말해서 데이터가 2개 3차 비치면 여러분 찬찬히 살펴보세요 3차 비트리면 자식이 많아요 몇 개 세 개라는 거고 자식이 많아야 세계라는 건 옅은 막대기가 많아야 3개다라는 거죠 결국 얘는 뭐다 데이터가 많아야 두 개다라는 겁니다 자 그러면 이렇게 두 개의 데이터가 있다라고 얘기했을 때 흥미로운 건 다 뭐가 돼 있어 경력이 돼 있다라는 겁니다 왼쪽이 오른쪽보다 더 작아요 단일노드 내에서 여러 개의 데이터가 존재하는 경우에는 이렇게 정렬이 되어 있다라는 겁니다 예를 들어 오차 비트야 5차 피트리면 데이터가 몇 개까지 가능하겠어 하나의 노즈의 자식이 5가지 가능하니까 데이터가 4개까지 가능하거든요 그런 경우에도 우리가 어떤 식이다 요런 순이다라는 거예요 우리가 오차비트리의 경우에 이렇게 10 15 17 23 데이터가 4개까지 가능한데이 경우에도 반드시 이렇게 오름차순으로 정렬이 되어 있다 노드 내에서 데이터는 정렬이 되어 있다라는 겁니다 근데 그뿐 아니라 뭐 틀이 전체의 관점에서 보더라도 데이터는 정렬이 되겠습니다 여러분 자식이 괜히 막대기에서 뿜어져 나오는게 아닙니다 여러분 이맘때기 제가 지금 네모초를이 막대기는 무엇을 의미하냐면 33의 왼쪽이죠 33의 왼쪽이면 뭐다 내 밑에 놈들은 모두 33 미만이라는 의미입니다 실제로 그래요 얘이 네모 제가 지금 빨갛게 처리한요 옅은 네모에서 뿜어져 나온 자식들을 제가 모두 체크해 볼게요 요 네모에서 잉태한 자식들이 얘죠 자손을 포함해서 손자 포함해서이 네모에서 잉태한 놈들이요 세 가지인데 세 가지 모두 뭐예요 33보다 작아요 이거 어디서 많이 봤던 장면인데 이진 탐색 트리 원리였잖아 그걸 그대로 준용한다라는 겁니다 이온 네모 볼까요 이 네모의 특징은 뭡니까 33 [음악] 과 81 사이에 있다는 거죠 즉이 네모에서 잉태한 모든 자녀와 손자들은 33보단 크지만 81보다는 작은 규칙을 유지한다라는 겁니다 진짜야 제가 지금 동글뱅이 한 4개의 또는 6개의 수들은 모두 네모 처리한요 빨간 네모에서 잉태한 놈들거든요 이에 다 33보다 크고요 얘 전부 80일보다 작아요 실제로 그렇습니다 그래서 요런 트리에 관점에서도이 옅은 네모 기준으로 데이터가 완벽정렬 되어 있다 이게 바로 bhc라는 겁니다 복잡하지만 균형이 잡혀 있을거다라는 건 확실히 보장할 수 있어요 왜 높이로 다 똑같습니다 이런게 바로 b3의 균형 잡기 특징이다라는 겁니다 자 그럼 이제 뭐 보겠어요 어떻게 데이터를 탐색하는지 나가서 어떻게 데이터를 삽입하는지 보겠지 탐색 먼저 볼까요 이렇게 주어진 p3에서 82를 먼저 찾아봅시다 자 각 82를 찾으려면 7이나 항상 뭐부터 본다 루트에서 시작해서 제기적으로 내려간다라고 말씀을 드렸습니다 자 82를 먼저 찾아볼게요 자 사망 차사 80일을 한번 찾아봅시다 자 82는 루트 기준에서 봤을 때 새 막대기 중에 어디에 속해야 될 것 같아요 82는 33보다도 크고요 81보다도 커요 그럼 이막대기 아니야 어디로 가야 돼 오른쪽으로 가야 된다라는 겁니다 아 방금 전에 열심히 b3의 원칙을 배워 놨더니 아우로 가는 건 좀 쉽네 오른쪽으로 가서 이번에는요 노드를 보자라는 것 자 요노드 기준에서 봤을 때 82 찾고 있습니다 82는 83보다 작아요 그렇기 때문에요 네모에서 출발을 해야 한다라는 겁니다 계속 제기적으로 내려가니까 미안합니다 어 81을 찾아봤는데 이게 탐색이에요 탐색 있는 값은 요런 식으로 탐색할 수 있다라는 겁니다 역시 있는 값 27을 찾아볼까요 27은 33보다 작습니다요 네모에서 출발 24와 27 비교하면 입사보다 큽니다요 네모로 [음악] b3에서의 탐색 원리다이 친구도 이렇게 균형이 잡혀 있다 보니까 높이가 낮은데 결국 탐색에 드는 시간 복잡도가 뭐다 5h 만나야 로키 밖에 안 된다라는 걸 캐치할 수 있겠죠 자 그 다음에 b3에서 연산도 한번 살펴보도록 할 건데 연산 삽입 정도만 보도록 하겠습니다 자 삽입을 가벼운 마음으로 한번 볼 건데 자 우리가 규칙을 깨지 않는 선에서 b3의 데이터를 삽입하는 상황을 한번 생각해 보도록 하겠습니다 비틀의 규칙을 안 깬다라는게 중요해요 자 쉬운 거 먼저 어려운 건 나중에 보겠습니다 자 쉬운 거부터 65를 삽입하는 상황을 한번 생각을 해 볼게 65를 삽입하려면 어떻게 하면 된다 제가 지금 하이라이트 천원대로 뭐가 중요하냐면은 탐색이랑 비슷한 방법으로 리프까지 가는게 중요합니다 여러분 삐칠이에서도 중복이 있겠어요 없어요 중복이 없는데 중복 없이 새 노드를 삽입하려는 경우에는 어디까지 간다 리프까지 가겠다라는 겁니다 그 리플을 선정한 다음에 거기에다가 자 찰 때까지 삽입하는게 핵심입니다 예를 들어 65를 볼까요 65를 탐색하듯이 리프까지 내려가자라는게 올립니다 탐색하듯이 리프까지 내려가자 자 65를 보겠습니다 65는 맨 처음 탐색할 때 어디 보죠 루트 보죠 루트에서 새 네모 중에 어른의 33보다 크지만 85보다 작으니까이 네모를 따라 내려가면은 45와 72를 만나는데 역시 얘 영화도 가운데에 있어요 그렇게 내려가니까 60까지 왔고요 이제 더 이상 못 내려가요요 60이 우리가 찾고자 하는 리프 노른데 우린 지금 탐색이 아니라 신규 데이터를 삽입하려고 하는 거죠 자 근데 60일 시선에서 볼게요 제가 60 다시 한번 그리겠습니다 여기 65 못 들어가요 왜 못 들어가 이렇게 들어가도 규칙에만 아니지요 왜 얘는 아 여러분 3차 비트리 과정입니다 3차 B 트리가 좀 이거를 깜빡할 뻔했군요 3차 b3를 가정했을 때 3차면은 데이터가 최대 2개까지 위치할 수 있고 자식이 3개까지 가능한데 이렇게라도 규정 위반 아니잖아요 높이 전혀 안 깨지잖아요 그래서 60 옆에 65를 낑겨 놓는다 그럼 끝 이게 바로 삽입이 된다라는 겁니다 그럼 99도 한번 넣어 볼까요 결국 중요한 거는 뭐다 탐색하듯이 리프까지 내려갔다 99는 80일보다 크고요 95보다 크고요 그래서요 노드의 위치하게 됩니다 자요 노드 외로이 98밖에 없어 99 채워주면 되지 자 여러분 99강에 98 옆에 갈까요 노드 내에서도 오름차순 유지라고 말씀드렸죠 그러기 때문에 99가 98 오른쪽에 가는 겁니다 97이었으면 왼쪽으로 갔겠지 이렇게 우리가 삽입이 가능하다라는 겁니다 세상 모든 빛의 삽입이 이런 거면 정말 좋겠어요 근데 그렇게 했으니까 아니죠 대표적으로 어떤 경우가 있냐면은 이런 경우에 당장 이런 식으로 삽입이 불가능하다라는 거 39를 삽입한다고 생각을 할게요 똑같은 원리로 일단 갈게요 39는 33보다 91보다 내려가서 45보다 작죠 그렇게 왼쪽으로 가서 35 38요 동글뱅이 친 니프노드에 39를 삽입하면 되겠습니다 어 삽입은 되는데 3차 피트리 과정입니다 이러면 안 되는데 이러면 왜만 왜 안 돼요 3차 피트리는 자식이 많아야 3개다라고 말씀을 드렸는데 얘는 데이터가 3개고 자식이 4시 돼버려요 그래서 요런 식의 경우는 생각하지 않는다고 물론 얘는 리프니까 아직은 자식이 없어 하지만 기본적으로는 m2p3의 균형의 위배된 겁니다 왜 m2p3는 자식으로 가질 수 있는게 많아야 그리고 데이터로 가질 수 있는게 많아야 엠마 1개부터 그래서 얘는 규칙을 위반한 겁니다 3차 b3의 규칙을 그러면 어떻게 하냐 규칙을 위반하는데 영향을 준게 뭐예요이 친구가 너무 길다라는게 규칙에 영향을 준 거잖아 그러면 기니까 얘를 잘라 버리자라는 거예요 얘를 스플린 분리라고 이야기를 합니다 자 얘를 어떻게 분리할 수 있을까요 개미를 분리하면 머리가 이렇게 분리하듯이 얘도 총 튕겨져 내서 분리를 하자라는 겁니다 근데 멀티 튕겨내느냐 아빠도 오지 않습니까 가운데 있는 놈을 쏙 튕겨 가지고 사지를 분리한다니까 너무 잔인하네요 그러니까 35 38 39 이렇게 뭉쳐져 있던 거를 38 가운데만 튕겨져서 분리를 하다라는 겁니다 그러면 어떻게 된다 여러분 35와 30분은 더 이상 붙어 있지 않게 됩니다 이거 굉장히 중요해요 이렇게 넣은 다음에 35랑 39는 가운데 허리가 끊어짐으로 인해서 지들끼리도 분리가 돼 버립니다 35와 39로 분리가 되고 38은 어디로 간다 어디로 가겠어요 분리되면서 위로 용천해 버렸으니까 38은 여기 간다라는 야 근데 문제 또 터졌네 38 45 72도 안 돼요 이렇게 세 개의 몸집이 있을 만한 3차 트리가 아니라니까 3차 트리는 노드에 많아야 데이터가 둘밖에 없다고 그러면 38 45 72도 말싸움 그럼 어떻게 하면 돼 얘도 터트리면 돼 45를 터트려 버리고 38과 72는 분리시키자라는 겁니다 그러면이 위에 38이 올라가게 돼요 33 38 81 그러면 38을 또 터트려서 위에 올리자라는 겁니다 그러면 최종적으로 어떻게 되겠어 이거를 예쁘게 바꾸면은 요렇게 되겠다라는 거예요 38을 끝까지 올렸어요 38 39로 넣었을 때 이렇게 39가 들어가지만 38은 위로 올라간다라고 얘기했고 여기에 38이 들어갈 것 같지만 실제로는 45가 허리에서 튕겨져 나가서 위로 올라갈 것 여기에 있을 것 같지만 이렇게 되면 안 되니까 최종적으로는 우리가 45가 가게 된다라고 말씀을 드리겠습니다 방금 전에 제가 말씀드린 부분 중에서 살짝 놓친 부분이 하나 있어요 다시 한번 설명을 드리자면 우리가 38 39인 상황에서 하나부터 갈게요 38이 위로 올라간다 용천한다라고 얘기했죠 그럼 38 45 72인 상황에서 지워져야 되는 하나가 튕겨져 나가야 되는데 그때 38이 아닙니다 왜 38 45 70이 순이니까 45가 지워지고 45가 튕겨져 그렇게 45가 33과 81 사이에 위치하게 되는데 그것도 안 되니까 결국 최종적으로는 45가 위에 자리잡게 되는 그럼이 삐칠이를 고상하게 다시 그리면 어떻게 된다 편의상 이렇게 동글뱅이로만 그리겠습니다 45가 되고이 45는 하나의 값만을 가지기 때문에 뭐가 가능하겠어 왼쪽과 오른쪽 둘만 가질 수 있다라는 것 자 근데 왼쪽 오른쪽 둘은 각각 가질 수 있어요 어떻게 가질 수 있어 33과 80 그렇게 약속했잖아 3345 81이 있는 상황에서 45를 허리로 올려버리면 33과 81은 더 이상 붙지 않고 쪼개진다고 그렇게 33과 82를 구현을 했습니다 그러면 33의 왼쪽에는 누가 위치하겠어요 33 왼쪽에는 원래 있던 듯 원래 33 왼쪽에 있던 대로 24가 위치하겠다라는 겁니다 그리고 24의 원래 왼쪽에 19 원래 오른쪽에 20실이 있었죠 자 그리고이 33의 오른쪽에는 무엇이 위치하는고 하고 보니까 방금 위에서 튕겨서 냈던 대로 38이 위치하겠다라는 겁니다 그리고 38 기준으로는 또 뭐 우리가 방금 전에 잘 튕겨져 낸 대로 35와 위치하겠다라는 거고요 자 그러면은 81의 왼쪽에는 무엇이 붙게 될까요 원래 81의 왼쪽에 있었던 72가 붙게 된다라는 겁니다 자 그리고 72는 뭐를 가졌더라 72는 우리가 60과 79를 원래부터 가지고 있었다라는 겁니다 그래서 60과 그리고 81의 오른쪽은 그대로 가면 됩니다 83과 95 얘는 애초에 떨어져 있지 않지요 원래 83과 95는 안 건드렸으니까 얘는 원래대로 82 90 98을 가질 수가 있게 된다라는 겁니다 조금 스플릿 과정에서 복잡해지기는 했지만 이런 식으로 우리가 뭐를 삽입입니다 삽입을 수행할 수 있겠다라는 거예요 데이터를 가운데에 튕겨내는 과정을 반복하겠다 그 과정에서 좌우가 분리된다는 점이 좀 유의를 해달라는 겁니다 자 엑서사이즈로 한번 연습을 해 볼까요 비트리와 관련된 엑서사이즈를 두 문제를 준비해 드렸는데 일시정지하고 푸시면 되겠죠 비대면 수업이니까 자 엑소사이즈 원을 한번 보겠습니다 차수가 32b3가 있어요 우측과 같이 표현을 했는데 여기에 g를 삽입한 후의 모습으로 옳은 것은 무엇일까요 참고로 여러분 굳이 말씀 안 드려도 되겠지만 acef 순으로 정렬이 되어 있다는 것 자체가 뭐야 하나의 노드 안에서 알파벳이 오름차순으로 정렬되어 있다라는 거죠 여기에 g를 삽입했습니다 차수가 3이라는 거에 주의하면 과연 어떻게 결말이 나게 될까요 1 2 3 4주는 골라 보시죠 자 풀고 오셨습니까 자 g를 삽입했을 때 우리가 어떤 식으로 전개되는지 한번 보도록 하겠습니다 루트에서부터 시작해서 차차 내려가는 탐색 과정을 거친다라는게 중요했지요 자 b보다 g는 큽니다 그래서 오른쪽 화살표를 따라가게 되고 ef 노드 리프의 벌써 도달을 했으니까 여기 g에 들어가면 돼요 아 이러면 안 되는데 왜 efg는 허용이 안 돼요 3차 비치기 때문에 많아야 알파벳이 두 개까지 밖에 없어야 된다고 그래서 efg를 잔인하지만 분리해 주도록 하겠습니다 f도 허리춤 위로 솟구쳐 올라가라는 거죠이랑 주인은 그렇게 떨어지게 되고 그 대신 어떻게 된다 윗자리에 f가 붙게 되는데 아 이번에는 붙어도 됩니다 왜 루트에는 루트도 어차피 노드니까 많아야 두 개까지 알파벳을 가질 수 있는데 아직 d밖에 없었잖아 그러니까 D 옆에 f가 조용히 들어가면 되는 구조다라는 거죠 그러면은 결국 어떻게 된다 F 이렇게 위에 그림이 좀 복잡하게 됐으니까 다시 한번 그려드리는 겁니다 df가 이렇게 그려지고 뒤에 왼쪽에는 원래 ac가 있었습니다 이건 불변이에요 a씨가 있었다라는 것은 불변이고 자 d와 F 사이에는 뭐가 위치하게 된다 2 가 들어가게 된다라는 겁니다 자 그리고 2와 g가 떨어져 있게 된다라고 말씀을 드렸죠 뭐를 기준으로 떨어져 있게 되겠어 F 기준으로 떨어져 있게 되겠다라는 거죠 여러분 feg가 이렇게 채워지는게 우리가 알파벳을 다시 한번 비교해서 요렇게 채워지는게 아니라 애초에 f가 분리돼서 2주가 떨어져 나간 겁니다 그 형태가 그 양태가 보존이 되니까 이런 빛을 나온다라는 거죠 정말 몇 번입니까 이렇게 그려져 있는 거 1번밖에 없군요 답은 1번이 되겠습니다 자 2번으로 가죠 역시 일시정지하고 한번 풀어보시기 바랍니다 차수가 3인 이런 비트의 35와 40을 순서대로 삽입할 때 옳은 것을 기억력이 골라 보시죠 시간 좀 드리겠습니다 자 어느 정도 푸셨습니까 요거 한번 풀어보겠습니다 차수가 3이라고 했기 때문에 많아야 데이터가 줄밖에 없다 근데 리프의 벌써 둘씩 꽉꽉 차 있는 거 보니까 뭔가 불안해요 이것저것 해야 될 것 같아 자 35를 순서대로 넣도록 하겠습니다 35를 넣었을 때 어떻게 된다 35 52 이렇게 들어가게 되는데 어 이러면 안 되지 결국 30과 50은 잔인하게 분리되고 만다라는 겁니다 35를 넣었을 때 35를 넣었을 때 어떻게 된다 35 52 3단 분리되고 35는 어디로 올라간다 루트 옆으로 올라간다 다행히 루트 옆엔 자리가 비어 있습니다 그래서 결국 20과 35가 되겠고요 23 15는 세 가지 자식을 가져야 되죠 비트리의 특성상 왼쪽 자식은 원래 있던 대로 쉽고 그리고 가운데와 오른쪽 자식은 방금 전에 절단돼 버린 30% 50이 되겠죠 자이 상태에서 기어 풀 수 있겠습니다 35가 삽입된 직후 루트 노대는 두 개의 값이 존재하게 되는군요이 상태에서 40노트로 하겠습니다 자 탐색 과정은 똑같습니다 23 15 보다 더 크죠 그럼 오른쪽으로 가겠습니다 그 상태에서 40을 넣어야 되는데 40은 50보다 작죠 그럼 얘 대신 그래도 B 트리에 규정에 위반하지 않지요 끝 니은 40이 삽입되는 과정에서 리프노드의 개수는 안전하죠 10 15 30 45 10 이렇게 돼 있는데 리프 노드 수는이 타원의 수입니다 이건 하나의 노드예요 10 15 두 개의 값을 가져도 하나의 노드기 때문에 리프 노드의 개수는 3개에서 불변입니다 디귿 35와 42 삽입되는 과정에서 3의 높이 아무런 변화 없군요 답은 기억 하나가 되겠죠 자 이렇게 b3는 균형을 잡는데 굉장히 특이하게 잡는다 노드의 데이터가 반드시 하나의 이유는 없고 여러 개일 수 있다 특히 m 차의 경우에는 엠마 1개까지 데이터가 들어갈 수가 있다 다만 리프 노드 높이 자체를 철저하게 관리함으로써 리프노드의 깊이를 철저하게 관리함으로써 이런 식으로 특이하게 균형을 잡을 수도 있구나라고 이해하고 우리가 넘어가도록 하겠습니다 자 이제 오늘의 핵심 아주 중요한 코어 해시 테이블에 대해서 살펴볼 건데요 먼저 해시 테이블이 어떻게 데이터를 적재하는지 살펴보기로 하죠 자 해시 테이블을 한마디로 요약하자면네 자리는 내가 결정한다라는 겁니다 여러분 이게 굉장히 트리오하는 구분되는 중요한 특성입니다 이게 아주 중요해요 왜 3의 경우에는 예를 들어 이 있을 때 내가 새로운 데이터 30을 넣으려고 해요 30을 넣으려고 했을 때 30의 자리를 30이 결정하나요 아니에요 사실 30의 자리는 30 단독으로 결정하는게 아니라 3 모양이 결정합니다 애초에 거기에 40이 있었기 때문에 30은 여기 가는 거예요 만약에 트리가 91에서 봐 그럼 30은 여기 같겠지 그러니까 3와 같은 대부분의 자료구조의 경우에는 내가 새로 들어갈 자리를 누가 결정하려면 기존에 있던 골격이 결정한다라는 겁니다 근데 사실 on my on네 자리를 내가 결정할 수 있다라는 거죠 im 내 스스로 결정할 수 있다라는 거지 그런 자료 구조가 바로 해시태그를 자료구조가 되겠습니다 자 왼쪽을 볼까요 릴리는 4번 자리에 들어갔고요 지우는 5번 자리에 들어갔고 규진은 6번에 서류는 8번에 들어갔습니다 여러분 제가 해시 테이블에 대해서 설명 안 드려도 규칙성이 보이니까 이거 뭐예요 멤버 이름 글자 수잖아 그래서 릴리는네 글자니까 4번에 들어간 겁니다 지우규진 서류니 위치랑 상관없이 릴리 본인이네 글자니까 당당하게 4에 입성을 한 거예요 내가 4니까 4로 간 겁니다 지우도 내가 오니까 5로 간 거고요 규진이도 내가 6글자니까 6으로 간 겁니다 이런 식으로 내 자신의 값 사립될 데이터의 값과 해상수의 의해서 삽입 위치로 결정되는 자료구조를 우리는 테이블과 같은 모양인데 해쉬함수를 썼다라는 의미에서 해시 테이블이라고 얘기를 합니다 해쉬함수라는 말이 굉장히 어렵게 느껴질 수도 있어요 사실 우리가 해쉬가 가장 익숙한 건 뭡니까 그 맥도날드 해쉬브라운 이런게 좀 더 익숙하지요 자 그런데 여기서 해쉬 같은 경우에는 무엇을 의미하냐면은이 위치를 결정해주는 함수를 의미합니다 비록 내 자리는 내가 결정하는 건 맞지만 내 값을 바탕으로 어떠한 원칙 하의 결정이 될 거 아니에요 여기서도 내 값을 바탕으로 무슨 원칙하의 결정됐어 글자 수로 간다라는 원칙하의 결정됐죠 글자 수로 간다라는게 해시 함수다라는 겁니다 즉 내 값과 내 값이 투입될 함수 그 두 가지에 의해서 삽입 위치가 결정된 자료구조가 해시 테이블이다라는 거고요 자 여기서 그러면 해쉬 함수를 뭐라고 표현할 수 있을까요 보통 해시함수는 데이터의 값을 임의의 x라고 뒀을 때 hx라고 표현합니다 해쉬니까 HG 근데 여기서 hx는 이렇게 표현할 수 있다는 거죠 영문면 기준 s의 철자 수 그러니까 서류에는 8번에 들어갔다라는 거지요 자 해시 테이블이 아주 강력하고 실생활에서 굉장히 많이 쓰이는 알고리즘 자료구조인 이유가 뭐냐면은이 친구는 충돌이라는 특수한 경우를 무시했을 때 스피드 삭제도 검색도 상수 시간만큼만 소요가 됩니다 사실 생각을 해봐 릴리가 들어간 때 무슨 품이 필요해요 릴리를 집어 위해서 0번 인덱스에 있는 자료를 찾아야 되나요 왜 찾아 10번에 있는 인덱스 왜 필요가 없어요 릴리는 뭐만 하면 되냐면 여기다가 lily를 계산해서 거기 쏴주기만 하면 되기 때문에 합이 마찬가지로 삭제나 검색에도 5원 상수만큼만 소요가 된다라는 겁니다 아니 그럼 이런 사기적인 구조를 왜 추천해서 배워요 이거 애초에 이거 배웠으면 되는 거 아니야 왜 그러냐면은 충돌요 문제가 치명적이어서 실제로는 그 어떤 상황에서도 모험만 소요된다 절대 아닙니다 절대 아니기 때문에 우리가 스리드 배우고 링크드리스도 배우고 다른 거 다 배웠다라는 거 다만이 충돌이라는 특수 케이스를 무시한다면 5원의 시간 복잡도가 소요되는 아주 강력한 자료구조가 되겠다라는 겁니다 자 그러면은 우리가 해시 함수를 어떤 식으로 구성할 수 있을까요 방금 같은 경우에는 우리가 사람 이름이니까 글자수라는 특이한 핵심 함수를 구성을 했는데 우리가 지금부터는 숫자를 넣는 우리 숫자를 보통 많이 컨트롤 하잖아 숫자로는 일반적인 상황을 생각을 해 볼게요 사는 여전히 왼쪽과 같이 13칸 0번부터 시작하니까 13칸입니다 13칸의 해시 테이블이라고 가정하겠습니다 참고로 말씀드리자면요 왼쪽에 보이는 것 0부터 12까지를 우리가 잘 알고 있는 인덱스라고 얘기하고요이 인덱스에 해당하는 즉 0번의 할당될 수 있는 칸이 있을 거 아니야 방배라고 했을 때 그 방이 방을 보통 뭐라고 얘기하냐면 양동이 할 때 그 버킷이에요 자 그리고 그 버킷은 말 그대로 0번 인덱스의 할당될 자리에요 근데 여러분 질이 반드시 방이 하나의 필요는 없죠 집에 방이 4개일 수도 있고 베이라고 하나요 아무튼 이렇게 여러 개의 방이 있을 수도 있잖아 그래서 하나의 버킷에 들어갈 수 있는 데이터의 숲이 한 칸에 들어갈 수 있는 데이터의 수를 우리가 슬롯이라고 얘기합니다 근데 보통 해시 테이블에서 우리가 버킷이 한 칸이 있을 때 슬롯이 여러 개일 수도 있어요 즉 0번 인덱스의 뭐네 개의 수가 들어갈 수 있지만 지금부터는 편의상 한 개의 수만 들어가는 상황 한 버킷 값 즉이 한 칸다 네모 처리한요 한 칸당 하나의 값만이 들어가는 상황을 가정하겠습니다 즉 버킷당 슬로수가 하나인 경우를 가정을 해보겠습니다 자 버킷 딱 하나의 숫자가 들어가는 버킷 땅 하나의 자연수가 들어가는 상황을 생각해 보지요 자 우리가 보통 어떤 식으로 해시함수 를 구성할 수 있냐면 데이터에이 버킷의 수 버킷의 수가 13개야 그러면 준 해시태이블의 크기가 13이라는 건데 이런 애시함수를 생각할 수 있다라는 거예요 x모드 14 여러분 모드가 뭔지 알고 있으니까 모드는 모듈로의 준말이고요 이거 뭐냐면 이건 나누라는 거예요 x를 13으로 나눈 나머지 즉 0부터 12까지라는 건데 얼마나 깔끔합니까 괜히 모듈로를 해시로 쓰는게 아니에요 모듈로를 해시로 쓰기 편한 이유가 뭐냐면 0번부터 12번까지 쑥 들어가거든요 나머지는 0부터 12까지 밖에 없으니까 크기가 13이다 그러면 0부터 12까지가 슉슉 들어갈 수 있다라는 거죠 자 근데 요렇게 들어가는 과정에서 우리가 생각해 볼 필요가 있는 개념이 있습니다 예를 들어 여기에 뭐 14가 들어가고 여기에 23이 들어갔다라고 쳤을 때 억제율이라는 개념을 생각할 수가 있어요 우리 해시 테이블의 크기는 뭐 13인데요 여기에 두 칸을 두 개의 버킷을 이미 쓰고 있다라는 거죠 우리 그런 경우에는 얼마만큼 적재가 되어 있느냐 포화가 되어 있느냐를 따지기 위해서 적재율이 13분의 2다라고 보통 이야기를 합니다 전체 크기 중에 저장된 버킷 수가 적재율이 되겠다라는 거죠 자 그러면 해쉬함수를 실제로 적용해 볼까요 어렵지 않습니다 hx는 x모드 13 x를 13으로 나눈 나머지 2호 해시 함수를 활용해서 50일 37 22 19를 제가 지금부터 넣어볼게요 자 여러분 51을 13으로 나누면 어떻게 될까요 편의상 바로 알려드리겠습니다 나머지가 12가 됩니다 자 그러면 51이 어디에 들어갔다 여기 들어간다 아니 푸시 함수가 주어졌으니까 바로 집어넣으면 되는 거예요 끝 그 다음에 37을 13으로 나누면 여러분 나머지가 11이거든요 그럼 37 여기로 가면 돼 13으로 나누면 나머지가 9가 되고요 그럼 여기는 19를 13으로 나누면 나머지가 6이 되고요 여기는 이게 전부다라는 거예요 해시 테이블에 50일 30실 22 19를 넣은 결과는 왼쪽과 같다 이때 적재를 정도 13분의 4가 되겠다라는 이게 해수함수의 기본이에요 자 그러면은 그토록 문제라고 했던 이게 5 아니면 이렇게 좋은 자료구조가 있을 수가 없는데 단 하나의 치명적 문제 충돌은 예제하고 있다라고 말씀드렸죠 충돌에 대해서 논의해 보도록 하겠습니다 좋아요 해시태그 정말 좋습니다 이렇게 집어넣으면은 순식간에 5억만의 삽입도 되고 집어넣는 방식도 해쉬함수 모듈을 얼마나 깔끔해 다 좋은데 충돌 문제가 있다라는 거예요 예를 들어 제가 여기에 12를 넣으려고 그래 12를 13으로 나온 나머지 12점 그래서 인덱스가 12인 곳을 딱 보는데 이미 50일이 차 있다라는 거죠 그렇다고 해서 제가 뭐라고 얘기했어요 한 바퀴 땅 슬로우스를 하나로 제가 최소화했다니까 그래서 여기 뭘 더 넣을 수는 데이터를 집어넣으려고 했는데 하필 위치가 중복돼 우린 이거를 보통 충돌이라고 얘기를 합니다 새로운 데이터를 집어넣으려고 하는데 아이고 이해시 이미 쓰고 있네 그런 경우에 우리가 충돌이라고 얘기하는데 그 충돌을 어떻게 해결할 수 있을까 진짜 개강 각색이에요 오늘은네 가지 정도를 보고 수업을 마치도록 하죠 첫 번째로 충돌을 해결하는 방법은 굉장히 직관적인 방법입니다 50일이 있는 상태에서 제가 25를 넣으려고 해요 25를 13으로 나눈 나머지는 12이거든요 어 50일이 이미 있네 그럼 어떻게 하면 되냐면 줄줄이 소세지처럼 꽤 잘하는 거예요 50일이 있어 야 근데 내가 쓸로나라고 했지 즉 값이 하나만 들어간다라고 얘기했지 이거를 꼬리에 그날 이야기도 아니고 꼬리에 꼬리를 보는 숫자라고 안전한 법은 없잖아 그래서 50일 뒤에 링크드 리스트 여러분 대표적인 알고리즘 링크들이 그래서 링크드 리스트 하나를 넣으면 되는 거 아니냐라고 어쨌든 하나의 뭔가를 넣으면 되니까 링크드리스트를 넣자라는 겁니다 약간 졸려 날 수도 있겠지만 하나만 넣는 듯이 슬로시 하나니까 하나만 넣는 대신 링크들이 형태로 넣자라는 겁니다 즉 50일이 있는데 25도 넣고 싶어 그럼 51 뒤에 25를 넣잖아요 근데 90도 나오려고 하는데 90도 나머지가 10이거든요 그럼 25 뒤에 90% 38도 넣고 38도 나머지가 12네 그럼 90수에 38도라는 겁니다 예를 들어서 구두는 나머지가 9죠 그러면 22g에 이런 식으로 우리가 꼬리에 꼬리를 모는 데이터이야 이렇게 꼭꼭으로 넣자라는 걸 뭐라고 얘기하냐면 체인을 친다 체인닝을 이용한 충돌 회피라고 얘기합니다 링크드리스터와 같은 연결형 자료 구조를 이용해서 동일한 위치에 데이터를 연결해서 삽입하면 충돌 문제를 해결할 수 있다라는 거예요 위치는 동일합니다 중복이 되더라도 그 인덱스를 고수하자라는 거예요 뭐 시비가 또 나왔어 그러면 12 위치에 똑같이 넣는데 꼬리에 꼬리를 물면서 이게 바로 체인닝을 이용한 충돌 회피가 되겠습니다 자 근데 이거는 느낌이 오겠지만 인덱스가 유지된다는 점에서는 참 좋아요 내가 25나 90 같은 중복되는 해시값을 넣는다 하더라도 인덱스인 gb가 유지된다는 걸 참 좋거든 근데 이게 애초에 합당한가 즉 우리가 한 버킷에 한 슬롯을 하나의 값만을 넣겠다라는 건데 그러면은 사실 상식적으로 이렇게 꼭 고무를 허용해서 되겠냐라는 거예요 이렇게도 우리가 우회적으로 할 수 있겠지만 하나의 인덱스의 하나의 데이터만을 배정하는 해시 테이블에 정신 그 정신을 살린다 차원에서는 얘는 부적합할 수 있다라는 거야 그래서 애초에 51 다음에 25가 있을 때 즉 25라는 22가 중복되는 값을 넣고자 할 때 빈 다른 곳에다 25를 더 예를 들어 어 여기 비어 있네 대신 여기 놓지 뭐 이런 식으로 우리가 기어 있는 다른 데에 넣는 방식을 생각할 수가 있어요 우린 이걸 뭐라고 얘기하냐면 비어있는 주소에 갖다 놓는다 해서 오픈 어드 레싱 방식이라고 얘기합니다 즉 체인인과 대비되는 방식 비교되는 방식이 오픈 어드레싱 방식인데 지금부터 살펴볼게 바로요 오픈 어드레싱 방식이 되겠습니다 남은 세 가지 모두 오픈 어드레싱이에요 첫 번째 오픈 어드레싱의이 원조 조상격이라고 할 수 있는 미니어프로빙을 보도록 하겠습니다 자 지금부터 계속 25 90 38순으로 넣어 볼 건데 25 90 38은 애써 귀찮게 나눠보지 마세요 전부 나머지가 12입니다 즉요 25 90 38이 없는 상황에서 예 없다라고 쳤을 때 22 칸에서 계속 중복이 일어난다라고 생각하시면 돼요 자 25를 넣는 상황을 생각해 보겠습니다 제가 말씀드렸죠이 오픈 어드레싱 방식은 빈칸을 대신 찾자라는 거예요 자 50일은 안 돼 52를 침범할 수는 없다라는 거죠 그럼 다른 빈칸을 찾겠다라는 건데 여러분 상식적으로 우리 헬스장 다니는 걸 한번 생각을 해봐 헬스장을 다니는데 사물함을 열었어 누가 쓰고 있네 그럼 어디 봐요 참 돌아가서 아니잖아 옆에 사무라면 열어보잖아 그런 것처럼 헬스장 사물함처럼 여기가 아니야 그럼 옆에 거 여러분 되는 거 아니야 특히 옆에라 하더라도 오른쪽 어떤 다음 거를 열어보기 마련이니까 오른쪽 걸 열어보겠다는 거죠 12 다음은 뭐예요 13은 없으니까 0으로 돌아오게 됩니다 즉 12 다음이 0으로 돌아와서 보는데 영에는 아무것도 안 차 있어요 지금 제가 일부러 채운 건지 원래는 안 차 있는 겁니다 그러면 여기에다가 25를 넣겠다라는 거예요 자 그러면 요거 없다 생각하고 자이 상태에서 90을 또 넣으려고요 90은 나머지가 12라고 했어요 그래서 여기를 보는데 아이고 이미 50일 차 있네 그래서 한 칸 뒤를 봐요 근데 어 25도 차이네 그러면 또 열면 되는 겁니다 여러분 오른쪽 사물함 잠겨 있다고 포기할 거예요 아유 오늘은 운동하기 좀 그런 날인가 보다 이러면 안 되지 운동해야죠 그래서 오른쪽에 오른쪽을 보는 겁니다 여긴 다행히 열려 있어 그래서 여기에 90을 이런 식으로 선형적으로 다음 빈칸을 찾아서 그곳의 데이터를 대신 적재하는 방식을 우리는 선형조사법 영어로 풀면 리니어 프로빙이라고 얘기를 합니다 선형조사법 리니어 프로빙을 이용해서 충돌을 회피한다라고 얘기해요 예를 들어서 우리가 32를 여기서 넣어 볼까요 자 다 지우고 이렇게 [음악] 값을 다이 중복되는 값까지 다 넣은 상황에서 32를 넣는다고 생각을 해봅시다 자 32를 넣는다고 얘기했을 때 32는 모듈로 13을 하면 나머지가 6이거든요 어 6은 이미 차이슨 그러면 뭘 본다 6기에 있는 7을 본다 이렇게 데이터를 채우는 방식 이게 바로 해시 테이블에서의 리니어 프로빙 충돌 회피 기법이 되겠습니다 아하 이런 식이면 우리가 충돌을 회피해서 또 이러면은 뭐가 또 충족이 됩니까 우리 해시 테이블의 목표는 적당한 크기를 설정해서 빈칸 곳곳에 빈칸 여러 곳에 분산돼서 데이터가 적재하도록 하는게 목표인데 그게 깔끔하게 이루어졌죠 억지로 링크들이 스타 안 쓰고 여러 빈칸에 데이터가 적재가 됐다 근데 리니어 프로빙 참 좋아 보이는데요이 친구도 아쉬운 점은 있어요 두 가지가 있습니다 첫 번째 데이터를 넣었다가 지운 상황을 애매해 줘요 25 38이 있다라고 했을 때 우리가 90이 있었어요 원래는 90이 있는 상황이다라는 거죠 자요 상태에서 제가 90을 지우도록 하겠습니다 90을 지워요 90을 지으면 날아갑니다 알아가는데 자 90이 원래 위치했으나 데이터 삭제를 인해서 비어 있다는 거예요 25 90 38순으로 쫙 들어가 있었는데 90이 삭제됐습니다 자 이제 여기에 우리가 내가 뭐를 확인하려고 하냐면 38이 존재하는지 확인하려고요 삽입이 아니라 탐색인 겁니다 탐색 38이 존재하는지를 확인하려고 하는데 자 38이 존재한지는 어떻게 확인해요 38을 13으로 나눴을 때 12가 됩니다 그래서 내가 12칸부터 조사를 시작하겠다는 사실을 알고 있어요 그래서 51을 보는데 어이구 여기 38이 없네 그럼 혹시 니니어 프로빙으로 인해서 한 칸 밀린 거 아닌가라고 해서 0번 칸을 봐요 어 25 이것도 아니네 어 그럼 38을 찾기 위해서 여기를 그러면 리니어 프로빙에서 계속 계속 가서 38이 채워줬으면 애초에 여기에 뭔가 값이 있어야 될 텐데 값이 없네 비어인데 아 그러면이 테이블에 38이 없나 보구나 하고 돌아서게 된다는 근데 여기서 발걸음 돌리면 큰일나요 왜 38 여기 있거든요 아이 문제가 있었구나 데이터를 삭제를 하면은 우리가 다음 걸 안 보게 돼요 그래서 이런 탐색 같은 경우에는 삭제가 치명적 결과로 이어질 수 있다는 겁니다 38이 있는데 없다라고 말하게 된다는 거죠 그런 경우에는 우리가 어떻게 해야 될 생각보다 해결법이 단순합니다 90을 지을 때 빈칸으로 지우지 마시고 지운 흔적을 남기자라는 거예요 즉 1번 카드는 비록 90은 없어요 90이라는 기억은 없어요 없어야 되지만 뭔가가 있었다 사라짐이라고 얘기해 주자라는 거예요 그러면 38 탐색이 가능해집니다 왜 38 어 12회 12 보니까 51 아니야 선형조사법에 의해서 25 아니야 어 뭐 있었는데 지워졌나 보네 그러면 다음 걸 봤는데 2 30% 이렇게 가자라는 겁니다 자 그러면 조금만 더 머리를 조금 더 복잡하게 굴려보자면이 뒤에는 언제 사라지면 되겠어요 새로운 값이 투입될 때 그때 뒤에 대신 그 새로운 값을 집어넣어주면 되겠죠 이렇게 우리가 삭제 직후에는 뭔가 증빙할 만한 곳 얘는 뭔가 있었어라는 거를 남겨주는 센스가 필요하다라는게 선형조습하고 회사의 첫 번째 문제와 해결 방식이겠어요 자 근데 선형조사법이 이것만 문제인 거야 두 번째 문제 선형조사법 상황을 다시 한번 볼까요 37 51 25 90 38입니다 자 이렇게 떨어져 있지만 결국에는이 나머지라는 거는 윤회잖아요이 한 칸이 지비에서 13이 될 때마다 0으로 돌아오는 구조이기 때문에 사실상 뭐가 한 덩어리냐면 근데 이거 좀 보기 그렇지 않습니까 해시 테이블에 목표는 뭐냐면은 빈칸을 최대한 영리하게 분산해서 쓰자라는 건데 지금 얘는 분산이 됐어요 무려 5가지 하나로 붙어 있는 거야 이건 거의 클러스터 군집이나 다름이 없다라는 거죠 그래서 이런 식으로 클러스터가 생기면 마치 우리가 혈전이 생기면 몸에 치명적 결과를 주는 것처럼 이렇게 묶여서 데이터가 돌아다니게 되면은이 근방에서 데이터를 삽입할 때 계속 뒷조사를 하게 되는 문제가 발생됩니다 예를 들어 내가 12도 아니고 11월 삽입하려고 생각을 해봐 그러면이 혈전으로 인해서 어 여기 아니네 여기 여기 아니네 여기 여기 아니네 여기 아니네 여기 이렇게 혈전을 계속 돌아다니는 문제가 생긴다라는 거죠 즉 이렇게 한 칸씩만 가로 사물함 옆 사물함 우리가 헬스장에서 모두가 자기 사물함이 차 있으면 옆 사물함을 돌아다니게 되면은 특정 공간이 이렇게 꽉 들어차게 되는 문제가 혈전처럼 발생한다라는 거죠 이걸 막기 위해서 우리가 어떤 생각을 할 수 있느냐 이런 생각을 할 수 있다는 50일 다음에 25를 넣어 그럼 50일 다음에 25를 넣는 건 알겠어 근데 25랑도 겹쳐 예를 들어 25가 있는 상태에서 90을 넣겠다라고 얘기했을 때 50일이란 겹치고 25랑도 겹치죠 그러면은 가로 역할을 넣지 말고 좀 더 역할은 없다라는 겁니다 구체적으로 어떻게 넣자고 처음에는 바로 한 칸 옆에 넣어 근데 그 다음에는 두 칸이 아니라 2 제곱한 즉 4칸 뒤에 넣고 세 번째는 흥미롭게도 3이 제곱 즉 9칸 뒤에 넣자라는 겁니다 그러면 어떻게 된다 오실 뒤에 25를 넣으려면 한 칸 뒤니까 여기 들어가게 돼요 근데 그 다음으로 중복되는 90을 넣기 위해서는 50일에서 여러분 50일에서입니다 최초 충돌 발생지에서 기준입니다 최초 충돌 발생지에서 4칸 한 칸이 아니라네 칸 뒤를 가게 돼요 한 칸 두 칸 세 칸네 칸 90을 넣겠다는 거예요 그래도 충돌돼 그러면 가서 여섯 일곱 여덟 아홉 번째 여기 넣겠다라는 거 이러면 혈전이 훨씬 덜 생기죠 지금 많아야 연속된게 몇 개야 세 개밖에 혈전이 안 생긴다는 채우는 거 이걸 바로 우리가 2차원 프로비 또는 쿼드로키 프롭이라고 얘기를 합니다 이건 무슨 장점이 있다 혈전 안 됩니다라는 장점이 있다라는 건데 을의 봤자 사실 혈전이 아예 안 생길 수 없어요 왜 내가 예를 들어 11과 관련된 걸 너는 그러면은 좀 혈전이 덜 생길 수 있겠죠 근데 내가 예를 들어서 해시값 즉 인덱스 값이 12인 놈을 계속 넣는다고 생각을 해봐 그러면 어쨌든 22를 기준으로 했을 때는 넣는 위치는 고정입니다 한 칸 뒤네 칸 뒤 아홉 칸디 16가지 결국 22라는 굴레의 들어가지는 위치지 즉 충돌이 발생하는 위치가 동일할 수밖에 없다는 거 첫 번째 충돌 위치도 두 번째 충돌 위치 세 번째 충돌 위치도 동일할 수밖에 없다라는 겁니다 예를 들어 여기에 뭐 -1을 넣는다고 생각을 해요 -1도 나머지는 12이기 때문에 여기에 들어가야 되는데 어 여기 이미 차 있으니까 한 칸 어 한 칸이 차 있으니까 내가 결국 세 번에 충돌을 똑같이 겪는 건 매양가요 그래서 우리가 똑같은 시비라 여기가 중요합니다 똑같은 12라는 값이라 하더라도 x가 다르다면은 점핑하는 선수가 달라야 되지 않나라는 생각을 하게 돼요 그래서 우리가 생각하는 끝판왕 헬싱이 뭐냐면 오늘의 마지막 이론 슬라이드가 되겠습니다이 중에 더블헤싱이 되겠습니다 일단 파는 미치는 h로 정하는 건 똑같아요 똑같은데 충돌이 발생할 경우에는 함수를 하나 더 쓰자라는 거예요 fx라는 추가해싱함수 별도의 핵심 함수를 이용해서 우리가 건너뛸 칸 수를 결정하자라는 겁니다 다시 말해서 충돌이 발생한다 그러면은 애초에 서로 다른 수로 충돌이 발생하면은 건너뛰는 칼 수도 다르게 하자라는 거예요 여러분 이게 중요합니다 자 우리가 25 90 38을 넣잖아요 25 90 38 넣는다라고 얘기했을 때이 세 개의 공통점은 뭐냐면은 모두 해시값이 hx가 12라는 공통점을 가져요 그래서 똑같은 12에서 출발하면 충돌도 똑같은 스텝을 반복할 수밖에 없다라고 말씀드렸습니다 그거는 리니어든 쿼드로 튀기는 똑같았어요 쿼드러치기를 하더라도 결국 똑같은 충돌의 전처를 밟을 건 똑같잖아 그래서 우리가 어떤 생각을 하게 되냐이 피부 938이 똑같이 h 값을 지비로 가죠 그러면 f값도 한번 잡자라는 것 자이 친구의 f값을 계산하면 어떻게 되냐 f값을 계산하게 되면은 f는 새로운 함수 2 + x 모드 7을 설정하자라는 거예요 자 2 + x모드 칠하면 어떻게 되겠습니까 25를 7로 나눈 나머지 여러분 x모드 7을 먼저 계산하고 2를 더하겠습니다 25를 7로 나눈 나머지는 4거든요 그러니까 f-25는 이렇게 돼요 [음악] [음악] 이용하는 [음악] 문제인데 요거 한번 풀어 보시고 다음 시간에 제가 해설과 함께 내용을 나가 보도록 하죠 자 저희 오늘 수업은요 정도로 마무리하도록 하겠습니다 여러분 대단히 고생 많으셨고요 저희 12주차 영상에서 다시 뵙겠습니다 건강관리 잘 하시고요 여러분 다음 시간에 뵙겠습니다