[음악 재생] DOUG 로이드 : 그래서 우리는 가까이 인칭했습니다 가까이 데이터의 성배 우리가 삽입 할 수있는 구조, 하나 에,에서, 삭제 및 조회 일정 시간에. 권리. 즉, 목표의 종류이다. 우리는 할 수 있어야합니다 물건 아주, 아주 빠르게. 

우리가 여기에 때를 발견 우리는 시도에 대해 얘기? 음, 살펴 보자. 그래서 우리는 몇 가지 봤어요 다른 데이터 구조 즉, 매핑을 처리 키 - 값 쌍 소위, 데이터의 일부 조각을 매핑 데이터의 다른 부분에 그래서 우리는 어디에서 찾을 알고 구조 정보를 제공합니다. 

따라서 배열, 예를 들면, 키 인덱스 또는 소자 배열 위치 0 또는 배열 1 등. 및 값은 데이터 인 즉, 해당 위치에 존재한다. 그래서 배열 0에 무엇을 저장? 무엇은 대 어레이 (1)에 저장된다 0과 1 키가 될 것이다. 

해시 테이블로 그것은이다 같은 생각의 일종. 해시 테이블, 우리는이 해시가 해시 코드를 생성하는 기능. 그래서 키는 데이터의 해시 코드이다. 및 값, 특히 우리는 체인에 대해 이야기 해시 테이블에 대한 비디오, 데이터 링크 된 목록입니다 즉, 그 해시 코드에 해시. 권리. 또 다른 방법은 어떻습니까 이 방법,하지만? 방법에 대한 어떤 곳 키는 고유 보장 해시 테이블, 우리가 할 수 달리 2 개의 데이터와 끝까지 같은 해시 코드를 가진. 그리고 우리가 처리해야 그 중 하나 프로빙 이상 바람직하게는 그 문제를 해결하기 위해 체인. 

그래서 지금 우리가 보장 할 수 우리의 키는 고유합니다. 그리고 우리의 가치는 무엇 인 경우 쉬운처럼 뭔가 여부를 우리에게 그와 같은 사실과 거짓 정보의 여부를 그 조각 구조에 존재? 부울 조금처럼 간단 할 수있다. 현실적으로는 아마 조금 더 가능성 바이트. 하지만 그보다 훨씬 작다 50 문자열 어쩌면 저장, 예를 들면. 

시도 따라서, 해시 테이블과 유사하게, 이는 결합 배열과 연결리스트, 시도 배열을 결합, 구조 및 포인터 서로에 데이터를 저장하도록 의 흥미로운 방법 에서 꽤 다른 우리가 지금까지 본 적이 아무것도. 이제 로드맵 데이터를 사용 이 데이터 구조를 탐색 할 수 있습니다. 그리고 우리는 따라 할 수있는 경우 로드맵, 우리가 할 수있는 경우 로부터 데이터를 따르 끝으로 시작, 우리는거야 데이터 여부를 알 트라이에 존재합니다. 

그리고 우리는지도를 수행 할 수없는 경우 전혀 종료 의미에서, 데이터가 존재할 수 없습니다. 또, 키는 여기에 있습니다 고유합니다. 그래서 해시 테이블과는 달리, 우리는거야 여기에 충돌을 처리해야합니다. 그리고 데이터의 두 개의 조각 없음 똑같은 로드맵을 가지고 하지 않는 데이터는 동일하다. 

우리는 존을, 다음 삽입하는 경우 우리는 존을 검색합니다. 즉, 두 개의 동일한 조각의 데이터, 오른쪽, 우리는을 통해 찾고 있습니다. 그러나 그렇지 않은 경우, 어떤 데이터의 두 가지가 있습니다 독특한 로드맵을 보장 이 데이터 구조를 통해. 그리고 우리는 살펴거야 잠시이 시각적. 

우리는에 노력하여이 작업을 수행 할 수 있습니다 새로운 데이터 구조를 생성, 다음 키 값 쌍을 매핑. 이 경우, 우리는 사용하지 않을거야 부울 같은 간단한. 우리는 실제로 문자열을 저장합니다. 그리고 그 문자열을 것입니다 대학의 이름. 

그리고 키는 한 해가 될 것입니다 그 대학이 설립되었을 때. 대학에 대한 모든 년 네 자리가 될 것입니다. 그래서 우리는에 그 4 자리 숫자를 사용합니다 이 데이터 구조를 통해 이동합니다. 그리고 우리는 다시 볼 수 있습니다, 방법 우리는 단지 두 번째에 그렇게. 

경로의 끝에서, 우리는 이름을 볼 수 있습니다 해당 대학의 그 키에, 그 4 자리 숫자. 트라이의 기본 개념 우리는 중앙 경로가 있습니다. 그래서 나무처럼 그것에 대해 생각합니다. 그리고 이것은 철자 유사 그리고 나무에 개념. 일반적으로 우리가 생각하면 현실 세계에서 나무, 그들은에서의 루트를 지상 그들은 위쪽으로 성장 그들은 지점을 가지고 그들은 잎을 가지고있다. 그리고 기본적으로 아이디어 트라이는 똑같 그 루트는 고정되어 제외 하늘에서 어딘가에. 그리고 잎은 아래에 있습니다. 

그래서 나무를 복용 같은 종류의 그냥 거꾸로 뒤집기. 하지만 여전히 가지가 있습니다. 그리고 그는 우리의 경로가 될 것이다, 사람들은 우리의 연결됩니다 잎에 루트에서. 이 경우, 그 경로, 그 지점 우리에게 숫자로 표시되어 있습니다 어떤 방법으로 우리가 어디에서 이동합니다. 

우리는 0을 참조하면, 우리는이 지점 아래로 이동 우리가 1을 참조하면, 우리는이 지점 아래로 이동 등 등. 음, 이것은 무엇을 의미합니까? 글쎄, 그건 것을 의미한다 모든 연결 지점에서 그리고 모든 노드 중간 모든 지점, 수 (10)이있다 우리가 갈 수있는 곳. 그래서 10 포인터가있다 모든 위치에서. 

시도가 얻을 수있는 곳이있다 누군가 협박 조금 누가 것은 많이 없습니다 전에 컴퓨터 과학의 경험. 하지만 시도는 정말 꽤 굉장하다. 그리고 당신이있는 경우 그들과 함께 작업 할 기회 당신은 파고-에 기꺼이 그들과 함께 실험, 그들은 정말 아주 흥미있어 데이터 구조와 함께 작동합니다. 우리는 요소를 삽입 할 경우 트라이에, 모든 우리가해야 할 올바른 경로를 구축한다 잎에 루트에서. 여기에 무엇을 모든 단계를 따라입니다 방법은 다음과 같을 수 있습니다. 우리는 새로운 데이터를 정의하는거야 새로운 노드의 구조는 트라이를했다. 

그리고 그 데이터의 내부 구조 두 가지가있다. 우리는을 저장하는거야 대학의 이름입니다. 그리고 우리는 저장거야 포인터 배열 동일한 유형의 다른 노드. 그래서, 다시, 이것은 그런 종류입니다 사방의 개념 우리는 10 수에이다 우리가 갈 수있는 곳. 우리는 0을 참조하면, 우리는이 지점을 아래로 이동합니다. 우리가 1을 참조하면,이 지점, 등 등 등. 우리가 9를 말한다면, 우리는이 지점을 아래로 이동합니다. 모든 연결 지점에 따라서 우리는 10 가능한 장소를 갈 수 있습니다. 그래서 각 노드가 포인터 (10)를 포함한다 (10) 다른 노드에 다른 노드에. 

그리고 우리가 저장하고있는 데이터는 대학의 이름 만. 그럼 트라이를 구축 할 수 있습니다. 이제 몇 가지를 삽입하자 우리의 트라이에 항목. , 맨 위에 그래서 이것은 우리의 루트 노드입니다. 이것은 아마도 뭔가 될 것입니다 당신은 선언을 전역 것입니다. 그리고 당신은 유지 전역거야 항상이 노드에 대한 포인터. 

당신은 말할거야 뿌리는 동일, 당신은있어 자신에게 트라이 노드를 MALLOC 것. 그리고 당신은 결코 않을거야 다시 뿌리를 터치합니다. 당신이 원하는 때마다 를 탐색 시작 다른 포인터를 설정 같은 TRAV으로, 루트와 동일, 이는 예 I이고 내 동영상의 많은에 사용 여기에 스택과 큐에 링크 목록 등등. 

당신은 다른 포인터를 설정 순회 TRAV했다. 그리고 당신은 이동 TRAV를 사용 데이터 구조 내지. 그럼이 볼 수있는 방법을 살펴 보자. 그래서 지금, 무엇을 노드가 생겼는데? 글쎄, 우리의 데이터로 구조의 선언은, 표시 우리는 문자열을 가지고있는 이 경우에는 비어 있습니다. 여기에 아무것도 없습니다. 

10 포인터의 배열. 그리고 지금, 우리 만 이 트라이 1 노드를 가지고있다. 거기에 다른 아무것도 없습니다. 그래서 그 모든 10 포인트 포인터를 null로. 즉, 빨간색이 표시거야. 

의 문자열 하버드를 삽입 할 수 있습니다. 이제 대학 삽입하자 이 트라이에 하버드, 어떤 올해 1636 년에 설립되었다. 우리는 키를 사용하려면, 1636, 우리가있어 어디 우리에게 얘기를 트라이에 하버드를 저장하는 것. 이제, 우리는 어떻게 할 수 있는가? 

그것은 다음과 같을 수 있습니다. 우리는 루트에서 시작합니다. 그리고 우리는 우리가 갈 수있는이 10 곳이있다. 루트는 그냥 같다 트라이의 다른 노드입니다. 우리가 여기에서 갈 수있는 10 곳이있다. 

어디 우리가 아마 싶어 키가 1636 인 경우 이동? 정말 두 가지 옵션이있다. 권리. 우리는에서 키를 구축 할 수 있습니다 오른쪽에서 왼쪽으로, 6으로 시작합니다. 아니면 우리는에서 키를 만들 수 왼쪽에서 오른쪽으로 1부터 시작. 

아마 더 인간 직관적 우리에게 있습니다 이해하기 그냥 왼쪽에서 오른쪽으로 이동합니다. 그래서 내가 삽입 할 경우 이 트라이에 하버드, 아마 시작하려면 루트에서 시작하여, 제 10 옵션을보고 내 앞에, 그리고 말 나는 1 길을 가고 싶어. 그래. 

이제 1 경로는 현재 null입니다. 그래서 나는 그 길을 계속 진행하려면 트라이에이 요소를 삽입하려면, 나는 1가, 새 노드를 MALLOC해야 이 지적하고 나는 갈 수 있어요. 

그래서 나는 기본적으로 오전 포인트 어디 서있어 또는 트리의 루트 트라이 10 가지가있다. 그러나 각 지점이있다 그것의 앞에 문입니다. 권리. 아무것도 없기 때문에 다른 사람이있다. 안전한 통로 없습니다. 즉 아무 것도 없다는 것을 의미합니다 그 지점의 아래. 나는 건물을 시작하려면 뭔가, 나는 문을 제거 할. 나는 문을 제거 할 숫자 1의 앞. 그리고 나는 그것을 걸어 싶습니다. 그리고 구축하려는 나를 위해 다른 곳으로 이동합니다. 

그리고 그게 내가 여기에 무슨 짓을했는지입니다. 그래서 1은 더 이상 null로 지적 없습니다. 나는 지금 여기에 가서하는 것이 안전 말했다했습니다. 나는 다른 노드를 구축했다. 그리고 해당 노드에 도착하면, 나는 만드는 또 다른 결정을해야합니다. 어디 여기에서 갈 거지? 

글쎄, 난 이미 1 내려 갔어요. 그래서 지금은 아마 6을 가고 싶어. 권리. 다시 말하지만, 내가 선택할 수있는 위치가 10 개. 그래서 지금은 숫자 6을 가자. 그래서 문을 취소 번호 6의 앞. 그리고 나는 거기 걸어. 그리고 나는 또 다른 노드를 구축 할 수 있습니다. 그리고 나는 또 다른 연결 지점에 도달했습니다. 

다시 말하지만, 나는 10를 선택할 수 있습니다 내가 갈 수있는 곳합니다. 나는 1-6 이동했습니다. 그래서 지금은 아마 3에 가고 싶다. 3, 아무 곳에 나 갈 수 없다. 그래서 방법을 취소해야 자신에게 새로운 공간을 구축 할 수 있습니다. 그리고 내가 가고 싶어 3에서? 나는 아래로 6 가고 싶어. 

그리고, 다시, 나는에 있었다 그것을 할 수있는 방법을 취소합니다. 그래서 지금 만들고 삽입 내 키를 사용했습니다 노드는이 트라이를 구축하기 시작합니다. 나는 루트에서 시작했습니다. 나는 1636 아래로 갔어요. 그리고 지금은 맨 아래에 있어요 이 노드에. 그리고 당신은 할 수 있습니다 화면에 볼. 

그것은 노란색으로 강조합니다. 나는 현재 나는 곳이다. 내 키가 이루어집니다. 내 키의 모든 위치를 소진했다. 그래서 나는 더 이상 갈 수 없습니다. 이 시점에서, 모든 I 그래서 정말 좋아, 말을하기 만하면됩니다. 그것은 종류의보고처럼 지상에서 아래로, 당신이 상상하는 경우 직접 경로의 종류 등 다른 연결이. 정렬의 아래 종류의보고 지상에 하버드 페인팅 스프레이. 즉,이의 이름입니다. 즉,이 위치에서 무엇을 알고있다. 우리는 루트에서 시작하여 우리는 내려 가지 경우 1 다음 6 다음 3 다음 6, 우리를 어디? 그런데 우리는 아래를 보면 우리는 하버드 참조 우리는 하버드는 것을 알고있다 방식에 따라 1636 년에 설립 우리는이 데이터 구조를 구현하고있다. 그래서 희망 간단했다. 우리는 두 개 더 삽입을 할 것입니다. 그리고 희망이에 도움이됩니다 볼이 두 번 더 수행. 

이제, 다른 대학을 삽입 할 수 있습니다. 의이 트라이에 예일대를 삽입 할 수 있습니다. 예일대는 1701 년에 설립되었다. 그래서 우리는에서 시작합니다 루트, 우리가 항상있다. 그리고 우리는 순회 포인터를 설정합니다. 우리는을 통해 이동하는 것을 사용하는 것입니다. 우리가 할 첫 번째 일이 수행은 1 길을 갈 것입니다. 즉 우리의 키의 첫 번째 숫자입니다. 다행히도, 그러나, 우리는하지 않습니다 모든 작업이 시간을해야한다. 1 경로는 이미 지워졌습니다. 나는 이전에 때를 지워 1636에서 하버드를 삽입했다. 그래서 안전하게 이동할 수 있습니다 1 아래로 그냥 이동합니다. (1)를 아래로 이동 할 수있는 경우에. 

하지만 이제 나는 7에 가고 싶다. 나는 6시에 길을 지워. 나는 안전하게 할 수있는 알고 6 경로를 아래로 이동합니다. 하지만 7 경로에 진행해야합니다. 그래서 내가 어떻게해야합니까? 음, 그냥 예전처럼, 난 그냥 필요 게이트를 취소, 비켜, 그리고 7 경로에서 새 노드를 구축 할 수 있습니다. 그냥이있다. 

그래서 지금은 1 다음 7을 이동했습니다. 그리고 지금, 알 내가 종류 해요 이 새로운 subbranch에. 권리. (16)에서 다른 모든 에, 나는 걱정하지 않는다. 나는 16 아무것도 아니에요. 나는 17 물건을하고 있어요. 

그래서 지금 17에서에, 나는에있다 일종의 여기에 새로운 산책로 불꽃. 다음 숫자는 내 키는 0입니다. 나는 분명히 어디서든 얻을 수 없습니다. 난 그냥이 노드를 구축했다. 그래서 나는 더있다 알지 앞으로 여기에서 경로. 그래서 하나에게 자신을 확인해야합니다. 

그래서 나는 새 노드를 MALLOC 거기에 0 점을 가지고있다. 그리고 한 번 더, 나는 malloc에 새로운 노드가 하나의 점을 가지고있다. 다시 말하지만, 난 내 키, 1701 소진했습니다. 그래서 아래로보고 나는 예일 페인트 스프레이. 즉,이 노드의 이름입니다. 

그리고 지금은 그 어느 예일 있는지 확인해야하는 경우 이 트라이에, 나는 루트에서 시작되어, 나는 1701 아래로 이동, 아래로 본다. 그리고 예일 스프레이를 참조하는 경우 다음, 바닥에 그려진 나는 예일이 트라이에 존재하는 것을 알고있다. 이제 한 번 더 해 보자. 의이에 다트머스를 삽입하자 1769 년에 설립 된 트라이. 

다시 루트에서 시작합니다. 내 키의 내 첫 번째 숫자는 1입니다. 내가 안전하게 그 길을 이동할 수 있습니다. 즉 이미 존재합니다. 내 키의 다음 숫자는 7이다. 내가 안전하게 그 길을 이동할 수 있습니다. 그것은뿐만 아니라 존재한다. 

나의 다음은 6입니다. 여기에서, 나는 현재 나는 곳에서 그 중간 노드가 노란색, (6)는 현재 오프 잠겨 있습니다. 내가 그 길을 가고 싶은 경우, 내가 직접 구축 할 수 있습니다. 그래서 나는 새 노드를 malloc에​​ 있습니다 거기에 6 점을 가지고있다. 그리고, 다시, 나는 해요 여기에 새로운 산책로 타오르는. 

그래서 나는 새 노드를 MALLOC에서되도록 지금 그 node-- 경로 번호 9--과 나는 1769 여행, 나는 아래를 보면. 아무것도 현재 없습니다 이 페인트 스프레이. 나는 다트머스을 작성할 수 있습니다. 그리고 삽입 한 트라이에 다트머스. 

그래서 삽입의 트라이에 일. 이제 우리는 물건을 검색 할 수 있습니다. 우리는 어떻게 트라이에 물건을 검색 할 수 있습니까? 음, 거의 같은 생각입니다. 이제 우리는 단지 키의 숫자를 사용 우리는 루트에서 탐색 할 수 있는지 확인하기 위해 우리는 트라이에 가고 싶은 곳으로. 

우리는, 어떤 시점에서 막 다른 골목에 충돌하는 경우 우리는 그 요소가 존재할 수 있음을 알 그렇지 않으면 그 경로는 것 이미 삭제되었다. 우리는 모든 방식을 한 경우 결국, 모든 우리가해야 할 아래로보고 그건 있는지입니다 우리가 찾고있는 요소입니다. 그것은 성공 인 경우. 그렇지 않은 경우, 실패합니다. 

그럼 검색하자 이 트라이 하버드. 우리는 루트에서 시작합니다. 그리고 다시, 우리는거야 탐색 포인터를 만들 우리를 위해 우리의 이동을합니다. 루트에서 우리는 알고 우리가 갈 필요가 첫 번째 장소는, 1 우리는 그렇게 할 수 있습니까? 그래 우리는 할 수있어. 경우 안전하게 존재한다. 우리는 거기에 갈 수 있습니다. 

이제, 우리가 갈 필요가 다음 장소는 6입니다. 6 경로는 여기에서 존재 하는가? 네, 그렇습니다. 우리는 6 길을 갈 수 있습니다. 그리고 우리는 여기서 끝. 

우리는 여기에서 3 길로 갈 수 있습니까? 글쎄, 그것은 밝혀, 네, 역시 존재한다. 그리고 우리는 여기에서 6 경로에받을 수 있나요? 그래 우리는 할 수있어. 

우리는 아주 대답하지 않은 아직 질문입니다. 하나는 여전히있다 지금 단계, 우리가 아래로 볼 필요가와 그 ... 사실상의 경우 참조 우리가 하버드를 찾고 있다면,이다 우리가 키를 배출 한 후 우리는 무엇을 찾아? 이 예에서 우리가 여기에서 사용하고, 년은 항상 네 자리 숫자입니다. 하지만 당신은 예를 어디에 사용 될 수 있습니다 당신은 단어의 사전을 저장한다. 

그래서 대신에 10 포인터를 갖는 내 위치, 당신은 26가있을 수 있습니다. 알파벳의 각 문자 하나. 그리고 박쥐와 같은 일부 단어가있다, 이는 예를 들어 배치의 부분 집합이다. 그리고 당신은 얻을 그래서 경우에도 키의 끝 당신은 아래로보고, 당신은 무엇을 볼 수 있습니다 당신이 찾고 있습니다. 

그래서 당신은 항상 통과해야 전체 경로 다음 당신은 성공적으로 수 있다면 전체 경로를 통과합니다, 아래로보고 한 최종 확인을한다. 그게 내가 바라는 건 무엇인가? 글쎄, 난 시작한 후 아래로 보이는 상단과 1636을 것. 나는 아래로 본다. 나는 하버드를 참조하십시오. 그래서, 그래, 나는 성공했다. 어떤 경우에는 내가 무엇을 찾고 있어요 하지만, 트라이에 있지 않습니다. 내가 프린스턴 무엇을 찾고 있어요 경우, 이는 1746 년에 설립되었다. 그리고 1746 내 키가된다 트라이을 탐색합니다. 글쎄, 난 루트에서 시작합니다. 그리고 내가 원하는 첫 번째 장소 에는 1 길을 간다. 나는 그것을 할 수 있습니까? 예, 저는 할수 있습니다. 

나는 거기에서 7 경로 아래로 갈 수 있습니까? 네, 할 수 있습니다. 즉,도 존재한다. 그러나 여기에서 4 경로 아래로 갈 수 있나요? 즉, 수, 질문처럼 나는 작은 광장 것을 아래 진행 것을 나는 노란색으로 강조했습니다? 거기에 아무것도 없습니다. 권리. 

방법 앞으로 4 경로 아래 없습니다. 프린스턴,이 트라이에 있었다 (4) 그 경우 이미 우리를 위해 삭제되었을 것입니다. 그리고이 시점에서 우리는 막 다른 골목에 도달했습니다. 우리는 더 이상 갈 수 없습니다. 그래서 우리는 아니, 확실히 말할 수 있습니다. 프린스턴이 트라이에 존재하지 않습니다. 

그래서이 모든 무엇을 의미 하는가? 권리. 여기서 살펴 봐야 할 것들이 많다. 도처에 포인터가있다. 그리고, 같이 당신은 볼 수 있습니다 다만, 다이어그램에서 노드가 많이있다 그 종류의 주위를 날고있다. 그러나 우리가 원하는 모든 시간을 알 뭔가 트라이에 있었다 여부를 확인, 우리는 단지 4 이동했습니다. 

우리가 원하는 때마다 트라이에 무언가를 삽입, 우리는 아마도 4 이동을해야 길을 따라 몇 가지 물건을 mallocing. 우리가 삽입 때 우리가 본 바와 같이 트라이에 다트머스, 때때로 경로의 일부 이미 우리를 위해 삭제 될 수 있습니다. 그래서 우리의 트라이가수록 더 크고 더 큰, 우리는 적은 작업을 할 때마다 수행해야 새로운 것을 삽입 우리는 이미했습니다 때문에 중간 많이 내장 길을 따라 가지. 우리는 지금까지보고해야하는 경우 4 일, 4 단 일정하다. 우리는 정말 가지 접근하고있다 일정 시간 삽입 그리고 일정 시간 조회. 트레이드 오프는 물론, 주도 이 트라이는,로 당신은 아마 알 수 있습니다 거대하다​​. 이러한 각 노드 하나 많은 공간을 차지한다. 

그러나 그것은 트레이드 오프입니다. 우리는 정말 빠른하려면 삽입, 정말 빠른 삭제, 정말 빠른 조회, 우리는해야 많은 양의 데이터가 주위를 비행합니다. 우리는 많은 공간을 따로 설정할 필요 그 데이터 구조에 대한 메모리 존재합니다. 

그리고 그 트레이드 오프입니다. 하지만 우리처럼 보인다 그것을 발견했을 수 있습니다. 우리는 것을 발견 할 수 데이터 구조의 성배 빠른 삽입과, 삭제, 조회. 그리고 어쩌면이 될 것입니다 적절한 데이터 구조 어떤 정보를 사용하는 우리는 가게에 시도하고있다. 내가 더그 로이드 해요,이 CS50입니다.