[Powered by Google Translate] [Binary Search] [Patrick Schmid - Đại học Harvard] [Đây là CS50. - CS50.TV] 

Nếu tôi đưa cho bạn một danh sách các tên nhân vật Disney trong thứ tự chữ cái và yêu cầu bạn tìm Mickey Mouse, làm thế nào bạn sẽ đi về việc này? Một cách rõ ràng sẽ được để quét các danh sách từ đầu và kiểm tra tất cả các tên để xem nếu nó là Mickey. Nhưng khi bạn đọc Aladdin, Alice, Ariel, và vv, bạn sẽ nhanh chóng nhận ra rằng bắt đầu ở phía trước của danh sách không phải là một ý tưởng tốt. Rồi, có lẽ bạn nên bắt đầu làm việc ngược trở lại từ cuối danh sách. Bây giờ bạn đọc Tarzan, Stitch, Snow White, và vv. Tuy nhiên, điều này không có vẻ như là cách tốt nhất để đi về nó. 

Vâng, một cách khác mà bạn có thể đi về việc này là cố gắng để thu hẹp danh sách các tên mà bạn phải nhìn vào. Vì bạn biết rằng họ đang có trong thứ tự chữ cái, bạn chỉ có thể nhìn vào những cái tên ở giữa của danh sách và kiểm tra xem Mickey Mouse là trước hoặc sau khi tên này. Nhìn vào tên cuối cùng trong cột thứ hai bạn sẽ nhận ra rằng M cho Mickey đến sau khi J cho Jasmine, vì vậy bạn chỉ đơn giản là muốn bỏ qua nửa đầu của danh sách. Sau đó, bạn có thể muốn nhìn vào phía trên cùng của cột cuối cùng và thấy rằng nó bắt đầu với Rapunzel. Mickey đến trước khi Rapunzel, trông giống như chúng ta có thể bỏ qua cột cuối cùng. Tiếp tục chiến lược tìm kiếm, bạn sẽ nhanh chóng thấy rằng Mickey trong nửa đầu của danh sách còn lại của tên và cuối cùng đã tìm thấy Mickey ẩn giữa Merlin và Minnie. 

Những gì bạn chỉ cần làm là về cơ bản tìm kiếm nhị phân. Như tên gọi này hàm ý, nó thực hiện chiến lược tìm kiếm của mình trong một vấn đề nhị phân. Điều này có nghĩa là gì? Vâng, đưa ra một danh sách các mục được sắp xếp, các thuật toán tìm kiếm nhị phân làm cho một quyết định nhị phân - trái hoặc phải, lớn hơn hoặc ít hơn, theo thứ tự bảng chữ cái trước hoặc sau khi tại mỗi điểm. Bây giờ chúng ta có một cái tên mà đi cùng với thuật toán tìm kiếm này, chúng ta hãy nhìn vào một ví dụ khác, nhưng lần này với một danh sách các số được sắp xếp. Nói rằng chúng tôi đang tìm kiếm cho số 144 trong danh sách các số được sắp xếp. Giống như trước đây, chúng ta thấy số đó là ở giữa - trong trường hợp này là 13 - và xem nếu 144 là lớn hơn hoặc nhỏ hơn 13. Kể từ khi nó rõ ràng là lớn hơn 13, chúng ta có thể bỏ qua tất cả mọi thứ đó là 13 hoặc ít hơn và chỉ tập trung vào một nửa còn lại. Kể từ bây giờ chúng ta có một số chẵn các mục còn lại, chúng tôi chỉ đơn giản là lựa chọn một số đó là gần giữa. Trong trường hợp này, chúng tôi chọn 55. Chúng tôi có thể chỉ là một cách dễ dàng lựa chọn 89. Okay. Một lần nữa, 144 là lớn hơn 55, do đó, chúng tôi đi đến bên phải. May mắn cho chúng tôi, số lượng trung tiếp theo là 144, chúng ta đang tìm kiếm. Vì vậy, để tìm 144 bằng cách sử dụng tìm kiếm nhị phân, chúng tôi có thể tìm thấy nó trong chỉ có 3 bước. Nếu chúng tôi đã sử dụng tìm kiếm tuyến tính ở đây, nó sẽ đưa chúng ta 12 bước. Như một vấn đề của thực tế, kể từ khi phương pháp tìm kiếm nửa số lượng các mục nó có để xem xét tại mỗi bước, nó sẽ tìm thấy mục tìm kiếm trong nhật ký của số lượng các mục trong danh sách. Bây giờ chúng ta đã nhìn thấy 2 ví dụ, chúng ta hãy xem xét một số giả cho một hàm đệ quy mà thực hiện tìm kiếm nhị phân. Bắt đầu từ trên, chúng ta thấy rằng chúng ta phải tìm một chức năng mà mất 4 đối số: chìa khóa, mảng, min và max. Điều quan trọng là số lượng mà chúng tôi đang tìm kiếm, vì vậy 144 trong ví dụ trước. Array là danh sách các số mà chúng tôi đang tìm kiếm. Min và max là các chỉ số của các vị trí tối thiểu và tối đa mà chúng tôi đang xem xét. Vì vậy, khi chúng tôi bắt đầu, min sẽ là số không và tối đa sẽ là chỉ số tối đa của mảng. Như chúng ta đã thu hẹp tìm kiếm, chúng tôi sẽ cập nhật min và max là phạm vi mà chúng tôi vẫn đang tìm kiếm. 

Hãy bỏ qua phần thú vị đầu tiên. Điều đầu tiên chúng tôi làm là tìm ra điểm giữa, chỉ số nằm giữa min và max của mảng mà chúng tôi vẫn đang xem xét. Sau đó, chúng ta nhìn vào giá trị của mảng tại vị trí đó trung điểm và xem nếu số lượng mà chúng ta đang tìm kiếm là quan trọng mà. Nếu số ở vị trí đó là ít hơn, sau đó nó có nghĩa chính là lớn hơn so với tất cả các số bên trái của vị trí đó. Vì vậy, chúng ta có thể gọi chức năng tìm kiếm nhị phân một lần nữa, nhưng lần này cập nhật các thông số min và max để đọc nửa đó là lớn hơn hoặc bằng giá trị mà chúng ta chỉ cần nhìn vào. Mặt khác, nếu chính là ít hơn so với số lượng tại trung điểm hiện tại của mảng, chúng tôi muốn đi bên trái và bỏ qua tất cả các số lớn. Một lần nữa, chúng ta gọi là tìm kiếm nhị phân, nhưng thời gian này với phạm vi của các min và max cập nhật bao gồm chỉ thấp hơn một nửa. Nếu giá trị tại trung điểm hiện tại trong mảng không phải là lớn hơn cũng không nhỏ hơn khoá, sau đó nó phải có bằng chìa khóa. Vì vậy, chúng tôi chỉ đơn giản là có thể quay trở lại các chỉ số trung điểm hiện tại, và chúng tôi đang thực hiện. Cuối cùng, việc kiểm tra này ở đây là đối với trường hợp số lượng không phải là thực sự trong mảng các số chúng tôi đang tìm kiếm. Nếu chỉ số tối đa của phạm vi mà chúng tôi đang tìm kiếm bao giờ ít hơn mức tối thiểu, có nghĩa là chúng ta đã đi quá xa. Kể từ khi con số này là không có trong mảng đầu vào, chúng tôi trở về -1 để cho biết rằng không có gì đã được tìm thấy. 

Bạn có thể đã nhận thấy rằng thuật toán này để làm việc, danh sách các số đã được sắp xếp. Nói cách khác, chúng ta chỉ có thể tìm thấy 144 bằng cách sử dụng tìm kiếm nhị phân nếu tất cả các số được sắp xếp từ thấp nhất đến cao nhất. Nếu đây không phải là trường hợp, chúng tôi sẽ không thể loại trừ một nửa của con số ở mỗi bước. Vì vậy, chúng tôi có 2 lựa chọn. Hoặc là chúng ta có thể có một danh sách được phân loại và sắp xếp nó trước khi sử dụng tìm kiếm nhị phân, hoặc chúng tôi có thể chắc chắn rằng danh sách các số được sắp xếp như chúng ta thêm số vào nó. Như vậy, thay vì sắp xếp chỉ khi chúng ta phải tìm kiếm, tại sao không giữ danh sách được sắp xếp ở tất cả các lần? 

Một cách để giữ một danh sách các số được sắp xếp trong khi đồng thời cho phép một để thêm hoặc di chuyển số từ danh sách này là bằng cách sử dụng một cái gì đó gọi là cây tìm kiếm nhị phân. Một cây tìm kiếm nhị phân là một cấu trúc dữ liệu có 3 thuộc tính. Trước tiên, các cây con trái của nút bất kỳ chỉ chứa các giá trị nhỏ hơn hoặc bằng giá trị của nút. Thứ hai, bên phải cây con của một node chỉ chứa các giá trị lớn hơn hoặc bằng giá trị của nút. Và, cuối cùng, cả hai bên trái và phải subtrees của tất cả các nút cũng là cây tìm kiếm nhị phân. Hãy xem một ví dụ có cùng số chúng tôi đã sử dụng trước đó. Đối với những người bạn của những người chưa bao giờ thấy một cây trước khi khoa học máy tính, hãy để tôi bắt đầu bằng cách nói với bạn rằng một cây khoa học máy tính phát triển xuống dưới. Có, không giống như cây bạn đã quen với, gốc rễ của một cây khoa học máy tính ở đầu trang, và lá ở phía dưới. Mỗi hộp nhỏ được gọi là một nút, và các nút được kết nối với nhau bởi các cạnh. Vì vậy, các thư mục gốc của cây này là một giá trị nút với giá trị 13, trong đó có 2 trẻ em các nút với các giá trị 5 và 34. Cây con là cây được hình thành chỉ bằng cách nhìn vào một tiểu mục của toàn bộ cây. 

Ví dụ, cây con trái của nút 3 là cây được tạo ra bởi các nút 0, 1, và 2. Vì vậy, nếu chúng ta quay trở lại các thuộc tính của một cây tìm kiếm nhị phân, chúng ta thấy rằng mỗi nút trong cây phù hợp với tất cả 3 thuộc tính, cụ thể là, cây con trái chỉ chứa các giá trị nhỏ hơn hoặc bằng giá trị của nút; bên phải cây con của tất cả các nút chỉ chứa các giá trị lớn hơn hoặc bằng giá trị của nút; subtrees trái và phải của tất cả các nút cũng là cây tìm kiếm nhị phân. Mặc dù cây này có vẻ khác nhau, đây là một cây nhị phân tìm kiếm hợp lệ cho cùng một tập hợp số. Như một vấn đề của thực tế, có rất nhiều cách có thể là bạn có thể tạo một cây nhị phân tìm kiếm hợp lệ từ những con số này. Vâng, chúng ta hãy quay trở lại với một trong những đầu tiên chúng tôi tạo ra. Vì vậy, những gì chúng ta có thể làm gì với những cây này? Vâng, chúng tôi rất đơn giản có thể tìm thấy những giá trị tối thiểu và tối đa. Các giá trị tối thiểu có thể được tìm thấy bằng cách luôn luôn đi bên trái cho đến khi có các nút không đến thăm. Ngược lại, để tìm ra một tối đa chỉ đơn giản chỉ đi xuống bên phải trong từng thời điểm. 

Tìm kiếm bất kỳ số nào khác mà không phải là tối thiểu hoặc tối đa chỉ là dễ dàng. Nói rằng chúng tôi đang tìm kiếm cho số 89. Chúng tôi chỉ đơn giản là kiểm tra giá trị của mỗi nút và đi sang trái hoặc phải, tuỳ thuộc vào việc giá trị của nút nhỏ hơn hoặc lớn hơn chúng ta đang tìm kiếm. Vì vậy, bắt đầu từ thư mục gốc của 13, chúng ta thấy rằng 89 là lớn hơn, và do đó, chúng tôi đi về bên phải. Sau đó, chúng ta thấy nút cho 34, và một lần nữa chúng tôi đi đến bên phải. 89 vẫn còn lớn hơn 55, vì vậy chúng tôi tiếp tục đi về bên phải. Sau đó chúng tôi đi lên với một nút với giá trị trên 144 và đi bên trái. Nhìn kìa, 89 là phải có. 

Một điều mà chúng ta có thể làm là in ra tất cả các số bằng cách thực hiện một traversal inorder. An inorder traversal có nghĩa là để in ra tất cả mọi thứ trong cây con trái tiếp theo là in ấn các nút đó và sau đó theo sau bằng cách in ra tất cả mọi thứ ở bên phải cây con. Ví dụ, chúng ta hãy lấy cây nhị phân tìm kiếm của chúng tôi yêu thích và in ra các con số theo thứ tự sắp xếp. Chúng tôi bắt đầu từ thư mục gốc của 13, nhưng trước khi in 13 chúng tôi phải in ra tất cả mọi thứ trong cây con trái. Vì vậy, chúng tôi đi đến 5. Chúng tôi vẫn phải đi sâu hơn xuống trong cây cho đến khi chúng tôi tìm thấy các nút trái nhất, đó là số không. Sau khi in không, chúng tôi trở lại lên đến số 1 và in mà ra. Sau đó, chúng tôi đi đến cây con phải, đó là 2, và in mà ra. Bây giờ chúng ta đang thực hiện với cây con, chúng ta có thể trở lại lên đến 3 và in ra. Tiếp tục trở lại, chúng tôi in 5 và sau đó là 8. Bây giờ chúng ta đã hoàn thành toàn bộ trái cây con, chúng ta có thể in ra 13 và bắt đầu làm việc trên bên phải cây con. Chúng tôi nhảy xuống đến 34, nhưng trước khi in 34 chúng tôi phải in ra cây con trái của nó. Vì vậy, chúng tôi in ra 21; sau đó chúng tôi nhận được để in ra 34 và truy cập quyền của mình cây con. Kể từ khi 55 không có cây con bên trái, chúng tôi in nó ra và tiếp tục sang phải cây con của nó. 144 có một cây con bên trái, và vì vậy chúng tôi in ra 89, tiếp theo là các 144, và cuối cùng là nút phải nhất trong tổng số 233. Có bạn có nó, tất cả các con số được in ra theo thứ tự từ thấp nhất đến cao nhất. 

Thêm một cái gì đó để cây là tương đối không đau là tốt. Tất cả chúng ta phải làm là đảm bảo rằng chúng tôi theo 3 thuộc tính cây tìm kiếm nhị phân và sau đó chèn giá trị nơi có không gian. Hãy nói rằng chúng tôi muốn chèn giá trị của 7. Vì 7 nhỏ hơn 13, chúng tôi đi về bên trái. Nhưng nó lớn hơn 5, vì vậy chúng tôi đi qua bên phải. Kể từ khi nó ít hơn 8 và 8 là một nút lá, chúng tôi thêm 7 con trái của 8. Thì đấy! Chúng tôi đã thêm một số cây tìm kiếm nhị phân của chúng tôi. 

Nếu chúng ta có thể thêm những điều, chúng ta tốt hơn có thể xóa những thứ như là tốt. Thật không may cho chúng ta, xóa là một ít phức tạp hơn không nhiều, nhưng chỉ cần một chút ít. Có 3 kịch bản khác nhau mà chúng ta phải xem xét khi xóa các yếu tố từ cây tìm kiếm nhị phân. Đầu tiên, trường hợp đơn giản nhất là phần tử là một nút lá. Trong trường hợp này, chúng tôi chỉ đơn giản là xóa nó và đi về với kinh doanh của chúng tôi. Nói rằng chúng tôi muốn xóa 7 mà chúng ta chỉ cần thêm. Vâng, chúng tôi chỉ đơn giản là tìm thấy nó, loại bỏ nó, và đó là nó. Các trường hợp tiếp theo là nếu nút chỉ có 1 trẻ em. Ở đây chúng ta có thể xóa các nút, nhưng trước tiên chúng ta phải chắc chắn để kết nối các cây con mà bây giờ còn lại parentless phụ huynh của các nút, chúng tôi chỉ cần xóa. Nói rằng chúng tôi muốn xóa 3 từ cây của chúng tôi. Chúng tôi có các phần tử con của nút đó và đính kèm nó cho phụ huynh của các nút. Trong trường hợp này, chúng ta đang gắn 1 đến 5. Điều này làm việc mà không có một vấn đề bởi vì chúng ta biết, theo tài sản cây tìm kiếm nhị phân, rằng tất cả mọi thứ trong cây con bên trái trong 3 là nhỏ hơn 5. Bây giờ 3 của cây con được đưa về chăm sóc, chúng ta có thể xóa nó. Trường hợp thứ ba và cuối cùng là phức tạp nhất. Đây là trường hợp khi các nút chúng tôi muốn xóa có 2 trẻ em. Để làm điều này, đầu tiên chúng ta phải tìm các nút có giá trị lớn nhất tiếp theo, trao đổi hai, và sau đó xóa các nút trong câu hỏi. Chú ý nút có giá trị lớn nhất tiếp theo không thể có 2 con riêng của mình kể từ khi con trái của nó sẽ là một ứng cử viên tốt hơn cho lớn nhất tiếp theo. Vì vậy, việc xóa một nút với 2 trẻ em số tiền để trao đổi 2 nút, và sau đó xóa được xử lý bởi 1 của 2 quy tắc nói trên. Ví dụ, chúng ta hãy nói rằng chúng tôi muốn xóa nút gốc, 13. Điều đầu tiên chúng tôi làm là chúng ta tìm thấy những giá trị lớn nhất trong cây trong đó, trong trường hợp này, là 21. Chúng tôi sau đó trao đổi 2 nút, làm cho 13 một chiếc lá và 21 nút nhóm trung tâm. Bây giờ chúng tôi chỉ đơn giản là có thể xóa 13. 

Như ám chỉ trước đó, có rất nhiều cách có thể làm cho một cây nhị phân tìm kiếm hợp lệ. Thật không may cho chúng ta, một số tồi tệ hơn so với những người khác. Ví dụ, những gì xảy ra khi chúng ta xây dựng một cây tìm kiếm nhị phân từ một danh sách sắp xếp các con số? Tất cả số chỉ cần thêm vào bên phải trong mỗi bước. Khi chúng tôi muốn tìm kiếm một số, chúng tôi không có sự lựa chọn, nhưng chỉ cần nhìn vào bên phải ở mỗi bước. Đây không phải là tốt hơn so với tìm kiếm tuyến tính ở tất cả. Mặc dù chúng tôi không đề cập tới chúng ở đây, có khác, phức tạp hơn, cấu trúc dữ liệu mà làm cho chắc chắn rằng điều này không xảy ra. Tuy nhiên, một đơn giản, điều mà có thể được thực hiện để tránh điều này là để shuffle ngẫu nhiên chỉ là các giá trị đầu vào. Đó là không cao mà bởi cơ hội ngẫu nhiên một danh sách xáo trộn các con số được sắp xếp. Nếu đây là trường hợp, sòng bạc sẽ không tiếp tục kinh doanh cho lâu dài. 

Có bạn có nó. Bây giờ bạn biết về tìm kiếm nhị phân và cây tìm kiếm nhị phân. Tôi là Patrick Schmid, và đây là CS50. [CS50.TV] Một cách rõ ràng sẽ được để quét các danh sách từ ... [beep] ... Số lượng mặt hàng ... yep [Cười] ... Gửi nút ... 234 augh. >> Yay! Đó là