[MUSIC CHƠI] DOUG LLOYD: Vì vậy, chúng tôi đã nhích gần hơn và gần gũi hơn mà Chén thánh của dữ liệu cấu trúc, một trong đó chúng ta có thể chèn vào, xóa từ, và nhìn lên trong thời gian liên tục. Bên phải. Đó là loại khung thành. Chúng tôi muốn có thể làm điều rất, rất nhanh chóng. 

Chúng ta đã tìm thấy nó ở đây khi chúng ta đang nói về cố gắng? Vâng, chúng ta hãy có một cái nhìn. Vì vậy, chúng tôi đã nhìn thấy một số cấu trúc dữ liệu khác nhau có thể xử lý các bản đồ của Cái gọi là cặp khóa-giá trị, lập bản đồ số phần dữ liệu để một số phần khác của dữ liệu vì vậy chúng tôi biết nơi để tìm thấy thông tin trong cấu trúc. 

Vì vậy, đối với mảng, ví dụ, Điều quan trọng là các chỉ số phần tử hay mảng vị trí 0 hoặc 1 mảng và như vậy. Và giá trị là các dữ liệu mà tồn tại ở vị trí đó. Vì vậy, những gì được lưu trữ trong mảng 0? Những gì được lưu trong mảng 1 so với chỉ 0 và 1, đó sẽ là chìa khóa. 

Với một bảng băm nó loại ý tưởng tương tự. Với một bảng băm, chúng ta có băm này chức năng mà tạo mã băm. Vì vậy, điều quan trọng là các mã băm của dữ liệu. Và giá trị, đặc biệt chúng tôi nói chuyện về chuỗi trong đoạn video trên bảng băm, là danh sách liên kết dữ liệu mà băm để hashcode đó. Bên phải. Những gì về cách tiếp cận khác phương pháp này, mặc dù? Những gì về một phương pháp mà các quan trọng là đảm bảo là duy nhất, không giống như một bảng băm, nơi chúng tôi có thể kết thúc với hai mẩu dữ liệu có hashcode cùng. Và sau đó chúng ta phải đối phó với rằng bằng cách hoặc là thăm dò hay hơn tốt chain để khắc phục vấn đề đó. 

Vì vậy, bây giờ chúng tôi có thể đảm bảo rằng chính của chúng tôi là duy nhất. Và nếu giá trị của chúng tôi là chỉ một cái gì đó dễ dàng như đúng và sai cho chúng ta biết liệu hoặc không có mẩu thông tin tồn tại trong cấu trúc? Một Boolean có thể đơn giản như là một chút. Thực tế nó có thể là một byte nhiều hơn một chút. Nhưng đó là nhỏ hơn rất nhiều so với lưu trữ có thể là một chuỗi 50 ký tự, Ví dụ như. 

Vì vậy, cố gắng, tương tự như bảng băm, trong đó kết hợp các mảng và danh sách liên kết, cố gắng kết hợp các mảng, cấu trúc, và con trỏ với nhau để lưu trữ dữ liệu trong một cách thú vị đó là khá khác nhau từ bất cứ điều gì chúng ta đã thấy cho đến nay. Bây giờ chúng ta sử dụng các dữ liệu như là một lộ trình để điều hướng cấu trúc dữ liệu này. Và nếu chúng ta có thể làm theo lộ trình, nếu chúng ta có thể theo các dữ liệu từ đầu đến cuối, chúng tôi sẽ biết liệu dữ liệu tồn tại trong Trie. 

Và nếu chúng ta không thể làm theo bản đồ từ có nghĩa là kết thúc ở tất cả, các dữ liệu không thể tồn tại. Một lần nữa, các phím ở đây là đảm bảo là duy nhất. Và không giống như một bảng băm, chúng tôi sẽ không bao giờ phải đối phó với các va chạm ở đây. Và không có hai mẩu dữ liệu có chính xác cùng một lộ trình trừ khi dữ liệu đó là giống hệt nhau. 

Nếu chúng ta chèn John, sau đó chúng tôi tìm kiếm cho John. Đó là hai phần giống hệt nhau của dữ liệu, phải, chúng tôi đang tìm kiếm thông qua. Nhưng nếu không, bất kỳ hai mẩu dữ liệu là đảm bảo để có lộ trình độc đáo thông qua các cấu trúc dữ liệu này. Và chúng ta sẽ có một cái nhìn tại một hình ảnh của này chỉ trong một khoảnh khắc. 

Chúng tôi sẽ làm điều này bằng cách cố gắng tạo ra một cấu trúc dữ liệu mới, lập bản đồ các cặp giá trị quan trọng sau đây. Trong trường hợp này, chúng tôi sẽ không sử dụng một cái gì đó đơn giản như một Boolean. Chúng tôi sẽ thực sự lưu trữ các chuỗi. Và chuỗi được sắp là tên của một trường đại học. 

Và chìa khóa là có được năm khi các trường đại học được thành lập. Tất cả các trường đại học năm sẽ có bốn chữ số. Và vì vậy chúng tôi sẽ sử dụng những bốn chữ số điều hướng thông qua các cấu trúc dữ liệu này. Và chúng ta sẽ thấy, một lần nữa, làm thế nào chúng tôi làm điều đó chỉ trong một giây. 

Vào cuối của con đường, chúng ta sẽ thấy tên của các trường đại học tương ứng với phím đó, bốn chữ số. Ý tưởng cơ bản đằng sau một Trie là chúng ta có một tuyến đường trung tâm. Vì vậy, suy nghĩ về nó như một cái cây. Và điều này cũng tương tự như trong chính tả và trong khái niệm một cái cây. Thông thường khi chúng ta nghĩ về cây trong thế giới thực, họ có một gốc đó là trong mặt đất và chúng lớn lên và họ có các chi nhánh và họ có lá. Và về cơ bản các ý tưởng của một Trie là giống hệt nhau, trừ gốc được neo một nơi nào đó trên bầu trời. Và lá ở phía dưới. 

Vì vậy, nó là loại giống như dùng một cây và chỉ flipping nó lộn ngược. Nhưng vẫn có những lĩnh. Và những người sẽ là con đường của chúng tôi, những người sẽ kết nối chúng tôi từ gốc đến lá. Trong trường hợp này, những người con đường, những chi nhánh được dán nhãn bằng các con số đó cho chúng tôi có cách nào để đi từ nơi mà chúng ta đang có. 

0 nếu chúng ta thấy, chúng ta đi xuống chi nhánh này, nếu chúng ta nhìn thấy một 1, chúng tôi đi xuống chi nhánh này, và như vậy và như vậy. Vâng, điều này có nghĩa là gì? Vâng, điều đó có nghĩa rằng tại mỗi điểm giao nhau và tất cả các nút trong giữa và các chi nhánh, có 10 thể những nơi mà chúng ta có thể đi. Vì vậy, có 10 con trỏ từ mọi vị trí. 

Và đây là nơi mà cố gắng có thể có được một chút đáng sợ cho ai đó những người không có nhiều kinh nghiệm trong khoa học máy tính trước. Nhưng cố gắng thực sự là khá tuyệt vời. Và nếu bạn có cơ hội để làm việc với họ và bạn đã sẵn sàng để đào-in và thử nghiệm với họ, chúng thực sự khá thú vị cấu trúc dữ liệu để làm việc với. Nếu chúng ta muốn chèn một phần tử vào Trie, tất cả chúng ta cần phải làm được xây dựng con đường đúng từ gốc đến lá. Dưới đây là những gì mọi bước dọc đường có thể trông như thế nào. Chúng tôi sẽ xác định một dữ liệu mới cấu trúc cho một nút mới được gọi là một Trie. 

Và bên trong các dữ liệu mà cấu trúc có hai miếng. Chúng ta sẽ lưu các tên của một trường đại học. Và chúng ta sẽ lưu một mảng của các con trỏ với các nút khác cùng loại. Vì vậy, một lần nữa, đây là loại đó các khái niệm về khắp mọi nơi chúng tôi, chúng tôi có thể ở mức 10 nơi chúng ta có thể đi. 0 nếu chúng ta thấy, chúng ta đi xuống chi nhánh này. Nếu chúng ta nhìn thấy một 1, chi nhánh này, vv và vv và vv. Nếu chúng ta nói 9, chúng tôi đi xuống chi nhánh này. Vì vậy, tại mỗi điểm giao nhau, chúng ta có thể đi 10 địa điểm có thể. Vì vậy, mỗi node có chứa 10 con trỏ với các nút khác, để 10 nút khác. 

Và các dữ liệu chúng tôi đang lưu trữ là chỉ là tên của các trường đại học. Vì vậy, hãy xây dựng một Trie. Hãy chèn một vài các mục vào Trie của chúng tôi. Vì vậy, ở phía trên đỉnh, đây là nút gốc của chúng tôi. Đây có lẽ sẽ là một cái gì bạn đang đi trên toàn cầu khai báo. Và bạn đang đi trên toàn cầu duy trì một con trỏ đến nút này luôn. 

Bạn sẽ nói, gốc bằng, và bạn đi để malloc mình nút Trie. Và bạn sẽ không bao giờ chạm vào gốc một lần nữa. Mỗi khi bạn muốn bắt đầu điều hướng thông qua, bạn đặt con trỏ khác bằng gốc, chẳng hạn như trav, đó là những ví dụ tôi sử dụng trong rất nhiều các video của tôi đây trên ngăn xếp và hàng đợi và danh sách liên kết và như vậy. 

Bạn đặt con trỏ khác gọi trav cho traversal. Và bạn sử dụng để điều hướng trav thông qua các cấu trúc dữ liệu. Vì vậy, chúng ta hãy xem làm thế nào điều này có thể xem xét. Vì vậy, ngay bây giờ, những gì không một nút như thế nào? Vâng, chỉ là dữ liệu của chúng tôi khai báo cấu trúc chỉ ra, chúng ta có một chuỗi, trong trường hợp này là trống rỗng. Không có gì ở đây cả. 

Và một mảng 10 con trỏ. Và ngay bây giờ, chúng ta chỉ có 1 nút ở Trie này. Không có gì khác trong nó. Vì vậy, tất cả 10 người điểm con trỏ null. Đó là những gì màu đỏ cho biết. 

Hãy chèn chuỗi Harvard. Hãy chèn Đại học Harvard vào Trie này, mà được thành lập vào năm 1636. Chúng tôi muốn sử dụng chìa khóa, 1636, cho chúng tôi biết chúng tôi sẽ lưu học Harvard ở Trie. Bây giờ, làm thế nào chúng ta có thể làm điều đó? 

Nó có thể giống như thế này. Chúng tôi bắt đầu từ gốc rễ. Và chúng ta có những 10 địa điểm chúng ta có thể đi. Gốc là giống như bất kỳ nút khác của Trie. Có 10 địa điểm chúng ta có thể đi từ đây. 

Nơi nào chúng ta có thể muốn để đi nếu chính là năm 1636? Có thực sự hai lựa chọn. Bên phải. Chúng tôi có thể xây dựng các chính từ phải sang trái và bắt đầu với 6. Hoặc chúng ta có thể xây dựng các chính từ trái sang phải và bắt đầu với 1. 

Đây có thể là nhiều hơn trực quan như một con người để hiểu rằng chúng tôi sẽ chỉ đi trái sang phải. Và vì vậy nếu tôi muốn chèn Harvard vào Trie này, Tôi có lẽ muốn bắt đầu được bắt đầu từ gốc, nhìn vào 10 Lựa chọn của tôi trước mặt tôi, và nói Tôi muốn đi theo con đường 1. ĐƯỢC. 

Bây giờ, 1 con đường là hiện null. Vì vậy, nếu tôi muốn tiếp tục con đường đó để chèn phần tử này vào Trie, Tôi có để malloc một nút mới, có 1 điểm đó, và sau đó tôi là tốt để đi. 

Vì vậy, về cơ bản tôi đang ở một điểm mà tôi đang đứng ở gốc của cây hoặc Trie và có 10 chi nhánh. Nhưng mỗi chi nhánh có một cổng ở phía trước của nó. Bên phải. Bởi vì không có gì khác có. Không có lối đi an toàn. Điều đó có nghĩa rằng không có gì là xuống bất kỳ của các ngành đó. Nếu tôi muốn bắt đầu xây dựng một cái gì đó, tôi muốn loại bỏ các cửa khẩu. Tôi muốn loại bỏ cổng trước số 1. Và tôi muốn đi bộ xuống đó. Và tôi muốn xây dựng một nơi để tôi đi. 

Và đó là những gì tôi đã thực hiện ở đây. Vì vậy, 1 không còn chỉ để null. Tôi đã nói nó an toàn để đi xuống đây ngay bây giờ. Tôi xây dựng một nút khác. Và khi tôi được nút đó, tôi có một quyết định để thực hiện. Tôi sẽ đi đâu để đi từ đây? 

Vâng, tôi đã đi xuống 1. Vì vậy, bây giờ tôi có thể muốn đi xuống 6. Bên phải. Một lần nữa, tôi có 10 địa điểm tôi có thể lựa chọn. Vì vậy, bây giờ chúng ta đi xuống số 6. Vì vậy, tôi xóa cổng ở phía trước của số 6. Và tôi đi bộ xuống đó. Và tôi xây dựng một nút khác. Và tôi đã đạt đến một điểm giao nhau. 

Một lần nữa, tôi có 10 lựa chọn cho nơi tôi có thể đi. Tôi đã di chuyển 1-6. Vì vậy, bây giờ tôi có thể muốn đi đến 3. 3, có nơi nào tôi có thể đi. Vì vậy, tôi phải dọn đường và xây dựng cho mình một không gian mới. Và sau đó từ 3, nơi nào tôi muốn đi đâu? Tôi muốn đi xuống 6. 

Và, một lần nữa, tôi đã phải dọn đường để làm điều đó. Vì vậy, bây giờ tôi đã sử dụng chìa khóa của tôi để chèn tạo nút và bắt đầu xây dựng Trie này. Tôi đã bắt đầu ở gốc. Tôi đã đi xuống 1636. Và bây giờ tôi đang ở phía dưới có vào nút đó. Và bạn có thể có thể nhìn thấy nó trên màn hình của bạn. 

Nó đánh dấu màu vàng. Đó là nơi mà tôi hiện nay. Chìa khóa của tôi được thực hiện. Tôi đã kiệt sức từng vị trí trong chính tôi. Vì vậy, tôi không thể đi xa hơn nữa. Vì vậy, tại thời điểm này, tất cả tôi thực sự cần phải làm là nói, OK. Nó loại thích tìm kiếm xuống đất, nếu bạn đang hình dung mình là loại này con đường với các kết nối khác nhau. Sắp xếp nhìn xuống và loại phun sơn Harvard trên mặt đất. Đó là tên của điều này. Biết đó là những gì tại địa điểm này. Nếu chúng ta bắt đầu ở gốc và chúng tôi đi xuống 1 và sau đó 6 và sau đó 3 và sau đó 6, chúng ta ở đâu? Vâng, nếu chúng ta nhìn xuống và chúng ta thấy Harvard, sau đó chúng ta biết rằng Harvard là thành lập năm 1636 có trụ sở trên đường chúng tôi đang thực thi cấu trúc dữ liệu này. Vì vậy, đó là hy vọng đơn giản. Chúng ta sẽ phải làm hai phần thêm vào nhiều hơn nữa. Và hy vọng rằng nó sẽ giúp thấy điều này được thực hiện hai lần nữa. 

Bây giờ, chúng ta hãy chèn các trường đại học khác. Hãy chèn Yale vào Trie này. Yale được thành lập vào năm 1701. Vì vậy, chúng tôi sẽ bắt đầu ở root, như chúng ta vẫn thường làm. Và chúng tôi thiết lập một con trỏ traversal. Chúng ta sẽ sử dụng để di chuyển qua. Điều đầu tiên chúng tôi muốn làm là đi xuống con đường 1. Đó là chữ số đầu tiên của chính chúng tôi. May mắn thay, tuy nhiên, chúng tôi không phải làm bất kỳ công việc lần này. Các đường 1 đã được giải tỏa. Tôi xóa nó trước khi tôi được chèn Harvard tại 1636. Vì vậy, tôi có thể di chuyển một cách an toàn xuống 1 và chỉ đi đến đó. Nếu có thể di chuyển xuống 1. 

Bây giờ, tuy nhiên, tôi muốn đi đến 7. Tôi đã mở đường tại 6. Tôi biết tôi có thể an toàn đi xuống 6 con đường. Nhưng tôi cần phải tiến hành trên con đường 7. Vì vậy, những gì tôi cần phải làm gì? Vâng, giống như trước đây, tôi chỉ cần để xóa các cửa khẩu, có được ra khỏi con đường, và xây dựng một nút mới từ con đường 7. Chỉ như thế này. 

Vì vậy, bây giờ tôi đã thay đổi 1 và sau đó 7. Và bây giờ thông báo, tôi đang sắp xếp của trên nhánh phụ mới này. Bên phải. Mọi thứ khác từ 16 trên, tôi không quan tâm. Tôi không làm bất cứ điều gì 16. Tôi đang làm 17 công cụ. 

Vì vậy, bây giờ từ 17 trở đi, tôi phải loại blaze đường mòn mới đây. Các chữ số tiếp theo chìa khóa của tôi là 0. Tôi rõ ràng không thể có được bất cứ nơi nào. Tôi chỉ cần xây dựng nút này. Vì vậy, tôi biết không có con đường phía trước từ đây. Vì vậy, tôi phải làm một bản thân mình. 

Vì vậy, tôi malloc một nút mới và có 0 điểm đó. Và sau đó một lần nữa, tôi malloc một nút mới và có một điểm ở đó. Một lần nữa, tôi đã kiệt sức quan trọng của tôi, năm 1701. Vì vậy, tôi nhìn xuống và tôi phun sơn Yale. Đó là tên của nút này. 

Và vì vậy bây giờ nếu tôi cần phải xem nếu Yale đang ở Trie này, tôi bắt đầu ở gốc, Tôi đi xuống 1701, và nhìn xuống. Và nếu tôi thấy phun Yale sơn lên mặt đất, sau đó Tôi biết Yale tồn tại Trie này. Hãy làm một nhiều hơn. Hãy chèn Dartmouth vào đây Trie, được thành lập vào năm 1769. 

Bắt đầu tại gốc một lần nữa. Chữ số đầu tiên của tôi về chìa khóa của tôi là 1. Tôi một cách an toàn có thể di chuyển xuống con đường đó. Điều đó đã tồn tại. Các chữ số tiếp theo của chính tôi là 7. Tôi một cách an toàn có thể di chuyển xuống con đường đó. Nó tồn tại là tốt. 

Tiếp theo của tôi là 6. Từ đây, từ nơi tôi hiện nay màu vàng có trong đó nút giữa, 6 hiện đang bị khóa ra. Nếu tôi muốn đi xuống con đường đó, Tôi có để xây dựng bản thân mình. Vì vậy, tôi sẽ malloc một nút mới và có 6 điểm ở đó. Và sau đó, một lần nữa, tôi lòng đam mê những con đường mòn mới đây. 

Vì vậy, tôi malloc một nút mới để từ rằng số con đường node-- 9-- và sau đó bây giờ nếu tôi đi du lịch năm 1769, và tôi nhìn xuống. Không có gì hiện phun sơn có. Tôi có thể viết Dartmouth. Và tôi đã chèn Dartmouth vào Trie. 

Vì vậy, đó là chèn điều vào Trie. Bây giờ chúng tôi muốn tìm kiếm những điều. Làm thế nào để chúng tôi tìm kiếm những thứ trong Trie? Vâng, đó là khá nhiều những ý tưởng tương tự. Bây giờ chúng ta chỉ cần sử dụng các chữ số của khóa để xem liệu chúng ta có thể di chuyển từ gốc đến nơi mà chúng ta muốn đi trong Trie. 

Nếu chúng ta đánh một kết thúc chết vào thời điểm bất kỳ, sau đó chúng ta biết rằng yếu tố đó không thể tồn tại hoặc người nào khác con đường đó sẽ đã được giải tỏa. Nếu chúng ta làm cho nó tất cả các cách để Cuối cùng, tất cả chúng ta cần phải làm là nhìn xuống và thấy nếu đó là các yếu tố chúng tôi đang tìm kiếm. Nếu có, thành công. Nếu không, không. 

Vì vậy, hãy tìm kiếm Harvard ở Trie này. Chúng tôi bắt đầu từ gốc rễ. Và, một lần nữa, chúng ta sẽ tạo ra một con trỏ traversal để làm di chuyển của chúng tôi đối với chúng tôi. Từ gốc chúng ta biết rằng nơi đầu tiên chúng ta cần phải đi là 1, chúng ta có thể làm điều đó? Vâng, chúng tôi có thể. Nếu an toàn tồn tại. Chúng tôi có thể đến đó. 

Bây giờ, địa điểm tiếp theo chúng ta cần phải đi là 6. Có 6 con đường tồn tại từ đây? Vâng, nó. Chúng tôi có thể đi xuống trong 6 đường. Và chúng ta kết thúc ở đây. 

Chúng ta có thể đi xuống 3 đường đi từ đây? Vâng, khi nó quay ra, có, mà tồn tại quá. Và chúng ta có thể nhận được trên 6 đường đi từ đây? Vâng, chúng tôi có thể. 

Chúng tôi đã không hoàn toàn trả lời các câu hỏi được nêu ra. Vẫn có một nhiều hơn bước, mà bây giờ là chúng ta cần phải nhìn xuống và xem đó là actually-- nếu chúng ta đang tìm kiếm Harvard, là những gì chúng tôi tìm thấy sau khi chúng tôi cạn kiệt phím? Trong ví dụ này chúng ta sử dụng ở đây, những năm qua luôn bốn chữ số. Nhưng bạn có thể sử dụng ví dụ nơi bạn đang lưu trữ một từ điển các từ. 

Và do đó, thay vì có 10 con trỏ cho vị trí của tôi, bạn có thể có 26. Một cho mỗi chữ cái của bảng chữ cái. Và có một số từ như dơi, mà là một tập hợp con của hàng loạt, ví dụ. Và do đó, ngay cả khi bạn nhận được đến cuối khóa và bạn nhìn xuống, bạn có thể không nhìn thấy gì bạn đang tìm kiếm. 

Vì vậy, bạn luôn phải đi qua toàn bộ con đường và sau đó nếu bạn là thành công có thể để đi qua toàn bộ con đường, nhìn xuống và làm một xác nhận cuối cùng. Có phải đó là những gì tôi đang tìm kiếm? Vâng, tôi nhìn xuống sau khi bắt đầu ở đầu và đi 1636. Tôi nhìn xuống. Tôi thấy Harvard. Vì vậy, có, tôi đã thành công. Điều gì nếu những gì tôi đang tìm kiếm không có trong Trie, mặc dù. Nếu tôi đang tìm Princeton, được thành lập năm 1746. Và do đó, năm 1746 sẽ trở thành chìa khóa của tôi để điều hướng thông qua các Trie. Vâng, tôi bắt đầu từ gốc rễ. Và nơi đầu tiên tôi muốn để đi xuống con đường 1. Tôi có thể làm điều đó? Vâng tôi có thể. 

Tôi có thể đi xuống con đường 7 từ đó? Vâng, tôi có thể. Mà tồn tại quá. Nhưng tôi có thể đi xuống 4 đường đi từ đây? Điều đó giống như đặt câu hỏi, có thể Tôi đi xuống mà hơi vuông mà tôi đã đánh dấu màu vàng? Có gì ở đó. Bên phải. 

Không có con đường phía trước xuống con đường 4. Nếu Princeton là ở Trie này, mà 4 sẽ được giải tỏa cho chúng ta rồi. Và vào thời điểm này chúng tôi đã đạt đến một kết thúc chết. Chúng tôi không thể đi xa hơn nữa. Và vì vậy chúng tôi có thể nói, dứt khoát, không có. Princeton không tồn tại trong Trie này. 

Vì vậy, điều này có nghĩa là tất cả? Bên phải. Có rất nhiều xảy ra ở đây. Có con trỏ khắp nơi. Và, như bạn có thể nhìn thấy chỉ từ các sơ đồ, có rất nhiều các nút đó được loại bay xung quanh. Nhưng chú ý mỗi khi chúng ta muốn kiểm tra xem có điều gì đó trong Trie, chúng tôi chỉ có để làm cho 4 di chuyển. 

Mỗi lần chúng tôi muốn chèn một cái gì đó trong Trie, chúng ta phải làm cho 4 di chuyển, có thể mallocing một số thứ trên đường đi. Tuy nhiên, như chúng ta đã thấy khi chúng ta chèn Dartmouth vào Trie, đôi khi một số con đường có thể đã được xóa cho chúng tôi. Và như vậy, chúng tôi Trie lớn dần và lớn hơn, chúng tôi có làm việc ít hơn mỗi khi để chèn những điều mới bởi vì chúng tôi đã đã xây dựng rất nhiều các trung gian chi nhánh trên đường đi. Nếu chúng ta chỉ có bao giờ phải nhìn vào 4 điều, 4 chỉ là một hằng số. Chúng tôi thực sự được tiếp cận loại chèn thời gian liên tục và tra cứu thời gian liên tục. Sự thỏa hiệp, dĩ nhiên, là rằng Trie này, như bạn có thể cho biết, là rất lớn. Mỗi một trong các nút chiếm rất nhiều không gian. 

Nhưng đó là sự đánh đổi. Nếu chúng ta muốn thực sự nhanh chóng chèn, xóa thực sự nhanh chóng, và tra cứu thực sự nhanh chóng, chúng ta phải có rất nhiều dữ liệu bay xung quanh. Chúng ta phải dành rất nhiều không gian và bộ nhớ cho rằng cấu trúc dữ liệu tồn tại. 

Và đó là sự đánh đổi. Nhưng có vẻ như chúng tôi có thể tìm thấy nó. Chúng ta có thể thấy rằng Chén thánh của cấu trúc dữ liệu với chèn nhanh chóng, xóa, và tra cứu. Và có lẽ đây sẽ là một cấu trúc dữ liệu thích hợp để sử dụng cho bất cứ thông tin chúng tôi đang cố gắng để lưu trữ. Tôi Doug Lloyd, đây là CS50.