[Powered by Google Translate] Làm thế nào bạn sẽ đại diện cho tất cả các thành viên trong gia đình của bạn trong một máy tính?
Chúng tôi chỉ đơn giản là có thể sử dụng một danh sách,
nhưng có một hệ thống phân cấp rõ ràng ở đây.
>> Hãy nói rằng chúng tôi đang bắt đầu với bà ngoại tuyệt vời của bạn, Alice.
Cô có 2 con trai, Bob
và ông nội của bạn, Charlie.
Charlie có 3 con,
chú của bạn, Dave, cô, dì, Eve, và cha của bạn, Fred.
Bạn là đứa con duy nhất của Fred.
>> Tại sao tổ chức thành viên trong gia đình của bạn theo cách này
là tốt hơn so với các đại diện danh sách đơn giản?
Một lý do là cấu trúc phân cấp này,
được gọi là một 'cây' chứa nhiều thông tin hơn một danh sách đơn giản.
Chúng tôi biết các mối quan hệ gia đình giữa tất cả mọi người
chỉ bằng cách kiểm tra các cây.
Ngoài ra, nó có thể tăng tốc độ
thời gian nhìn lên rất nhiều, nếu dữ liệu cây được sắp xếp.
>> Chúng ta không thể tận dụng lợi thế của điều đó ở đây, nhưng chúng tôi sẽ sớm nhìn thấy một ví dụ về điều này.
Mỗi người được đại diện bởi một nút trên cây.
Nút có thể có các nút con
cũng như một nút cha.
Đây là những thuật ngữ kỹ thuật,
ngay cả khi sử dụng cây cho những thứ bên cạnh gia đình.
Alice của nút có 2 trẻ em và không có cha mẹ,
trong khi Charlie nút có 3 trẻ em và cha mẹ 1.
>> Một nút lá là một trong những mà không có bất kỳ trẻ em
trên các cạnh bên ngoài của cây.
Các nút trên cùng của cây, nút gốc,
có không có cha mẹ.
>> Một cây nhị phân là một loại hình cụ thể của cây,
trong đó, nhiều nhất, mỗi node có 2 trẻ em.
Dưới đây là cấu trúc của một nút của một cây nhị phân trong C.
Mỗi nút có một số dữ liệu liên kết với nó
và 2 con trỏ đến các nút khác.
>> Trong cây gia đình của chúng tôi,
các dữ liệu liên kết là tên của mỗi người.
Ở đây nó là một int, mặc dù nó có thể là bất cứ điều gì.
Khi nó quay ra,
một cây nhị phân sẽ không được một đại diện tốt cho một gia đình,
bởi vì người ta thường có nhiều hơn 2 trẻ em.
>> Một cây nhị phân tìm kiếm
là một loại lệnh đặc biệt của cây nhị phân
cho phép chúng ta tìm một giá trị một cách nhanh chóng.
Bạn có thể nhận thấy
rằng tất cả các nút dưới gốc cây
là gốc rễ của cây khác, được gọi là "cây con".
Ở đây, gốc rễ của cây là 6,
và con của nó, 2, là gốc rễ của một cây con.
>> Trong một cây tìm kiếm nhị phân
tất cả các giá trị của một nút bên phải subtree
lớn hơn giá trị của nút. Ở đây: 6.
Vâng, các giá trị trong trái cây con của một nút
ít hơn giá trị của nút.
Nếu chúng ta cần phải xử lý các giá trị nhân bản,
chúng ta có thể thay đổi một trong những người đến sự bất bình đẳng lỏng lẻo,
có nghĩa là giá trị giống nhau có thể rơi hoặc bên trái hoặc phải,
miễn là chúng ta nhất quán về nó trong suốt.
Cây này là một cây tìm kiếm nhị phân
bởi vì nó theo các quy tắc này.
>> Đây là cách nó sẽ xem xét nếu chúng tôi quay tất cả các nút vào cấu trúc của C.
Chú ý rằng nếu một đứa trẻ bị mất tích,
con trỏ là null.
Làm thế nào để chúng tôi kiểm tra xem nếu 7 là trong cây?
Chúng tôi bắt đầu ở gốc.
Bảy là lớn hơn 6, vì vậy nếu nó trong cây, nó phải là bên phải.
Sau đó, nó ít hơn 8, vì vậy nó phải được để lại.
Ở đây, chúng tôi đã tìm thấy 7.
Bây giờ, chúng tôi sẽ kiểm tra 5.
Năm là ít hơn 6, vì vậy nó phải được bên trái.
Năm là lớn hơn 2,
vì vậy nó phải được quyền,
và nó cũng là lớn hơn 4, vì vậy nó phải được đúng một lần nữa.
Tuy nhiên, có không có trẻ em nào ở đây.
Con trỏ là null.
Điều này có nghĩa là 5 không phải là cây của chúng tôi.
>> Chúng ta có thể tìm kiếm cây nhị phân với mã sau đây:
Tại mỗi nút, chúng ta kiểm tra xem liệu chúng ta đã tìm thấy
giá trị chúng tôi đang tìm kiếm.
Nếu chúng ta không tìm thấy nó, chúng tôi xác định nếu nó phải là
trên và sang trái hoặc phải kiểm tra xem cây con.
Vòng lặp này sẽ tiếp tục xuống cây
cho đến khi không có nút con ở hai bên trái hoặc phải.
>> Hãy nhớ rằng 5 trong cây.
Làm thế nào để chúng ta chèn nó?
Quá trình này trông giống như để tìm kiếm.
Chúng tôi lặp xuống cây bắt đầu từ 6,
trái đến 2,
quyền 4,
và phải một lần nữa, nhưng 4 không có con bên này.
Đây sẽ là vị trí mới cho 5,
và nó sẽ bắt đầu không có con.
>> Nhanh như thế nào là hoạt động trên một cây tìm kiếm nhị phân?
Hãy nhớ rằng Bigohnotation tìm cách cung cấp một trên ràng buộc.
Trong trường hợp xấu nhất,
cây của chúng tôi chỉ đơn giản là có thể là một danh sách liên kết
có nghĩa là chèn, xóa, và tìm kiếm
có thể mất thời gian tỷ lệ thuận với số lượng các nút trong cây.
Đây là O (n).
>> Ví dụ, sau đây là một cây nhị phân tìm kiếm hợp lệ.
Tuy nhiên, nếu chúng ta cố gắng để tìm 9,
chúng ta phải đi qua tất cả các nút.
Nó không phải là tốt hơn so với một danh sách liên kết.
Lý tưởng nhất, chúng tôi muốn tất cả các nút
của cây tìm kiếm nhị phân của chúng tôi có 2 con.
Bằng cách này, chèn, xóa và tìm kiếm
sẽ mất, lúc tồi tệ nhất, O (log n) thời gian.
Cây từ trước khi có thể được cân bằng hơn,
như thế này.
Bây giờ, nhìn lên bất kỳ giá trị nào có, nhiều nhất là 3 bước.
Cây này là cân bằng,
có nghĩa là có độ sâu tối thiểu
liên quan đến số lượng các nút.
>> Tìm kiếm một giá trị trong một cây tìm kiếm nhị phân cân bằng
tương tự như tìm kiếm nhị phân trên một mảng được sắp xếp.
Trong thực tế, nếu chúng ta không cần để chèn hoặc xóa các mục,
họ cư xử chính xác theo cùng một cách.
Tuy nhiên, một cấu trúc cây là tốt hơn
cho thêm vào xử lý và xóa bỏ
>> Tên tôi là Bannus Van der Kloot.
Đây là CS50.