[음악 연주] DAVID 마란 :이 CS50입니다. 그리고 이것은 시작과 둘 다 literally-- 거의 말처럼 end-- 주 여섯. 

나는를 공유하고자합니다 재미있는 사실 조금. 나는에서이 뽑아 봤어 지난 학기의 데이터를 설정합니다. 당신은 우리가 매일에 요청할 것을 기억하고있을 것 P 세트 형태로 온라인 시청 한 경우 또는 당신은 사람에 참석 한 경우. 그리고 여기에 데이터입니다. 그래서 오늘은 매우 예측했다. 그러나 우리는 조금을 보내고 싶어 시간을 당신과 함께 그럼에도 불구하고. 사람이 왜이 추측 하시겠습니까 그래프, 위로 아래로, 위로 아래로, 그래서 톱니입니다 그래서 지속적으로? 어떤 피크의 각을 과 최저점 대표? 

청중 : [들리지] DAVID 마란 : 사실. 그리고 더 재미있게, 신 금지, 우리는 금요일에 한 강의를 개최 학기의 시작 부분에서, 그것은 우리가 일을 참조거야. 그래서 오늘, 우리는 조금에 참여 데이터 구조에 대한 자세한. 그리고 당신에게 고체의 더주고 다섯에서 문제에 대한 정신 모델, 이는 지금 밖으로이다. 맞춤법 오류 항에있어서, 우리는거야 당신에게 텍스트 파일을 손으로 10 만명 플러스 영어 단어 및 당신은 할거야 영리를로드하는 방법을 알아 내기 위해 메모리, RAM에, 일부 데이터를 사용하여 당신의 선택의 구조. 

이제 하나의 데이터 구조는 수 안 아마 수 있지만, 상당히 단순 연결리스트, 이는 우리가 지난 시간에 소개했다. 그리고 연결리스트는 적어도했다 배열을 통해 하나의 장점. 하나의 이점은 무엇입니까 틀림없이 연결리스트? 

청중 : 삽입. 

DAVID 마란 : 삽입. 당신은 무엇을 의미합니까? 

청중 : 어디에나 목록 [들림]. 

DAVID 마란 : 좋은. 그래서 당신은 요소마다 삽입 할 수 있습니다 사용자는 목록의 중간에 원하는 아무것도 셔플하지 않고, 이는 우리가 우리의 정렬에 결론 토론이 아니다 반드시 좋은 일이, 그것은 시간이 걸리기 때문에 실제로 이동 그 사람의 모든 왼쪽 또는 오른쪽으로. 그리고 연결리스트, 당신은 할 수 단지의 malloc으로 할당, 새 노드, 다음의 몇 가지를 업데이트 pointers-- 두, 세 가지 작업이 max-- 우리는 사람을 슬롯 수있어 목록에 어디에서. 

또 어떤 유익했다 링크 된 목록에 대한? 그래? 

청중 : [들리지] DAVID 마란 : 완벽한. 완벽한. 정말 동적입니다. 그리고 당신은 투입하지 않을 것을, 사전에 어떤 고정 된 크기 메모리의 덩어리처럼 당신은 것 배열, 위쪽에있는의 만에 노드를 할당 할 수있다 요구함으로써 만 많은 공간을 사용하여 당신이 실제로 필요로하는. 배열과는 달리, 당신은 수도 실수로 너무 적게 할당합니다. 그리고 그것은 단지거야 목에 통증이있을 수 있습니다 새로운 더 큰 배열을 재 할당, 복사 모든 통해, 기존의 배열을 해제 다음의 비즈니스에 대해 이동합니다. 더 나쁜, 당신은 길을 할당 할 수 있습니다 당신이 실제로 필요한 것보다 더 많은 메모리, 그래서 당신은 매우를 할 겁니다 말하자면, 배열을 드문 드문 채워진. 

그래서 링크 된 목록이 당신에게 제공 활력과 유연성의 장점 삽입과 삭제와. 그러나 확실히 지불 가격이 있어야합니다. 테마의 사실, 하나 퀴즈 제로 탐험 했다 절충의 몇 우리는 지금까지 본 적이있다. 그래서 유료 가격 또는 무엇 연결리스트의 하락? 그래. 

청중 : 없음 랜덤 액세스. 

DAVID 마란 : 아니 랜덤 액세스. 하지만 누가 무슨 상관이야? 랜덤 액세스는 강력한 소리를하지 않습니다. 

청중 : [들리지] DAVID 마란 : 정확. 당신이 갖고 싶어 특정 algorithm-- 나 실제로 제안하자 특히 이진 검색, 어떤 우리는 꽤 bit--를 사용했습니다 하나입니다 만약 랜덤 액세스가없는 경우에, 당신은 간단한 산술 연산을 수행 할 수 없습니다 중간 요소처럼 발견 그리고 바로 점프. 대신 처음에 시작해야 요소와 선형 왼쪽에서 검색 오른쪽에 당신은 발견 할 경우 중간 또는 임의의 다른 구성 요소 일 수있다. 

청중 : 그것은 아마 더 많은 메모리가 소요됩니다. 

DAVID 마란은 : 더 많은 메모리를 이동합니다. 어디 추가적인입니다 메모리에서 오는 비용? 

청중 : [들리지] DAVID 마란 : 정확. 여기서이 경우, 우리는이 있었다 정수에 대한 연결리스트, 아직 우리는 배가있어 메모리의 양 우리는 또한 이러한 포인터를 저장하여 필요합니다. 같은 큰 문제가 지금 적은 당신의 구조체이 큰 얻을 당신이하지 번호를 저장하고 있지만, 어쩌면 학생 또는 다른 객체입니다. 그러나 중요한 점은 확실히 남아있다. 그래서 다수의 동작 연결리스트에 전화를했다 N-- 선형의 큰 O했다. 삽입 또는 검색 같은 것들 또는 경우 요소의 삭제 의 맨 마지막에 할 일 이 분류 여부를 여부 목록. 

때때로 당신은 운과의 수 이러한 작업에 이렇게 하한 당신이 있다면 또한 일정 시간이 될 수 있습니다 항상 첫 번째 요소에서 찾고, 예를 들면. 그러나 궁극적으로, 우리는 약속 성배를 달성하기 위해 데이터 구조, 또는 일부 근사 그, 일정 시간의 방법으로. 우리는 요소를 찾거나 요소를 추가 할 수 있습니다 또는 목록에서 요소를 제거? 우리는 아주 빨리 볼 것이다. 그리고 그 하나를 밝혀 우리가하고있는 메커니즘 오늘 사용하기 시작하는 것, P 연간 사용, 다섯 설정 실제로 꽤 잘 알고있다. 예를 들어,이 무리이면 시험 책, 각각의 학생의 첫 번째가 거기에 이름과 성을 이름, 나는 그들을에서 픽업 시험의 끝에, 그리고 그들은 모든 꽤있어 임의의 순서로 많은, 우리는 정렬에 대해 가고 싶어 이 시험은 그래서 한 번 등급 그냥 더 쉽게 그리고 빨리 그들을 다시 손합니다 알파벳 순으로 학생. 당신의 본능은 무엇 일 것 이 같은 시험의 더미 하시나요? 

글쎄, 당신이 저 같이 인 경우에, 당신 이 m 인 것을 볼 수 있습니다, 그래서, 일종의에 이것을 넣어 갈거야 이 내 테이블 또는 내 바닥 인 경우 나는 물건을 확산하고있어 병원을 나온 또는 내 배열 정말 - 나는 거기에 미스를 모두 넣어 수 있습니다. 오. 여기 A. 그래서 나는 수도의 여기로했습니다. 오. 여기에 내가 갈거야 다른 A.이다 여기에 그것을 넣어. 다음은 Z를 여기에 또 다른 M. 그래서입니다 이 같은 더미를 만들기 시작 수 있습니다. 그리고 어쩌면 내가 나중에 갈 것 및 종류의 매우 nitpicky-LY 정렬 개별 더미. 그러나 요점은이 보일 것입니다 나는 손으로 해요 입력에서 나는 약간의 계산 만들 것 그 입력에 기초하여 결정. 그것이로 시작하면, 거기에 넣어. 이 Z로 시작하면, 그것을 통해 넣어 사이에 존재하고, 모든 것을. 

그래서이의 기술이다 일반적으로 hashing--의 H-A-S-H--로 알려진 이는 일반적으로 복용 의미 입력과 계산이 입력을 사용하여 값, 일반적으로 숫자, 그 번호는 저장에 대한 인덱스입니다 컨테이너, 배열 등을들 수있다. 그래서 다른 말로하면, 나는이있을 수 있습니다 해시 기능, 내 머리에서와 같이, 내가 누군가의 보는 경우에 그 로 시작하는 이름, 나는 그지도거야 내 머리 0으로. 나는 Z와 사람을 볼 수 있다면, 난 내 머리 (25)에 그지도 것 다음에 넣습니다 마지막으로 대부분의 더미. 

이제, 경우에 당신은 내 뇌 없습니다 생각 그러나 C 프로그램, 어떤 번호가 있었던 당신은 동일한 결과를 얻을 수에 의존? 즉, 만약 , ASCII 문자 있었다 당신은 어떻게 결정합니까 무엇 양동이에 넣어하는 방법? 당신은 아마 싶지 않아 버킷 (65)에 넣어하는 저기 같은 것 더 좋은 이유. 어디를 넣어 싶어 그 ASCII 값의 측면에서? 어디는 ASCII로 수행 할 작업 값은 스마트 버킷 가지고 올 에 넣어하는 방법? 

청중 : 마이너스 A. 

DAVID 마란 : 그래. 그래서 마이너스 마이너스 특히 65이 있다면 자본 A. 98 경우 는 소문자입니다. 그리고 그것은 매우, 우리를 할 수 있도록 할 간단하고 매우 산술적으로, 그런 통에 넣어 뭔가. 그래서 우리가 실제로 어떻게 밝혀 이뿐만 아니라 심지어 퀴즈. 

그래서 당신은 당신이 원 불러올 수도있는 커버에 교육 동료의 이름입니다. 그리고 TF의 이름이 조직되었다 알파벳이 컬럼에, 물론, 믿거 나 말거나, 때 우리 모두 80 PLUS 학년에 밤 함께있어 우리 그레이딩 공정의 마지막 단계 큰에 퀴즈를 해시하는 것입니다 [들림] 바닥의 공간 모두의 퀴즈를 배치하기 자신의 TF 년대 정확히 순서대로 표지에 이름 때문에 그것은 우리에게 많은 쉽게 그 사용하여 선형을 검색합니다 검색하거나 영리 어떤 종류의 TF는 찾기위한 자신 그녀의 학생들의 퀴즈. 

해싱의 그래서이 아이디어 당신은 볼 수 있음 매우 강력 실제로 꽤 평범하고 매우 직관적, 많은 아마도 나누어 추천하고 정복은 주 제로였다. 핵킹 마라톤에 나는 빨리 감기 몇 년 전에. 이 Zamyla과 몇했다 다른 직원 인사말 학생 그들은 들어와. 그리고 우리는 접는의 전체 무리가 있었다 이름 태그가 테이블. 그리고 우리는 이름 태그를 구성했다 와 저기로 같은 그리고 저기 ZS. 그리고 TF들 중 하나 매우 영리하게 지침으로 쓴 하루. 그리고 학기이 12 주에 모든 완벽한 이해와 모든 사람을 만든 무엇을 알고 있었다. 그러나 언제 당신은했습니다 동일한 방식으로 대기, 당신을 구현하고 해시 같은 개념. 그래서이 조금 공식화 할 수 있습니다. 다음은 배열입니다. 그것은 조금 수 그려 넓은 단지 시각적으로 묘사하기 위해, 우리는 문자열을 넣을 수 있음 이 같은 뭔가. 그리고이 배열이다 명확하게 크기 26 총. 그리고 일이 호출됩니다 테이블 임의로. 그러나 이것은 단지 작가의 연주입니다 해시 테이블이 될 일의. 

그래서 해시 테이블은 지금에 가고 더 높은 레벨 데이터 구조 일. 하루의 끝에서 우리는 당신이 볼 것을 대략 해시 테이블을 구현할 수있는 많은 체크인 라인처럼 많은 이런 핵킹 마라톤에서 표는 시험 책을 정렬에 사용. 그러나 해시 테이블이고 이러한 높은 수준의 종류 배열을 사용할 수 개념 후드가 그것을 구현하는 아래 아니면 길이리스트를 사용, 또는 심지어 수 아마도 일부 다른 데이터 구조. 그리고 지금은 theme-- 복용 이러한 기본적인 성분의 일부 배열이 건물 등 길이 목록의 현재 차단 우리가 구축 할 수있는 다른 무엇을보고 그 위에, 재료 등 조리법에 더 많은을 재미 있고 유용한 최종 결과. 

해시 테이블에 따라서 우리는 그것을 구현할 수 메모리에 그림으로이 같은,하지만 어떻게 실제로 최대 코딩 할 수 있습니까? 글쎄, 단순히 이것이다. 모두 대문자로 용량이 단지 인 경우 예 (26)에 대한 몇 가지 constant--, alphabet--의 26 글자에 대한 내 변수 테이블을 호출 할 수 있습니다, 그리고 내가 갈거야 주장 할 수 거기에, 또는 문자열에 문자 별을 넣어. 그래서 간단합니다 경우이 같이 해시 테이블을 구현하려는. 그럼에도 불구하고,이 정말 그냥 배열입니다. 그러나 다시, 해시 표는 우리가거야 지금 단지 추상적 인 데이터 타입을 호출 상단에 레이어 개념의 종류 더 평범한 무언가의 이제 배열을 좋아한다. 

이제, 우리가 어떻게 이동합니까 문제 해결에 대한? 음, 이전에 내가 사치를했다 의 여기에 충분한 테이블 공간을 가진 나는 넣을 수 있도록 퀴즈 어디서나 내가 원했다. 그래서으로는 여기 있습니다. ZS는 여기 있습니다. MS는 여기 있습니다. 그리고 나는 약간의 여분의 공간이 있었다. 그러나 이것은 속임수 권리의 비트입니다 지금이 테이블 때문에, 내가하면 정말 배열로 생각, 그냥 어떤 고정 된 크기가 될 것. 

그래서 기술적으로, 나는 당기면 다른 학생의 퀴즈까지 이 사람의, 오, 참조 이름은 너무 시작 나는 종류의 거기를 넣을. 그러나 곧 나는 경우, 거기 넣어 이 테이블은 실제로 배열을 나타냅니다, 나는 무시하거나 건드리지 될거야 누구든지이 학생의 퀴즈입니다. 오른쪽? 이러한 배열의 경우, 단 하나가 수 이러한 세포의 각 요소에 이동합니다. 그래서 나는 가지가 선택하고 선택합니다. 

이제 이전의 내가 가지 사기 및이 아니면했다 단지 종류의 적층 서로 위의 그들. 하지만 그 코드에 비행 않을거야. 그래서 어디를 넣을 수 이름이 두 번째 학생 내가 가진 모든이 경우 A는 사용 가능한 테이블 공간? 그리고 3 개의 슬롯과 ​​사용했습니다 몇 가지 다른 사람들이있는 것 같다. 당신은 무엇을 할 수 있을까? 청중 : [들리지] DAVID 마란 : 그래. 어쩌면 그냥 간단하게 할 수 있습니다. 오른쪽? 나는 그것을 넣을 곳은 적합하지 않습니다. 그래서 넣어 갈거야 기술적으로 B가 갈 것입니다 경우. 지금, 물론, 내가 시작 해요 코너에 자신을 페인트. 나는 학생에 도착하면 이름이 실제로는 B이다, 이제 B는 조금 이동 될 것입니다 앞으로, 등, 네, 일어날 수 이 B 인 경우, 지금은 여기에있다. 

그래서이 매우 빠르게 , 문제가 될 수 하지만, 기술은 실제로 야 선형 프로빙라고, 이에 방금 고려하여 배열은 라인을 따라합니다. 그리고 당신이 종류의 조사 또는 사용 가능한 각 요소를 검사 사용 가능한 자리를 찾고. 그리고 가능한 빨리 발견하면 하나는, 당신은 거기에 놓습니다. 

이제, 가격은 현재 지불되고 이 솔루션은 무엇입니까? 우리는 고정 된 크기 어레이가, 나는 이름을 삽입 할 때 그것으로, 적어도 처음, 무엇이다 삽입의 실행 시간 학생들을 '퍼팅 오른쪽 양동이에 퀴즈? 무슨 큰 O? 

청중 : N. DAVID 마란 : 나는 N의 큰 O를 들었다. 사실이 아닙니다. 그러나 우리는 떨어져 애타게 것 왜 그냥 순간에. 그것은 다른 무엇을 할 수 있는가? 

청중 : [들리지] DAVID 마란 : 그리고 저를 시각적으로 할 수 있습니다. 그래서이 편지 S.은 가정하자 

청중 : 그것은 하나입니다. DAVID 마란 : 그것은 하나입니다. 오른쪽? 이 배열 인 우리는 랜덤 액세스를 의미합니다. 그리고 우리는이 생각한다면 제로이 같은 25, 우리는 그 실현, 아, 여기 내 입력 S가이다, 나는 확실히 변환 할 수 있습니다 S, ASCII 문자, 해당 번호에 영 ~ 25 다음 바로 자신이 속한 곳을 넣습니다. 

그러나 물론, 최대한 빨리는 도착으로 이름의 두 번째 사람은 A 또는 B 또는 C이다 결국, 내가 사용했을 경우 선형, 내 솔루션으로 프로빙 의 실행 시간 최악의 경우 삽입 실제로 무엇으로 바뀔 것입니다? 그리고 난 여기가 되셨습니까 제대로 초기에. 청중 : [들리지] DAVID 마란 : 그래서 그것은 참 한번 n은 당신은 충분히 큰 데이터 세트를 가지고있다. 따라서, 한편으로, 만약 당신의 배열이 충분한 크기 당신의 데이터는 당신은 충분히 스파 스 이 아름다운 일정 시간을 얻을. 그러나 곧 시작으로 점점 더 많은 요소를 얻고, 다만 통계적으로 당신은 얻을 문자로 더 많은 사람들이 그들의 이름 또는 편지 B, 잠재적으로 수 뭔가 더 선형으로 바뀔. 그래서 아주 완벽하지. 그래서 우리는 더 잘 발음 할 수 있나요? 

그럼,이었다 우리의 솔루션 때를하기 전에 보다 더 역 동성을 갖고 싶어 배열과 같은 허용? 청중 : [들리지] DAVID 마란 : 우리는 무엇을 소개 했습니까? 그래. 그래서 연결리스트. 음,이 링크 해 보자 목록 대신 우리를 위해 할 수 있습니다. 글쎄, 내가 그 우리를 제안하자 다음과 같이 그림을 그립니다. 지금 이것은 다른 예로부터 그림 다른 텍스트에서, 실제로 그 실제로 크기 (31)의 배열을 사용한다. 그리고이 저자 단순히 문자열을 해시로 결정 그 사람의 이름을 기반으로하지, 하지만 자신의 생년월일에 따라. 에 관계없이 월, 그들은 생각 당신은 한 달의 1 일에 태어난하는 경우 또는 그 달의 31 일, 저자 그 값에 기초하여 해싱 것 비트로부터 이름을 확산 시키도록 다만 26 점을 허용하는 것보다 더. 그리고 아마도 좀 더 균일 한이다 알파벳 문자로가는 것보다, 때문에 물론 거기에 아마 이름으로 세계에 더 많은 사람들이 확실히 이상으로 그 시작 알파벳의 다른 글자. 아마이 조금이다 보다 균일 한, 가정 균일 한 분포 한 달에 걸쳐 아기의. 

그러나 물론, 이것은 여전히​​ 불완전하다. 오른쪽? 우리는 충돌을 데있어. 이에있는 여러 사람들 데이터 구조는 여전히 적어도 동일한 생년월일을 갖는 당신은 한달에 관계없이 것입니다. 그러나 저자는 무엇을했다? 우리가 배열을 가지고있는 것처럼 보이네요 수직으로 그려진 왼쪽에, 하지만 그것은 단지 작가의 연주입니다. 그것은 중요하지 않습니다 어떤 방향을 배열을 그려, 여전히 배열입니다. 이런 방식이 배열 무엇입니까? 

청중 : 링크 된 목록입니다. 

DAVID 마란 : 그래. 가있어 것 같습니다 연결리스트의 배열입니다. 그래서 다시, 종류의이 시점에 이제 이러한 데이터 구조를 이용하는 이상으로 성분으로 흥미로운 솔루션, 당신은 절대적으로 걸릴 수 있습니다 기본적인 배열과 같은, 다음 뭔가 더 걸릴 링크리스트와 같은 재미있는 심지어 더로 결합 더 흥미로운 데이터 구조. 그리고 실제로,이 너무 것 해시 테이블을 호출, 이에 배열 인 정말로 해시 테이블, 하지만 해시 테이블에는 체인은, 그래서, 말하자면 그 성장하거나에 따라 수축 요소의 수는 당신이 삽입 할. 

이제, 따라서, 무엇이다 지금 시간을 실행? 나는 누군가를 삽입 할 경우 10월 31일 누구의 생일이다, 어디 그 또는 그녀는 가는가? 좋아. 이 31라는 매우 하단에서. 그리고 완벽 해. 즉 일정 시간이었다. 그러나 우리는 다른 사람을 찾을 경우 누구의 생일, 보자되어, 10 월, 11 년 12 월 31 일? 어디 그 또는 그녀는 갈거야? 같은 일. 하지만 두 단계. 즉, 비록 일정하지 않습니다? 좋아. 순간 그 것이다. 그러나, 일반적인 경우에, 우리가 추가 더 많은 사람들, 확률 적으로, 우리는거야 더 많은 충돌을 얻을 수 있습니다. 

지금 이것은 조금이다 더 나은 기술적 때문에 지금 내 체인에있을 수 최악의 경우 얼마나 오래? 나는이 더에 N 사람을 삽입하는 경우 복잡한 데이터 구조, N 사람, 최악의 경우는 N 될 것. 왜? 

청중 : 때문에 경우 모두 같은 생일을 가지고, 그들은 한 줄이 될 것입니다. DAVID 마란 : 완벽한. 그것은, 약간의 인위적인 수 있습니다 그러나 진정 최악의 경우, 모두가 같은 생일이있는 경우, 당신이 가지고있는 입력 주어, 당신은이 겁니다 대규모 긴 체인. 그래서, 당신은 그것을 호출 할 수 있습니다 테이블을 해시,하지만 정말입니다 그냥 대규모 연결리스트 낭비되는 공간의 전체를 많이. 그러나 일반적으로, 우리가 가정하는 경우 적어도 생일 uniform-- 있습니다 그리고 그것은 그렇지 않다. 나는 그를 만들고있어. 그러나 우리는 가정하면, 대한 토론을 위해 그들은 다음 이론, 경우 있음 이 수직 표현 배열의 잘 잘하면 당신이있어 , 당신이 알고 사슬을 얻을 것, 거의 같은 길이 어디에 각 이 달의 날을 나타냅니다. 

달에 삼십일일이 있다면 지금, 정말 내 실행 시간을 의미 (31)를 통해 N의 큰 O는, 인 선형보다 더 느낀다. 그러나 한 것이었다 우리 약속 몇 주 전은 표현에 와서 때마다 알고리즘의 실행 시간은? 그냥 만 높은 순서 기간을 확인합니다. 오른쪽? 31 확실히 도움이됩니다. 그러나 이것은 여전히​​ N의 큰 O입니다. 그러나 테마 중 하나 의 문제는 다섯 설정 로 될 것입니다 절대적으로 그 인정, 점근 적, 이론적으로 데이터 구조 단지보다 낫다 하나의 거대한 연결리스트. 그리고 실제로, 최악의 경우,이 해시 테이블은으로 바뀔 수 있습니다. 

그러나 현실 세계에서 우리와 함께 인간 자신의 맥 또는 PC 나 어떤 그 그리고 현실 세계를 실행하는 실제 데이터의 소프트웨어, 어떤 알고리즘 당신이 선호하는 건가요? 최종 단계 또는 소요 하나 N 31 단계로 나누어 소요 하나 데이터의 일부 조각을 찾거나 몇 가지 정보를 찾기 위해? 나는 절대적으로 31 차종을 의미 현실 세계에서의 차이. 그것은 31 배 빠른 속도입니다. 그리고 우리 인간은 확실히 있습니다 그 감사 것. 

그래서 이분법을 실현 이 실제로 사이 이론적으로 것들에 대해 이야기 확실히 및 점근하는 우리가 보았 듯이 값을 가지고, 그러나 현실 세계에서, 당신은 단지을 걱정하는 경우 일반 입력에 대한 인간의 행복, 당신은 매우 잘 읽고 동의를 할 수 있습니다 예,이 선형, 사실, 하지만 31 배 빠른 속도이다 보다 선형이 될 수 있습니다. 그리고 더 나은 아직, 우리는 필요가 없습니다 생년월일 같은 임의의 일을, 우리는 조금 보낼 수 더 많은 시간과 영리함 우리가 할 수있는 일에 대해 생각, 주어진 사람의 이름과 아마 자신의 생년월일은 사람들을 결합 성분은 무엇인가를 알아 내기 위해 즉 진정으로 더 균일하고 적은 톱니, 그래서이 그림보다 이야기하기 현재이 될 수 있습니다 제안합니다. 우리는 어떻게 코드에서이를 구현할 수있다? 글쎄, 내가 그 우리를 제안하자 우리가했습니다 몇 가지 구문을 빌려 지금까지 몇 번을 사용했다. 그리고 내가 정의하는거야 노드, 이는 다시 단지 일부에 대한 일반적인 용어이다 일부 데이터 구조에 대한 컨테이​​너입니다. 나는 그 제안거야 문자열은 거기에 것입니다. 그러나 우리는 복용 시작하는거야 지금 떨어져 바퀴를 훈련하는. 

더 이상 CS50 라이브러리 없다 정말, 당신이 원하는하지 않는 한 최종을 위해 사용하는 괜찮 프로젝트, 그러나 지금 우리는 철수거야 커튼과 그냥 문자 스타 말할. 단어 그래서이 될 것입니다 본인의 이름. 그리고 지금은 링크가 여기에서 다음 노드로 이 대표 있도록 각 노드 체인, 잠재적 연결리스트의. 

그리고 지금은 어떻게 선언 할 해시 테이블 자체? 어떻게하면이 전체 구조를 선언합니까? 음, 정말, 많이 나는 포인터를 사용처럼 목록의 바로 첫 번째 요소 전에, 마찬가지로 난 그냥 말할 수 난 그냥 포인터의 무리가 필요 이 모든 해시 테이블을 구현합니다. 나는 배열을거야 해시 테이블이라는 테이블. 그것은 크기의 용량이 될 것. 즉,에 들어갈 수있는 방법을 많은 요소입니다. 그리고이에 그 각 요소 배열은 노드 스타가 될 것입니다. 왜? 음,이 그림 당, 내가 뭘 해요 해시 테이블로서 구현 효과적으로에 시작은 그냥 우리가 수직으로 그려 한이 배열, 그 사각형의 각 포인터를 나타냅니다. 사람은 슬래시를 가지고 있고, 그들을 통해 단지 null입니다. 그리고 사람은 그이 오른쪽에가는 화살표 실제 노드 실제 포인터이고, 연결리스트의 시작을 ERGO. 

그래서 여기, 다음, 우리가 어떻게 힘이다 해시 테이블을 구현하는 별도의 체인을 구현한다. 이제 우리는 더 잘 할 수 있습니까? 좋아 나는 지난 시간에 약속이 우리는 일정 시간을 달성 할 수있다. 그리고 나는 종류의 준 여기에 일정 시간, 하지만 정말로 말했다 일정 시간이 여전히 있기 때문에 총에 의존 요소 수 당신은에 입력하고 데이터 구조. 그러나 우리는 이런 짓을 가정합니다. 내가 여기에 화면으로 돌아 가자. 나 또한 여기를 프로젝트 명확한하자 화면이, 내가 이런 짓을 가정합니다. 내가 이름을 삽입하고 싶어한다고 가정 데 이븐 내 데이터 구조에. 

그래서 문자열을 삽입 할 데이터 구조로 데 이븐. 내가 사용하지 않는 경우 테이블을 해시,하지만 난 사용 더 뭔가 나무와 같은 가족 나무처럼 당신은에 어떤 루트를 상단과 다음 노드와 잎 그 아래쪽과 바깥쪽으로 이동합니다. , 그 I를 가정 데 이븐의를 삽입 할 현재 빈리스트 무엇으로. 나는 다음과 같은 작업을 수행 할거야 : 난 이 가족의 노드를 만들 것 나무와 같은 데이터 구조 보인다 조금이 같은, 각각의 사각형은,,의 말을 할 수있다 그것은 지금 26 요소. 그리고 각 셀 이 배열 것입니다 알파벳의 문자를 나타냅니다. 

특히, 나는 치료하는거야 이것은, 다음, B, C 다음, 다음 D이다 여기 하나. 그래서이 효과적으로 것입니다 문자 디를 나타냅니다 그러나 데 이븐의 모든 삽입 내가 좀 더해야 할 이름을 지정합니다. 그래서 내가 먼저 말하자면, 해시에 갈거야. 나는 첫 번째 문자를보고 갈거야 의 데 이븐의 분명 D 인 나는 할당 할거야 보이는 노드 같은 큰 큰 사각형을 두도록 전체 알파벳 맞게 충분히. 

이제 D가 이루어집니다. 이제 A. D-A-V-E-N이 목표입니다. 그래서 지금 내가 할거야 무슨이이다. 최대한 빨리 D 통지를 시작으로 거기에는 포인터가 없습니다. 그것은 순간에 쓰레기 값을의 아니면 null로 초기화 할 수 있습니다. 그러나 저와 계속하자 나무를 구축하는이 아이디어. 날이 또 다른 하나를 할당하자 그것은 26 요소가 노드. 

그리고 당신이 뭘 알아? 이 메모리에 단지 노드 인 경우 그 나는 구조체를 사용하여, malloc을 사용하여 만든 우리는 곧 살펴 보 겠지만, 나는 이런것을 할거야 나는에서 화살표를 그릴거야 아래 D를 나타내는 것 이 새로운 노드. 그리고, 제 다음 지금 데 이븐의 이름으로 편지, V-- D-A-V-- 나는 앞서 갈거야 이 같은 다른 노드를 그릴, 이에, 여기에 V 요소, 어떤 우리는 instance-- 으악 그려 주께. 우리가 그리하지 않습니다. 여기 갈 것입니다. 

그럼 우리가가는거야 이 V.이라고 생각 그리고 여기있는 우리는 색인에 갈거야 아래 V에서 우리가 E. 고려해 볼게 무엇에 그리고 여기에서 우리는에 갈거야 여기에 이​​러한 노드 중 하나가 이동합니다. 그리고 지금 우리는 대답 할 수있는 질문이 있습니다. 나는 것을 나타냅니다 어떻게 든 필요 우리는 문자열 데 이븐의 끝에있어. 그래서 난 그냥 널 떠날 수 있습니다. 

그러나 우리는 데 이븐의 무엇이있는 경우 또한 전체 이름, 어떤 우리가, 데븐 포트 말했듯이, 무엇입니까? 그래서 데 이븐은 무엇입니까 실제로 문자열, 더 이상 문자열의 접두사? 우리는 영구적으로 할 수 없습니다 아무것도 진행하지 말 때문에 우리가 할 수, 거기에 가고 데븐 포트와 같은 단어를 삽입하지 마십시오 이 데이터 구조에 

그래서 우리는 무엇을 할 수 있는지 대신하다 이들 요소의 각각을 치료 같은 어쩌면 두 가지는 그들 내부의 요소. 하나는, 참으로, 포인터 나는이 일을했습니다. 이 상자의 각 그래서 하나의 세포가 아닙니다. 그러나 경우 최고 보이면 아래 하나의 때문에, 널 (null)이 될 것 아직 더 대븐 포트가 없습니다. 어떤 경우 상단 하나 특별한 가치인가? 그리고 그것은 조금 될 것 그것은이 크기 그릴 하드. 하지만 그냥 체크 마크의 가정. 확인합니다. D-A-V-E-N은 문자열입니다 이 데이터 구조. 

한편, 경우에 나는 더 많은 공간이 있었다 여기에, 나는, P-O-R-T를 할 수 나는 노드에 체크를 넣을 수 즉, 맨 마지막에 편지 T가 있습니다. 그래서이 대규모입니다 복잡한 수준의 데이터 구조를. 그리고 내 필기 확실히 도움이되지 않습니다. 하지만 뭔가를 삽입하기를 원한다면 또, 우리가 무엇을 할 것이라고 생각. 우리가 다윗을 넣어 원하는 경우, 우리는 같은 논리, D-A-V를 따라 줄 하지만 지금은 다음에 가리키는 것 요소하지 E에서,하지만 난에서 D.에 그래서이있을거야 이 나무에서 더 많은 노드. 우리는 더 많은 통화의 malloc이 될 것입니다. 하지만 난을 만들고 싶어하지 않는다 이 그림의 완전 엉망. 그래서 대신 하나를 살펴 보자 그는 미리 책정 된 것 점없는이 같은 점, 점,하지만 줄여서 배열. 그러나 각 노드 여기이 나무 위로의 같은 건 말인데 ...을 나타냅니다 배열 크기 (26)의 레이. 

아니면 우리가 수 있도록하려면 정말 적절한 지금, 무엇을 다른 사람의 이름과 같은 경우 아포스트로피는의를하자 각 노드가 실제로 있다고 가정 그것은 27 인덱스, 단지 26 등을들 수있다. 그래서 지금은 데이터가 될 것입니다 구조는 trie-- T-R-I-E라고합니다. 아마 인 트라이, 나무에 대한 역사적 영리한 이름 그은을 위해 최적화 된 검색, 이는 물론, 이 트라이 그래서 I-E 철자된다. 그러나 그것은 트라이의 역사입니다. 

그래서 트라이이 나무와 같은 데이터는 가족 나무와 같은 구조 즉 궁극적으로 그런 동작합니다. 그리고 여기의 또 다른 예이다 다른 사람의 이름의 전체 무리. 하지만 지금 질문 손에있는 것입니다 우리는 틀림없이 더 도입하여 얻은 복잡한 데이터 구조, 및 한 솔직히, 그 많은 메모리를 사용합니다. 

, 비록 때문에 순간, 난 단지 해요 D의 포인터를 사용하여 V와 ES 및, NS 및 나는 메모리 많아서을 낭비하고 있습니다. 하지만 하나의 자원을 소비하는 경우, 난 다시 서로를 얻는가하는 경향이있다. 나는 더 많은 공간을 소비하고있어 경우에 따라서 아마 희망이 무엇입니까? 나는 무엇을 덜 지출이야? 청중 : 적은 시간. DAVID 마란 : 시간. 이제 그 이유가 될 수 있을까요? 음, 삽입은 무엇인가 시간, 지금 큰 O의 관점에서, 데 이븐 같은 이름의 또는 데븐 포트 또는 데이비드? 음, 데 이븐은 다섯 단계이었다. 데븐 포트는 아홉 단계가 될 것입니다, 그래서 몇 가지 단계가 될 것입니다. 다윗은뿐만 아니라 다섯 단계가 될 것입니다. 그래서 사람들은 콘크리트입니다 번호, 그러나 확실하게있다 에 상한 다른 사람의 이름의 길이. 그리고 사실,이 문제에 다섯 사양의 세트, 우리가 제안하는거야 그것은 뭔가 그 즉 40 일부-이상한 문자입니다. 

현실적으로, 아무도 없습니다 무한히 긴 이름, 말을하는 것입니다 것을의 길이 이름이나 문자열의 길이 우리는 수도 국가의 특정이 구조는 틀림없이 무엇인가? 그것은 상수입니다. 오른쪽? 이 같은 큰 상수 수 있습니다 40 일이 있지만, 일정하다. 그리고 얼마나 많은에 대한 종속성이 없습니다 다른 이름은이 데이터 구조에 있습니다. 즉, 만약 I 지금 삽입하고 싶어 콜튼 또는 가브리엘 또는 롭 또는 Zamyla 또는 앨리슨 또는 벨린다 또는 다른 이름 이 데이터로 직원 구조는 실행 시간 다른 이름을 삽입 모든 영향에 될 것 얼마나 많은 다른 요소가 있습니다 이미 데이터 구조? 그것은 아니다. 오른쪽? 우리가 효율적으로 사용하기 때문에 이 다층 해시 테이블. 그리고의 실행 시간 이러한 작업의 의 수에 의존하지 않는 것입니다 데이터 구조적인 요소 또는 결국 가고있다 데이터 구조하기 위해, 하지만 구체적으로 어떤 길이에? 

되는 문자열 삽입 만들 않는 이 점근 일정 하나의 외엔 큰 O. 그리고 솔직히, 그냥 실제,이 데 이븐의 이름이 걸립니다 삽입 의미 다섯 단계, 또는 데이븐포트 - 9 단계, 또는 데이비드 다섯 단계. 즉 무척 작은 실행 시간입니다. 그리고, 사실, 그건 매우있어 좋은 일이, 특히 이 총에 의존 아니다 이 요소의 수. 그래서 우리는 이것을 구현하는 방법 코드의 구조를 가지? 그것은 좀 더있어 복잡한, 그러나 아직도이다 단지 응용 프로그램 기본 빌딩 블록입니다. 나는 다시 정의 할거야 우리 노드 다음과 같이 부울 word--라는이를 아무것도라고 할 수있다. 그러나 부울 나타냅니다 내가 체크 표시로 그렸습니다. 예. 이 문자열의 끝 이 데이터 구조. 

그리고, 물론, 노드 별 아이들에게이 참조된다. 그리고, 참으로, 단지 좋아 가계도, 당신 노드를 고려할 것 이 걸려있다 일부 부모의 아래쪽의 요소는 아이들합니다. 그래서 아이들이 가고있다 (27)의 배열, 27 일 하나 단지 아포​​스트로피하기위한 것이다. 우리는 정렬 할거야 특별한 경우 그. 그래서 당신은 어떤을 가질 수 있습니다 아포스트로피 이름. 어쩌면 하이픈해야 거기에 가서,하지만 당신은거야 P 세트 (5) 우리는주의에서 볼 문자와 아포스트로피에 대한. 

그리고 당신은 어떻게 표현 할 데이터 구조 자체? 어떻게 루트를 표시합니까 이 트라이의, 말하자면? 글쎄, 당신은, 연결리스트와 같은 첫 번째 요소에 대한 포인터가 필요합니다. 트라이하면 하나의 필요 이 트라이의 루트 포인터. 그리고 거기에서 당신은 해시 수 있습니다 길 아래로 점점 더 깊이 구조에서 다른 모든 노드. 그래서 단순히이 수와 우리는 그 구조체를 나타냅니다. 

이제, 오 질문을 Meanwhile--. 

청중 : 부울 단어가 무엇입니까? 

DAVID 마란은 Bool로 단어입니다 그냥이 C 화신 제가 설명 무엇을 여기에, 때이 상자에 I는 각 분할 시작한 두 조각으로 배열의 요소. 하나는 다음 노드에 대한 포인터이다. 다른 하나는 있어야한다 체크 박스 같은 거기에 '좋아요'라고 말하고 여기서 끝 데 이븐 단어, 우리가 원하는하지 않기 때문에 순간, 데이브. 

데이브을 될 것입니다 비록 합법적 인 단어, 그는 트라이에없는 아직. 그리고 D는 단어가 아닙니다. 그리고 D-A는 단어 나 이름이 아닙니다. 체크 표시 그래서 만 번을 나타냅니다 이 노드 인 히트 문자의 이전 경로 당신이 삽입 한 사실 문자열입니다. 그래서 모든 부울이다 우리가하고있다. 

시도에 다른 질문? 그래. 

청중 : 중첩은 무엇입니까? 당신이 데이브와 데 이븐이 있다면? DAVID 마란 : 완벽한. 당신이 데이브와 데 이븐이 있다면? 우리가 삽입한다면, 별명 말 의원님 Dave-- D-A-V-E 하시나요? 이것은 실제로 매우 간단합니다. 그래서 우리는 네 가지 조치를 취할 것입니다. D-A-V-E. 그리고 난에 무엇을해야합니까 내가 그 제 4 노드에 충돌하면 어떻게? 그냥 확인하는 것. 우리는 이미 갈 수 있어요. 완료. 네 단계. 점근 적으로 일정 시간. 그리고 지금 우리는 모두 데이브 표시했습니다 그리고 데 이븐은 구조 문자열입니다. 그래서 문제가되지 않는다. 그리고 어떻게 존재를 알 데 이븐의 그것을하지 않았다 더 이상 시간 미만을 시간 데이브 및 그 반대의 경우도 마찬가지입니다. 

그래서 우리는 지금 다른 무엇을 할 수 있습니까? 우리는 전에이 은유를 사용했습니다 트레이의 무언가를 나타내는. 그러나 그것은 밝혀 트레이의 스택은 실제로 다른 추상 데이터의 실증 높은 레벨의 데이터 구조 유형 선택 마지막에 날 그냥입니다 배열이나 연결리스트 같은 현세 또는 뭔가. 그러나 더 흥미있어 개념, 개념. 이와 같은 스택, 메이 여기에 트레이, 일반적으로 호출 다만 스택을 ... 그 얘기. 

그리고, 데이터 구조의이 유형의 두 operations--이 당신은 하나라는 푸시에 대한이 스택에 뭔가를 추가, 다른 용지함을 씌우고 스택의 상단에 백업합니다. 당신을 의미하는 그리고 팝 맨 위의 트레이 이륙. 그러나 스택이 있다는 것입니다에 대한 주요 무엇 그것은이 호기심 특성을 가지고있다. 식당 직원과 같습니다 다음 식사 트레이를 정리, 무슨 일이있을거야 어떻게 학생들에 대한 진실 데이터 구조와 상호 작용? 청중 : 그들은 하나 오프 팝업 것입니다. DAVID 마란 : 그들은 갈거야 하나 떨어져, 희망 상단 팝업. 그렇지 않으면 그것은 단지 종류의 바보 바닥에 모든 방법을 이동합니다. 오른쪽? 데이터 구조는 실제로 허용하지 않는다 적어도 하단 트레이를 잡아합니다 쉽게. 그래서이 호기심있다 스택에 등록 마지막 항목은 그 첫 번째 아웃 될 것이다. 그리고 컴퓨터 과학자들은 전화 이 먼저 아웃 지속 LIFO--. 그리고 실제 존재하는 흥미로운 응용 프로그램. 그것은 반드시 어떤만큼 명백하지 않다면, 다른하지만​​, 실제로, 유용 그리고, 실제로 구현 될 수있다 다른 몇 가지 방법. 

그래서 하나, 실제로,하자 나는에 뛰어하지. 의 대신이 작업을 수행 할 수 있습니다. 의 거의이야, 하나 살펴 보자 동일한 아이디어는 있지만 좀 더 공정이다. 오른쪽? 이러한 팬 소년의 하나라면 또는 정말 애플 제품을 좋아하는 여자 당신은 오전 3시 일어났다 일부 가게에서 줄을 최신 아이폰을 얻으려면, 이처럼 대기했을 수 있습니다. 

이제 큐는 매우 의도적으로 지정됩니다. 이 때문에이 라인의 그것은 몇 가지 공정성. 오른쪽? 만약 여러분의 경우는 가지 빨려 것 애플 스토어에 처음 도착했을 하지만 당신은 효과적으로 맨 아래에 있습니다 트레이 후 애플 직원 때문에 마지막 사람을 팝업 사람 실제로 라인에있어. 스택과 큐, 비록 그래서 기능적으로 그들은 same-- 가지있어 그냥이 컬렉션의 자원 그건 이 것 shrink-- 성장에 가서 그것은이 공정성 측면, 현실 세계에서 적어도, 여기서 작업은 당신이 운동 근본적으로 다르​​다. 큐 stack-- rather-- 가지고 있다고 두 가지 작업 : N 큐와 D 큐. 또는 당신이 그들을 호출 할 수 있습니다 일의 수. 그러나 당신은 캡처 할 하나를 추가한다는 개념 하나는 궁극적으로 차감됩니다. 

지금은 후드 아래, 두 스택 그리고 큐는 어떻게 구현 될 수 있을까? 우리의 코드로 가지 않을 것이다 그 때문에 높은 레벨 아이디어는 일종의 더 분명하다. 내 말은, 인간은 무엇을해야합니까? 나는 애플의 첫 번째 사람이야 경우 저장하고이 정문이다, 내가 여기 서거야, 알아. 그리고 다음 사람의 여기 서서 것. 그리고 다음 사람의 여기 서서 것. 그래서 데이터 구조 그 자체가 큐에 빌려 준다? 

청중 : 큐. DAVID 마란 : 음, 큐. 물론. 그 밖의 무엇? 

청중 : 연결리스트. 

DAVID 마란 : 링크 당신이 구현할 수있는 목록입니다. 그리고 연결리스트는 때문에 좋은 반대로 그것은 긴 임의 성장할 수 어떤 고정 된 수를 갖는 것 상점에있는 사람들의. 하지만 어쩌면 고정 된 수의 장소의 합법적이다. 그들은 20처럼이있는 경우 때문에 어쩌면, 첫날 아이폰 그들은 단지 크기의 어레이를 필요 (20)는 그 큐를 대표 할 우리가 이야기를 시작하면 지금은 말을하는 것입니다 이러한 높은 수준의 문제에 대한, 당신은 그것을 구현할 수 있습니다 임의의 수의 방법. 그리고 아마 가고있다 공간과 시간에서 무역을 할 수 또는 당신의 자신의 코드 복잡성. 

스택은 어떻습니까? 음, 스택, 우리는 너무 본 적이 다만이 트레이 수 있습니다. 그리고 당신은이 배열을 구현할 수 있습니다. 그러나 어떤 시점에서 당신은 배열을 사용하는 경우 무엇 트레이에 일어날 당신은 내려 놓으려고? 좋아. 당신은에 갈거야 그래서 높은 갈 수. 그리고 나는 그들이있어 메이 생각 실제로 개방에 함몰. 그래서 실제로, 거의이다 메이가 사용하는 같은 고정 크기의 배열 만 할 수 있기 때문에 에서 그 열기에 너무 많은 트레이에 맞게 사람의 무릎 아래 아래로 벽. 그리고 그 수 있습니다 배열이라고, 그러나 우리는 확실히 구현할 수 더 일반적으로 링크 된 목록. 

그럼, 다른 데이터 구조에 대한? 내가 여기에 시각적 다른 하나를 올려 보자. 어떻게 여기 하나에 대해 같은 뭔가? 왜하지 않은 것이 유용 할 수도 있습니다 트라이만큼 멋진 뭔가하는 우리는 이러한 매우 넓은 노드보고 ... 이들은 각각 배열인가? 그러나 우리는 뭔가 더 많은 일을 할 경우 단순히 오래된 학교 가족 나무처럼, 누구 여기에 각 노드 단지 수를 저장한다. 대신 이름 또는 자손의 다만이 같은 번호를 저장한다. 

음, 전문 용어는 우리가에 사용 데이터 구조는 모두 시도이고 나무, 트라이는 다시, 어디 단지 그 노드 배열은 하나, 아직도 당신은 무엇을 수도 초등학교에서 사용 당신은 가족을 만들 때 tree-- 잎과 뿌리 나무와 아이들의 부모와 그 형제 자매. 그리고 우리는 나무를 구현할 수, 예를 들어, 단순히이있다. 나무, 그 경우 노드의 하나로서 번호가 이러한 원, 그것은이 없을거야 하나의 포인터 만 두. 그리고 곧 추가로 두 번째 포인터, 당신 실제로 정렬 할 수 있습니다 이차원 데이터 메모리의 구조. 두 차원과 마찬가지로 배열, 당신은 할 수 두 차원의 종류가 연결리스트하지만 사람 그 패턴을 따라 위치에 상관주기를가 없습니다. 그것은 하나의 진정으로 나무의 여기에 다음 조부모 길 일부 부모와 자녀와 손자와 증손자. 등. 

그러나, 너무이 정말 깔끔한 무엇 단지 코드의 비트와 함께 당신을 괴롭혀, 에서 리콜 재귀 잠시 뒤로, 이에 당신은 자신을 호출하는 함수를 작성합니다. 이 아름다운 기회 어떤 구현 재귀처럼, 때문에이를 고려한다. 

이 나무입니다. 그리고 방법에 약간의 항문 봤는데 나는 거리에 정수를 넣어. 그래야 많이 특수가 이진 검색 트리를 이름 -. 이제 우리는 바이너리 들었어요 당신을 검색 할 수 있지만, 이 물건의 이름에서 거꾸로? 나는 방법의 패턴은 무엇입니까 이 나무에 정수를 삽입? 그것은 임의 아니다. 몇 가지 패턴이있다. 그래. 

청중 : 왼쪽에있는 작은 것들. 

DAVID 마란 : 그래. 작은 사람은 왼쪽에 있습니다. 더 큰 사람은 오른쪽에 있습니다. 이러한 사실 문이있는 부모, 좌측 자식보다 큰 오른쪽 아이보다 미만. 그리고 혼자 심지어입니다 재귀 언어 적 정의 당신은 적용 할 수 있기 때문에 모든 노드에 같은 논리 그리고 단지 바닥 아웃, 기본 케이스 괜찮다면 의지 할 때 중 하나를 명중 잎은, 그래서, 말하자면 휴가는 더 아이가없는 곳. 

이제 당신은 어떻게 수 (44)를 찾을 수 있습니까? 당신은, 흠 루트에 시작하고 말할 것입니다. 55 그래서 내가 가고 싶어 (44) 아니다 오른쪽 또는 내가 왼쪽으로 가고 싶어? 글쎄, 확실히 당신은 왼쪽으로 가고 싶어. 그래서 그냥 전화처럼 이진 검색에서 책의 예 더 일반적으로. 그러나 우리는 그것을 구현하고 이제 좀 더 동적 어레이가 허용 할 수보다도. 그리고 사실, 당신이보고 싶은 경우 코드에서 먼저 눈에 확인합니다. 이 라인의 전체 무리처럼 보인다. 그러나 그것은 아름답게 간단합니다. 당신은 기능을 구현하려면 그 목적은 인생에서라는 검색 값을 검색하는 것입니다 같은 n은 정수, 당신은 하나 pointer--에 전달하고 뿌리의 노드에 대한 포인터, 오히려, 그 나무의 어떤에서 당신은, 다른 모든 것들에 액세스 할 수 있습니다 어떻게 똑 바르게 알 당신은 논리를 구현할 수 있습니다. 나무가 null의 경우는, 분명히이 아니다. 그냥 false를 돌려 보자. 오른쪽? 당신은 그에게 아무 것도 손없는 경우, 거기에 아무것도 없다. 

n은 그렇지 미만이면 지금 N 화살표 N-- 나무 화살표, 우리가 슈퍼를 도입 리콜 잠시 다른 일, 그것은 바로 드 참조를 의미 포인터와 N이라는 필드를 확인합니다. 그래서 가서 의미 N이라는 필드를 확인합니다. 그래서 N 경우, 당신이 제공하고있는 값이 작 나무의 정수 값보다, 어디 가고 싶어? 왼쪽으로. 

그래서 재귀를 알 수 있습니다. 난 안 사실 returning--하고 있습니다. 거짓되지 않습니다. 내가 어떤 대답을 반환 해요 자신에 대한 호출에서이다, 통과 중복 다시 N, 하지만 지금은 약간의 차이는 무엇입니까? 어떻게 작은 문제를하고 있죠? 나는 두 번째로 통과 해요 인수, 트리의 루트가 아닌, 그러나이 경우에는 좌측 아이. 그래서 왼쪽 자식을 전달하고 있습니다. 

한편, n은보다 큰이면 나는 현재 찾고 있어요 노드, 나는 오른쪽을 검색 할 수 있습니다. 그렇지, 나무, null가 아닌 경우 요소는 왼쪽이 아니라면 그리고, 오른쪽 아니다 경우 멋지고 무엇인가? 우리는 실제로에서 노드를 발견했습니다 질문은, 그래서 우리는 true를 돌려줍니다. 

그래서 우리는 단지 표면을 다루었 이제 이러한 데이터 구조의 일부. 문제는 다섯 설정에서 당신은거야 또 다른이를 탐험, 당신은 당신의 디자인이 제공됩니다 이것에 대해 이동하는 방법을 선택. 나는에 체결하고 싶습니다 무엇 단지 30 초 티저입니다 넘어 다음 주에 기다리고 무엇. 

우리는 다행히 begin--로서 당신은 수도 천천히 우리의 전환을 생각 엔 ... C와 하부의 세계에서 레벨 구현 세부 사항 세계에있는 우리가 걸릴 수 있습니다 다른 사람이 마지막으로 가지고 부여 이러한 데이터를 구현 우리를 위해 구조, 그리고 우리는을 이해하기 시작합니다 현실 세계가 구현 수단 웹 기반 프로그램과 웹 사이트보다 일반적으로 또한 매우 보안 우리 만했습니다 의미 의 표면에 흠집을하기 시작. 여기에서 우리를 기다리고 무엇인가 시대에 와서. 

[동영상 재생] 

- 그는, 메시지와 함께 모든 자신의 프로토콜. 그는 잔인의 세계에 온 방화벽, 무관 심한 라우터, 및 위험 죽음보다 훨씬 더. 그는 빠르다. 그는 강한. 그는 TCP / IP, 그리고 그는 당신의 주소를 가지고있다. "인터넷의 전사." [END 동영상 재생] DAVID 마란 : 다음 주에 간다. 우리는 당신이 다음 볼 수 있습니다. [동영상 재생] - 그리고 지금, "깊은 생각" 데 이븐 판햄로. 데이비드는 항상 시작 와 강의 "좋아요." 왜, "여기에 솔루션입니다 이번 주 문제 세트 "에 또는 "우리는 여러분 모두를주는거야?" [하하] [END 동영상 재생]