>> 케빈 슈 미드 : 때때로 구축 할 때 이 프로그램은, 당신은 사용 할 수 있습니다
사전으로 알려진 데이터 구조.
있습니다 사전지도 키, 일반적으로 문자열 값, 정수,
문자, 일부 개체에 대한 포인터, 우리는 원하는대로.
그냥 일반 사전처럼 정의를 통해 그지도는 말.
>> 사전은 우리에게 제공 정보를 저장하는 능력
뭔가와 관련된 나중에 그것을보고.
어떻게 우리가 실제로 어떻게 구현합니까 C 코드, 말, 사전에 우리가 할 수있는
우리의 프로그램 중 하나에서 사용할 수 있습니까?
음, 많은 방법이 있습니다 그 우리는 사전을 구현할 수 있습니다.
>> 하나, 우리는 배열을 사용할 수 있습니다 우리 동적으로 다시 크기 또는 우리가 사용할 수
연결리스트, 해쉬 테이블 또는 이진 트리.
하지만 우리가 무엇을 선택, 우리가해야 효율성을 염두하고
구현의 성능을 제공합니다.
우리는 사용 된 알고리즘에 대해 생각해야 삽입에 항목을 찾으려면
우리의 데이터 구조입니다.
>> 지금, 이제 우리를 가정 해 보자 문자열을 키로 사용합니다.
의 하나의 가능성에 대해 얘기하자, 데이터 구조는 트라이 불렀다.
그래서 여기에 시각적 표현이다 트라이의.
>> 사진은 트라이에게 알 수 있듯이 와 트리 데이터 구조
노드는 서로 연결.
우리는 뿌리가 분명히 있다는 것을 참조 몇 가지 링크가 확장과 노드
다른 노드.
그러나 각 노드에 대해 어떻게 구성되어 있습니까?
우리는 우리가 키를 저장한다고 가정하면 영문자와 함께
우리는 자본에 대해 걱정하지 않는다, 여기 노드의 정의의 그
충분합니다.
>> 유형이 객체는 구조체입니다 노드는 두 부분으로 구성되어 있습니다
데이터와 아이들을했다.
우리는 주석으로 데이터 부분을 남겨 두었습니다 구성 요소에 의해 대체 될 수 있습니다
구조체 노드 인 선언 C 프로그램에 포함.
노드의 데이터 부분이 될 수도 나타내는 부울 값 여부
하지 노드는 완료를 의미 사전 키 또는이 될 수 있습니다
정의를 나타내는 문자열 사전에있는 단어.
>> 우리는 나타 내기 위해 웃는 얼굴을 사용합니다 데이터 노드에 존재하는 경우.
26 요소가 우리의 어린이 배열, 하나의 인덱스
알파벳 문자 당.
우리는 의미를 볼 수 있습니다 곧이의.
>> 의 루트 노드의 면밀한 관찰을하자 우리의 그림에서, 이는 데이터가 없습니다
로 나타낸 바와 같이, 그것과 관련된 에서 웃는 얼굴의 부재
데이터 부분.
의 부분으로부터 연장되는 화살표 어린이 배열이 아닌 노드를 나타냅니다
다른 노드에 대한 포인터.
예를 들어, 화살표부터 연장 아이들의 두 번째 요소
문자 B를 나타냅니다 사전의 키.
그리고 큰 그림에서 우리는 B를 레이블을
>> 더 큰 그림의 점에 유의하면 우리 다른 노드에 대한 포인터를 그려, 그
문제가되지 않는 곳 화살촉 다른 노드를 충족합니다.
샘플 사전 트라이는 포함 두 단어, 즉 줌.
의는의 예를 살펴 보겠습니다 키에 대한 데이터를 찾고입니다.
>> 우리가보고 싶어한다고 가정 키 목욕 값을 해당.
우리는 우리의 모습을 시작합니다 루트 노드.
그런 다음 우리는 우리의 첫 번째 편지 할게요 키 B, 및 대응하는 정보를 찾아
우리 아이 배열에 자리.
정확히 26 반점이 있다는 것을 알 수 배열의 각 문자 하나
알파벳.
그리고 우리는 관광 명소가 표현해야합니다 순서대로 알파벳의 편지입니다.
>> 우리는 두 번째 인덱스에 대해 알아 보겠습니다 일반적으로 B의 인덱스 하나, 만약에 우리
일부 알파벳 문자 C의 우리가 해당 지점을 결정할 수
사용하여 아이들의 배열 이 같은 계산.
우리는 더 큰 아이들을 사용할 수도 우리는 모양 업을 제공하고 싶었 배열하는 경우
다양한 문자와 키 예를 들면 전체로
ASCII 문자를 설정합니다.
>> 이 경우, 포인터 우리 아이 배열에있는
인덱스에 null이 아닙니다.
그래서 우리는 계속 찾고 있습니다 키 목욕 업.
우리는 지금까지 널 포인터가 발생하는 경우 아이들의 적절한 자리에
어레이 우리는 노드를 통과하는 동안, 우리는 우리 말을해야합니다
해당 키에 대한 아무것도 찾을 수 없습니다.
>> 이제, 우리는 두 번째 편지 할게요 우리의 키, A, 계속 다음
이러한 방식으로 포인터 우리까지 우리 키의 단부에 도달한다.
우리없이 키의 끝에 도달하면 죽은 끝을 타격, 널 포인터,
경우는 여기로, 우리 만 한 가지 더 확인해야합니다.
이 열쇠 실제로 사전에?
>> 그렇다면, 우리는 잘 값을 찾아야한다 우리 그림의 웃는 얼굴 아이콘 위치
단어가 종료됩니다.
에 저장된 다른 뭔가가있는 경우 데이터는, 우리는 그것을 반환 할 수 있습니다.
예를 들어, 키 동물원에없는 우리가 할 수 있더라도 사전,
이제까지없이이 키의 끝에 도달 , 널 포인터를 치는 동안 우리
트라이를 반복.
>> 우리는 키 목욕을 올려 보았습니다 경우 마지막 노드의 배열 인덱스 두 번째,
, 편지 H에 해당하는 것 널 포인터를 개최했다.
그래서 목욕은 사전에 없습니다.
그리고 트라이는 키에 고유 명시 적으로 저장되지 않습니다
데이터 구조.
그렇다면 우리는 무엇인가를 삽입합니까 트라이에?
>> 의 키를 삽입하자 우리의 트라이에 동물원.
기억이 노드에서 웃는 얼굴 간단한에 코드에 해당하는 수
그 동물원를 나타내는 부울 값 사전에 또는 그것을 할 수
자세한 내용에 해당하는 우리 키 동물원과 연결하려면,
정의처럼 단어 또는 뭔가.
어떤면에서, 프로세스는 삽입 트라이에 뭔가 비슷합니다
트라이에서 뭔가를 찾고.
>> 우리는 다시 루트 노드로 시작한다 다음 포인터에 해당하는
우리의 키의 문자.
다행히, 우리는 포인터를 수행 할 수 있었다 우리가 도달 할 때까지 모든 방법
키의 단부.
동물원은 단어의 접두사이기 때문에 의 구성원 줌,
사전은, 우리가 할 필요가 없습니다 새로운 노드를 할당합니다.
>> 우리는 표시하는 노드를 수정할 수 에 선행 문자의 경로
우리의 사전에서 키를 나타냅니다.
이제 삽입 해보자 트라이에 키 BATH.
우리는 루트 노드에서 시작하자 다시 포인터를 따릅니다.
그러나이 상황에서, 우리는 죽은 충돌 우리가 얻을 수있어 이전에 종료
키의 끝.
이제, 우리는 새로운 할당해야합니다 노드가 하나의 새로운 할당해야합니다
나머지 각 노드에 대한 우리의 키의 문자.
>> 이 경우, 우리는 단지 필요 하나의 새로운 노드를 할당 할 수 있습니다.
그 다음 우리는 H 지수를 확인해야합니다 이 새로운 노드를 참조합니다.
다시 한번, 우리는에 노드를 수정할 수 있습니다 나타낸다고 문자 경로
그것을 선도를 나타냅니다 우리의 사전에있는 키를 누릅니다.
의는 점근 적 추론하자 이러한 우리의 절차의 복잡성
두 가지 작업.
>> 우리는 알이 두 경우의 수 우리의 알고리즘은 한 걸렸다 단계
의 개수에 비례 키워드의 편지.
맞아요.
당신의 단어를 검색 할 때 트라이 당신은 단지를 반복 할 필요가
글자 하나 하나 때까지 하나 단어의 끝 또는 도달
트라이에 막 다른 골목을 기록했다.
>> 그리고 당신은 키를 삽입 할 때 사용 트라이에 값 쌍
절차 우리는 최악의 경우를 논의 새로운 노드를 할당해야합니다
각 문자.
그리고 우리는 그 할당을 가정합니다 일정 시간 작업입니다.
우리는 키 길이가 가정이 경우 고정 된 상수, 모두에 의해 제한
삽입과 조회가 일정하다 트라이 시간 작업.
>> 우리는이 가정을하지 않으면 그 키 길이는 고정에 묶여있다
상수, 다음 삽입 및 조회, 최악의 경우에 선형
키의 길이.
아이템의 개수가 저장된 것을 알 트라이의 모습을 영향을주지 않습니다
또는 삽입 시간.
그것은 단지 영향있어 키의 길이.
>> 반대로 말하자면,에 항목을 추가, 해시 테이블 만드는 경향
미래는 느린 찾아보십시오.
이 처음에는 매력적인 사운드 수 있지만 우리가 염두에 두어야하는
유리한 점근 복잡하지 않습니다 말은 그 연습의 데이터
구조가 필요하다 비난을 넘어.
우리는 또한 저장하는 것을 고려해야합니다 최악의에서 우리가 필요로하는 트라이, 단어
케이스, 노드들의 개수에 비례 단어 자체의 길이.
>> 시도는 많은 공간을 사용하는 경향이있다.
즉, 해시 테이블과 대조의 정보, 우리는 단지 하나의 새로운 노드를 필요로하는 곳에
일부 키 값 쌍을 저장합니다.
이제, 다시 이론, 큰 공간 소비가 큰 아닌 것 같아
특히 주어진 처리하는 현대 컴퓨터는 기가 바이트를 가지고
메모리의 기가 바이트.
하지만 우리는 여전히이 밝혀 메모리 사용에 대한 걱정
의 이익을 위해 조직 성능, 이후 현대 컴퓨터
아래의 장소에있는 메커니즘이 메모리 액세스 속도를 높일 수 후드.
>> 그러나 이러한 메커니즘은 가장 좋은 때 작동 메모리 액세스는 소형에서한다
지역이나 지역.
그리고 트라이의 노드가 상주 할 수 그 힙의 아무 곳.
그러나 이러한 트레이드 오프입니다 우리는 고려해야합니다.
>> 데이터를 선택할 때, 그 기억 특정 작업에 대한 구조, 우리
에 대해 생각해야 어떤 종류의 작업 데이터 구조는 필요
지원 얼마나 성능 이들 각각의
우리에게 운영 문제.
이러한 작업도 할 수있다 그냥 넘어 확장
기본적인 모양의 위로 삽입.
우리는 친절을 구현하고 싶어한다고 가정 자동 완성 기능의 많은
같은 구글의 검색 엔진은 않습니다.
즉, 모든 키를 반환 잠재적으로 가치있는
특정 접두사가.
>> 트라이 고유 유용 이 작업.
그것은을 통해 반복하는 간단합니다 각 문자의 트라이
접두사.
다만, 조회 작업 등 우리는 포인터를 수행 할 수
문자 단위.
그 후, 우리는 말에 도착하면 접두사, 우리는을 반복 할 수
데이터 구조의 나머지 부분 키 중 하나 이상 이후
이 점은 접두사가.
>> 그것은이 리스팅을 얻기도 쉽다 이후 알파벳 순서로
어린이 배열의 요소 알파벳 순으로 정렬됩니다.
그래서 희망을 고려해야합니다 기부는 시도를하려고합니다.
나는 케빈 슈미트 해요, 이것은 CS50입니다.
>> 아, 이것은 시작에 불과하다 감소.
미안 해요.
>> 네 스트라이크.
나도 야.
미안 해요.
사람을 만들기위한 죄송합니다 사람 이 미쳐 편집 할 수 있습니다.
>> 미안 해요.
미안 해요.
>> 스피커 1 : 잘 했어.
그건 정말 잘 이루어졌다.