Cây, cây đỏ đen

"Chào, Amigo!"

"Xin chào, Rishi!"

"Tôi đã tìm thấy những ghi chú cũ của mình ở đó và chuẩn bị một số tài liệu thú vị cho bạn. Tôi nghĩ bạn sẽ thích thú khi nghe nó."

"Hãy nghe nó. Bạn luôn tìm thấy một cái gì đó thú vị mà sau này chứng minh là rất hữu ích."

"OK. Hôm nay tôi muốn nói với các bạn về cây cối , vì vậy tôi sẽ bắt đầu bằng đồ thị ."

" Đồ thị là một hệ thống các điểm và đường nối chúng. Các điểm được gọi là đỉnh của đồ thị và các đường được gọi là các cạnh của đồ thị. Ví dụ:"

"Một biểu đồ rất thuận tiện để sử dụng làm mô hình toán học cho các quy trình và nhiệm vụ khác nhau trong thế giới thực. Nhiều nhiệm vụ và thuật toán khác nhau đã được phát minh cho biểu đồ, vì vậy chúng được sử dụng khá thường xuyên."

"Ví dụ: giả sử các đỉnh là các thành phố và các cạnh là các con đường. Sau đó, việc tìm kiếm con đường ngắn nhất giữa các thành phố trở thành: «cho một biểu đồ, tìm đường đi ngắn nhất giữa hai đỉnh». "

"Nhưng đường dẫn từ A đến B không phải lúc nào cũng giống như đường dẫn từ B đến A. Vì vậy, đôi khi có hai đường khác nhau được ưu tiên hơn. Để làm điều này, các đường (cạnh của biểu đồ) được thay thế bằng các mũi tên. Trong nói cách khác, đồ thị có thể có hai mũi tên: một từ A đến B, và một từ B đến A."

"Nếu đồ thị sử dụng các mũi tên, thì nó được gọi là đồ thị có hướng ; nếu nó chỉ có các đường, thì nó được gọi là đồ thị vô hướng ."

"Mỗi đỉnh có thể có số cạnh riêng của nó. Một đỉnh cũng có thể không có cạnh nào cả. Ngược lại, một đỉnh có thể được kết nối bởi các cạnh với mọi đỉnh khác.  Nếu mỗi cặp đỉnh trong đồ thị được kết nối bởi một cạnh, thì nó được gọi là một đồ thị đầy đủ. "

"Nếu bạn có thể sử dụng các cạnh để đi tới mọi đỉnh trong một đồ thị, thì nó được gọi là đồ thị liên thông . Một đồ thị có ba đỉnh riêng biệt và không có cạnh nào vẫn là đồ thị, nhưng chúng ta gọi nó là đồ thị không kết nối ."

"Để tạo thành một đồ thị liên thông từ N đỉnh, bạn cần ít nhất N-1 cạnh. Loại đồ thị này được gọi là cây."

"Hơn nữa, thông thường một đỉnh được chọn làm gốc của cây và phần còn lại được khai báo là các nhánh. Các nhánh cây không có nhánh riêng được gọi là lá . Ví dụ:"

"Nếu mỗi phần tử của cây có hai con, thì nó được gọi là cây nhị phân . Nói cách khác, có thể có 0 hoặc 2 nhánh. Bạn có thể thấy cây nhị phân ở phía trên bên phải."

" Một cây được gọi là cây nhị phân đầy đủ khi mỗi nhánh có 2 con và tất cả các lá (đỉnh không có con) nằm trên cùng một hàng."

"Ví dụ:"

"Tại sao những cây này cần thiết?"

"Ồ, cây được sử dụng ở rất nhiều nơi. Nói chung, cây nhị phân là dữ liệu có cấu trúc được sắp xếp."

"Đó là cái gì?"

"Vâng, rất đơn giản. Chúng tôi lưu trữ một giá trị nhất định trong mỗi đỉnh. Và mỗi phần tử tuân theo một quy tắc: giá trị được lưu trữ trong phần tử con bên phải phải lớn hơn giá trị được lưu trữ trong phần tử con bên trái và giá trị được lưu trữ trong phần tử con bên trái phải lớn hơn giá trị được lưu trữ trong phần tử con bên trái. nhỏ hơn giá trị được lưu trữ trong đỉnh.  Thứ tự này giúp bạn có thể nhanh chóng tìm thấy các phần tử của cây mà bạn cần."

"Bạn có thể làm rõ điều đó có nghĩa là gì?"

"Các phần tử của cây thường được sắp xếp bằng cách cộng. Giả sử chúng ta có 7 phần tử: 13, 5, 4, 16, 8, 11, 10"

"Đây là cách các phần tử được thêm vào cây."

"Nếu chúng ta đang tìm kiếm số 7 trong cái cây này, thì đây là cách tìm kiếm sẽ diễn ra"

"0) Bắt đầu từ gốc."

"1a) 7 có bằng 13 không? Không"

"1b) 7 có lớn hơn 13 không? Không, vì vậy chúng tôi chuyển sang cây con bên trái."

"2a) 7 có bằng 5 không? Không."

"2b) 7 có lớn hơn 5 không? Vâng, vì vậy chúng ta chuyển sang cây con bên phải."

"3a) 7 có bằng 8 không? Không"

"3b) 7 có lớn hơn 8 không? Không, vì vậy chúng tôi chuyển sang cây con bên trái."

"4a) Không có cây con bên trái, có nghĩa là số 7 không có trong cây."

"À. Nói cách khác, chúng ta chỉ cần kiểm tra các đỉnh trên đường đi từ gốc đến vị trí có thể là của số mong muốn. Ừ, nhanh thật đấy."

"Hơn nữa, nếu cây cân bằng, thì bạn chỉ cần đi qua khoảng 20 đỉnh để tìm kiếm một triệu phần tử."

"Tôi đồng ý - đó không phải là rất nhiều."

"Bạn có ý nghĩa gì bởi cây cân bằng?"

"Một cái cây không bị méo mó, tức là không có cành dài. Ví dụ, nếu các yếu tố đã được sắp xếp sẵn khi chúng ta dựng cây, thì chúng ta sẽ tạo ra một cây rất dài gồm một cành. "

"Hừm. Anh nói đúng. Vậy chúng ta phải làm gì?"

"Như bạn có thể đã đoán, cây hiệu quả nhất có các nhánh có chiều dài xấp xỉ nhau. Sau đó, mỗi phép so sánh sẽ loại bỏ phần lớn nhất của cây con còn lại."

"Vì vậy, chúng ta cần phải xây dựng lại cái cây?"

"Đúng vậy. Nó cần phải «cân bằng» — để được tạo ra càng gần càng tốt với một cây nhị phân hoàn chỉnh."

"Để giải quyết vấn đề này, người ta đã phát minh ra cây tự cân bằng.  Nếu cây trở nên méo mó sau khi thêm một phần tử, thì nó sẽ sắp xếp lại thứ tự các phần tử một chút để mọi thứ ổn thỏa.  Đây là một ví dụ về sự cân bằng:"

"Một số cây này được gọi là cây đỏ đen ."

"Tại sao chúng được gọi là đỏ-đen?"

"Nhà phát minh của họ đã vẽ tất cả các đỉnh bằng hai màu. Một màu đỏ và màu kia màu đen. Các đỉnh khác nhau tuân theo các quy tắc khác nhau. Điều này tạo thành toàn bộ cơ sở cho quy trình cân bằng."

"Ví dụ:"

"Vậy những quy tắc này là gì?"

"1) Một đỉnh màu đỏ không thể là con của một đỉnh màu đỏ."

"2) Độ sâu màu đen của mỗi lá là như nhau (độ sâu màu đen là số lượng đỉnh màu đen trên đường dẫn từ gốc)."

"3) Gốc cây màu đen."

"Tôi sẽ không giải thích cách thức hoạt động của nó - đầu của bạn có lẽ đã nổ tung."

"Vâng. Bộ xử lý của tôi tỏa ra một ít khói."

"Đây là một liên kết dành cho bạn. Nếu muốn, bạn có thể đọc thêm về nó ở đây."

Liên kết đến tài liệu bổ sung

"Còn bây giờ, đi nghỉ đi."