KEVIN Schmid: Đôi khi, khi xây dựng một chương trình, bạn có thể muốn sử dụng một cấu trúc dữ liệu được biết đến như một từ điển. Một bản đồ từ điển phím, trong đó có dây thông thường, với các giá trị, số nguyên, ký tự, một con trỏ đến một số đối tượng, bất cứ điều gì chúng ta muốn. Nó chỉ giống như từ điển thông thường từ bản đồ thông qua các định nghĩa. 

Từ điển cung cấp cho chúng tôi với khả năng lưu trữ thông tin kết hợp với một cái gì đó và nhìn nó lên sau đó. Vì vậy, làm thế nào để chúng tôi thực sự thực hiện một từ điển, nói, mã C mà chúng ta có thể sử dụng trong một chương trình của chúng tôi? Vâng, có rất nhiều cách mà chúng ta có thể thực hiện một cuốn từ điển. 

Đối với một, chúng ta có thể sử dụng một mảng mà chúng ta tự động chỉnh lại kích thước hoặc chúng ta có thể sử dụng một danh sách liên kết, bảng băm hoặc một cây nhị phân. Nhưng bất cứ điều gì chúng ta lựa chọn, chúng ta nên hãy chú ý đến hiệu quả và hiệu suất của việc thực hiện. Chúng ta nên suy nghĩ về các thuật toán sử dụng để chèn và tìm kiếm các mục vào cấu trúc dữ liệu của chúng tôi. 

Bây giờ, chúng ta hãy giả sử chúng ta có muốn sử dụng chuỗi như là chìa khóa. Hãy nói về một khả năng, một cấu trúc dữ liệu gọi là một Trie. Vì vậy, đây là một hình ảnh đại diện của một Trie. 

Như hình ảnh cho thấy, một Trie là một cấu trúc dữ liệu cây với các nút liên kết với nhau. Chúng ta thấy rằng có rõ ràng là một gốc nút với một số liên kết mở rộng để các nút khác. Nhưng những gì hiện mỗi nút bao gồm? Nếu chúng ta giả định rằng chúng ta giữ phím bằng ký tự chữ cái, và chúng tôi không quan tâm về vốn, đây là một định nghĩa của một nút sẽ đủ. 

Một đối tượng có kiểu là cấu trúc nút có hai phần gọi là dữ liệu và trẻ em. Chúng tôi đã để lại một phần dữ liệu như một bình luận được thay thế bằng một thành phần khai khi cấu trúc nút là kết hợp trong một chương trình C. Một phần dữ liệu của một nút có thể là một Giá trị boolean để cho biết hoặc không nút đại diện cho việc hoàn thành của một phím từ điển hoặc nó có thể là một chuỗi đại diện cho định nghĩa của một từ trong từ điển. 

Chúng tôi sẽ sử dụng một khuôn mặt cười để chỉ khi dữ liệu được trình bày trong một nút. Có 26 yếu tố trong của chúng tôi trẻ em mảng, một chỉ số mỗi ký tự chữ cái. Chúng ta sẽ thấy được tầm quan trọng điều này sớm. 

Chúng ta hãy xem xét kỹ hơn các nút gốc trong sơ đồ của chúng tôi, mà không có dữ liệu liên kết với nó, như được chỉ ra bởi các trường hợp không có các khuôn mặt cười trong phần dữ liệu. Các mũi tên kéo dài từ các bộ phận của mảng trẻ em đại diện cho không nút con trỏ đến các nút khác. Ví dụ, mũi tên kéo dài từ yếu tố thứ hai của trẻ em đại diện cho chữ B trong một khóa từ điển. Và trong sơ đồ lớn hơn chúng ta gọi nó với một B. 

Lưu ý rằng trong sơ đồ lớn hơn, khi chúng ta vẽ một con trỏ đến nút khác, nó không quan trọng nơi đầu mũi tên hội tụ đủ các nút khác. Từ điển mẫu của chúng tôi Trie chứa hai từ, đó và zoom. Chúng ta hãy đi bộ qua một ví dụ về tìm kiếm dữ liệu cho một khóa. 

Giả sử chúng ta muốn tìm kiếm các giá trị tương ứng cho phòng tắm chính. Chúng tôi sẽ bắt đầu nhìn chúng tôi lên tại nút gốc. Sau đó chúng tôi sẽ lấy chữ cái đầu tiên của chúng tôi chính, B, và tìm thấy những tương ứng phát hiện trong mảng con em chúng ta. Chú ý rằng có chính xác 26 điểm trong mảng, một cho mỗi thư bảng chữ cái. Và chúng tôi sẽ có những điểm đại diện cho chữ của bảng chữ cái theo thứ tự. 

Chúng tôi sẽ xem xét chỉ số thứ hai sau đó, chỉ số một, cho B. Nói chung, nếu chúng ta có một số chữ cái ký tự C chúng tôi có thể xác định vị trí tương ứng ở trẻ em mảng sử dụng tính toán như thế này. Chúng ta có thể sử dụng cho trẻ em lớn hơn mảng nếu chúng tôi muốn cung cấp cái nhìn lên của phím với một phạm vi rộng hơn của nhân vật, như toàn bộ Ký tự ASCII thiết lập. 

Trong trường hợp này, con trỏ ở trẻ em mảng của chúng tôi tại chỉ số một không phải là null. Vì vậy, chúng tôi sẽ tiếp tục tìm kiếm lên phòng tắm chính. Nếu chúng ta từng gặp phải một con trỏ null ở vị trí thích hợp ở trẻ em mảng trong khi chúng tôi đi qua các nút, sau đó chúng tôi sẽ phải nói rằng chúng ta có không thể tìm thấy bất cứ điều gì cho khóa đó. 

Bây giờ, chúng ta sẽ lấy lá thư thứ hai của chính của chúng tôi, A, và tiếp tục sau con trỏ theo cách này cho đến khi chúng tôi đến cuối quan trọng của chúng tôi. Nếu chúng ta đạt được kết thúc của khóa mà không đánh bất kỳ kết thúc chết, con trỏ null, như trường hợp ở đây, sau đó chúng tôi chỉ phải kiểm tra một điều nữa. Là chìa khóa này thực sự trong từ điển? 

Nếu như vậy, chúng ta nên tìm một giá trị, cũng một biểu tượng mặt cười trong sơ đồ của chúng tôi nơi từ kết thúc. Nếu có cái gì đó khác với lưu trữ dữ liệu, sau đó chúng tôi có thể trả lại. Ví dụ, sở thú quan trọng không phải là trong từ điển, mặc dù chúng ta có thể có đến cuối khóa này mà không bao giờ đánh một con trỏ null, trong khi chúng tôi lặp qua các Trie. 

Nếu chúng ta cố gắng tìm kiếm các phòng tắm khóa, thứ hai để chỉ số mảng nút cuối cùng của, tương ứng với chữ cái H, sẽ đã tổ chức một con trỏ null. Vì vậy, phòng tắm không có trong từ điển. Và do đó, một Trie độc ​​đáo ở chỗ các phím không bao giờ được lưu trữ một cách rõ ràng trong cấu trúc dữ liệu. Vì vậy, làm thế nào để chúng ta chèn một cái gì đó vào một Trie? 

Chúng ta hãy chèn phím sở thú vào Trie của chúng tôi. Hãy nhớ rằng một khuôn mặt cười tại một nút có thể tương ứng trong mã để đơn giản Giá trị boolean để chỉ ra rằng vườn thú có trong từ điển hoặc nó có thể tương ứng với thêm thông tin mà chúng tôi muốn liên kết với các sở thú chính, như định nghĩa của từ hay cái gì khác. Trong một số cách, quá trình này để chèn một cái gì đó vào một Trie tương tự như tìm kiếm một cái gì đó trong một Trie. 

Chúng tôi sẽ bắt đầu với nút gốc một lần nữa, con trỏ sau tương ứng với các chữ cái của chính chúng tôi. May mắn thay, chúng tôi có thể theo dõi con trỏ tất cả các cách cho đến khi chúng tôi đến cuối khóa. Từ sở thú là một tiền tố của từ zoom, mà là một thành viên của từ điển, chúng ta không cần phải phân bổ các nút mới. 

Chúng ta có thể sửa đổi các nút để chỉ ra rằng con đường của các nhân vật dẫn đến nó đại diện cho một chìa khóa trong từ điển của chúng tôi. Bây giờ, hãy thử chèn BATH chìa khóa vào Trie. Chúng tôi sẽ bắt đầu tại nút gốc và theo con trỏ một lần nữa. Nhưng trong tình huống này, chúng ta đánh một người chết kết thúc trước khi chúng tôi có thể đến được với các cuối khoá. Bây giờ, chúng tôi sẽ cần phải phân bổ một số mới các nút sẽ cần phải phân bổ một mới nút cho mỗi còn lại thư của chính chúng tôi. 

Trong trường hợp này, chúng ta chỉ cần để phân bổ một nút mới. Sau đó chúng tôi sẽ cần phải thực hiện các chỉ số H tham khảo nút mới này. Một lần nữa, chúng ta có thể sửa đổi các nút để chỉ ra rằng con đường của ký tự dẫn đến nó đại diện cho một quan trọng trong từ điển của chúng tôi. Chúng ta hãy suy luận về các tiệm cận phức tạp của thủ tục của chúng tôi cho các hai hoạt động. 

Chúng tôi nhận thấy rằng trong cả hai trường hợp số của các bước thuật toán của chúng tôi đã được tỷ lệ thuận với số lượng ký tự trong từ khóa. Đó là đúng. Khi bạn muốn tìm một từ trong một Trie bạn chỉ cần lặp qua các chữ cái một cho đến khi bạn có đến cuối của từ hoặc nhấn một kết thúc chết trong Trie. 

Và khi bạn muốn chèn một phím cặp giá trị vào một Trie sử dụng thủ tục, chúng tôi đã thảo luận, trường hợp xấu nhất sẽ có bạn bố trí một nút mới cho mỗi thư. Và chúng tôi sẽ giả định rằng phân bổ là một thời gian hoạt động liên tục. Vì vậy, nếu chúng ta giả định rằng chiều dài chính là bao quanh bởi một hằng số cố định, cả hai chèn và tìm kiếm là không đổi hoạt động thời gian cho một Trie. 

Nếu chúng ta không làm cho giả định này độ dài khoá được bao quanh bởi một cố định liên tục, sau đó chèn và nhìn lên, trong trường hợp xấu nhất, được tuyến tính trong độ dài của khoá. Nhận thấy rằng số lượng các mặt hàng được lưu trữ trong Trie không ảnh hưởng đến cái nhìn lên hoặc thời điểm chèn. Nó chỉ ảnh hưởng bởi độ dài của khoá. 

Ngược lại, thêm các mục vào, nói, một bảng băm có xu hướng làm tương lai nhìn lên chậm hơn. Trong khi điều này nghe có vẻ hấp dẫn lúc đầu, chúng ta nên ghi nhớ rằng một phức tạp tiệm cận thuận lợi không có nghĩa là trong thực tế dữ liệu cấu trúc nhất thiết phải ngoài sỉ nhục. Chúng ta cũng phải xem xét để lưu trữ một từ trong một Trie chúng ta cần, trong điều tồi tệ nhất trường hợp, một số nút tương ứng với chiều dài của từ chính nó. 

Cố gắng có xu hướng sử dụng rất nhiều không gian. Đó là trái ngược với một bảng băm, nơi chúng tôi chỉ cần một nút mới vào lưu trữ một số cặp giá trị quan trọng. Bây giờ, một lần nữa trong lý thuyết, không gian lớn tiêu thụ không có vẻ như một lớn đối phó, nhất là hiện đại máy tính có gigabyte và GB bộ nhớ. Nhưng nó quay ra rằng chúng ta vẫn còn phải lo lắng về việc sử dụng bộ nhớ và tổ chức vì lợi ích của hiệu suất, kể từ khi máy tính hiện đại có cơ chế tại chỗ dưới mui xe để tăng tốc độ truy cập bộ nhớ. 

Nhưng các cơ chế làm việc hiệu quả nhất khi truy cập bộ nhớ được thực hiện trong nhỏ gọn khu vực hoặc khu vực. Và các nút của một Trie có thể cư trú bất cứ nơi nào trong đống đó. Nhưng đây là những đánh đổi rằng chúng ta phải xem xét. 

Hãy nhớ rằng, khi lựa chọn một dữ liệu cấu trúc cho một công việc nào đó, chúng tôi nên suy nghĩ về những gì các loại hoạt động của cấu trúc dữ liệu cần hỗ trợ và bao nhiêu hiệu suất của mỗi người hoạt động các vấn đề với chúng tôi. Các hoạt động này thậm chí có thể mở rộng ra ngoài chỉ cơ bản nhìn lên và chèn. Giả sử chúng ta muốn thực hiện một loại chức năng tự động hoàn tất, nhiều như công cụ tìm kiếm Google. Có nghĩa là, trả lại tất cả các phím và có khả năng giá trị mà có một tiền tố nhất định. 

Một Trie là duy nhất hữu ích cho hoạt động này. Nó đơn giản để lặp qua các Trie cho mỗi nhân vật của tiền tố. Cũng giống như một cái nhìn lên hoạt động, chúng ta có thể theo con trỏ nhân vật của nhân vật. Sau đó, khi chúng tôi đến cuối tiền tố, chúng ta có thể lặp qua phần còn lại của cấu trúc dữ liệu từ bất kỳ của các phím ngoài thời điểm này có tiền tố. 

Nó cũng dễ dàng để có được bảng liệt kê này trong thứ tự chữ cái từ các yếu tố của mảng trẻ em được sắp xếp theo thứ tự abc. Vì vậy, hy vọng bạn sẽ xem xét hiến cố gắng thử. Tôi Kevin Schmid, và đây là CS50. 

Ah, đây là sự khởi đầu của sự suy giảm. Tôi xin lỗi. Xin lôi. Xin lôi. Xin lôi. 

Tấn công bốn. Tôi ra. Xin lôi. Xin lôi. Xin lôi. Xin lỗi vì làm cho người người có chỉnh sửa này điên. 

Xin lôi. Xin lôi. Xin lôi. Xin lôi. 

SPEAKER 1: Tốt lắm. Đã được thực sự thực hiện tốt.