Api tìm kiếm nhị phân python
Trong hướng dẫn này, chúng tôi sẽ giới thiệu Cây AVL và chúng tôi sẽ xem xét các thuật toán để chèn, xóa và tìm kiếm các giá trị Show 2. Cây AVL là gì?Cây AVL, được đặt theo tên của các nhà phát minh Adelson-Velsky và Landis, là một cây tìm kiếm nhị phân tự cân bằng (BST) Cây tự cân bằng là cây tìm kiếm nhị phân cân bằng chiều cao sau khi chèn và xóa theo một số quy tắc cân bằng Độ phức tạp thời gian trong trường hợp xấu nhất của BST là một hàm của chiều cao của cây. Cụ thể, đường đi dài nhất từ gốc của cây đến một nút. Đối với BST có N nút, giả sử rằng mỗi nút chỉ có 0 hoặc một nút con. Do đó, chiều cao của nó bằng N và thời gian tìm kiếm trong trường hợp xấu nhất là O(N). Vì vậy, mục tiêu chính của chúng tôi trong BST là giữ chiều cao tối đa gần với log(N) Hệ số cân bằng của nút N là chiều cao(phải(AND)) – chiều cao(trái(N)). Trong Cây AVL, hệ số cân bằng của nút chỉ có thể là một trong các giá trị 1, 0 hoặc -1 Hãy xác định một đối tượng Node cho cây của chúng ta
Tiếp theo, hãy xác định AVLTree
3. Làm thế nào để cân bằng một cây AVL?Cây AVL kiểm tra hệ số cân bằng của các nút sau khi chèn hoặc xóa nút. Nếu hệ số cân bằng của một nút lớn hơn một hoặc nhỏ hơn -1, cây sẽ tự cân bằng lại Có hai thao tác để cân bằng lại cây
3. 1. Xoay phảiHãy bắt đầu với vòng quay bên phải Giả sử chúng ta có một BST gọi là T1, với Y là nút gốc, X là nút con bên trái của Y và Z là nút con bên phải của X. Với các đặc điểm của BST, chúng ta biết rằng X < Z < Y Sau khi xoay phải Y, chúng ta có một cây gọi là T2 với X là gốc và Y là con phải của X và Z là con trái của Y. T2 vẫn là BST vì nó giữ nguyên thứ tự X < Z < Y Hãy cùng xem thao tác xoay vòng bên phải cho AVLTree của chúng tôi
3. 2. Thao tác xoay tráiTa cũng có phép toán xoay trái Giả sử BST có tên là T1, với Y là nút gốc, X là nút con bên phải của Y và Z là nút con bên trái của X. Với điều này, chúng ta biết rằng Y < Z < X Sau khi xoay trái Y, chúng ta có một cây gọi là T2 với X là gốc và Y là con trái của X và Z là con phải của Y. T2 vẫn là BST vì nó giữ nguyên thứ tự Y < Z < X Hãy xem thao tác xoay trái cho AVLTree của chúng ta
3. 3. Kỹ thuật tái cân bằngChúng ta có thể sử dụng các thao tác xoay phải và xoay trái trong các kết hợp phức tạp hơn để giữ Cây AVL cân bằng sau bất kỳ thay đổi nào trong các nút của nó. Trong một cấu trúc không cân bằng, ít nhất một nút có hệ số cân bằng bằng 2 hoặc -2. Hãy xem làm thế nào chúng ta có thể cân bằng cây trong những tình huống này Khi hệ số cân bằng của nút Z là 2 thì cây con có Z là gốc ở một trong hai trạng thái này, coi Y là con phải của Z Đối với trường hợp thứ nhất, chiều cao của con bên phải của Y(X) lớn hơn chiều cao của con bên trái (T2). Chúng ta có thể cân bằng lại cây một cách dễ dàng bằng cách xoay trái Z Đối với trường hợp thứ hai, chiều cao của con bên phải của Y (T4) nhỏ hơn chiều cao của con bên trái (X). Tình huống này cần sự kết hợp của các thao tác xoay Trong trường hợp này, trước tiên chúng ta xoay Y sang phải, để cây có hình dạng giống như trường hợp trước. Sau đó, chúng ta có thể cân bằng lại cây bằng cách xoay trái Z Ngoài ra, khi hệ số cân bằng của nút Z là -2, cây con của nó ở một trong hai trạng thái này, vì vậy chúng tôi coi Z là gốc và Y là con trái của nó Chiều cao ở con bên trái của Y lớn hơn chiều cao ở con bên phải của nó, vì vậy chúng ta cân bằng cây với phép quay bên phải của Z Hoặc trường hợp thứ 2 con bên phải của Y có chiều cao lớn hơn con bên trái Vì vậy, trước hết, chúng tôi chuyển đổi nó thành hình dạng ban đầu với phép quay trái của Y, sau đó chúng tôi cân bằng cây với phép quay phải của Z Hãy xem hoạt động tái cân bằng cho AVLTree của chúng tôi
Chúng tôi sẽ sử dụng cân bằng lại sau khi chèn hoặc xóa một nút cho tất cả các nút trong đường dẫn từ nút đã thay đổi đến gốc 4. Chèn một nútKhi chúng ta chèn một khóa vào cây, chúng ta phải xác định vị trí thích hợp của nó để chuyển các quy tắc BST. Vì vậy, chúng tôi bắt đầu từ thư mục gốc và so sánh giá trị của nó với khóa mới. Nếu khóa lớn hơn, chúng tôi tiếp tục sang bên phải - nếu không, chúng tôi chuyển sang con bên trái Khi chúng tôi tìm thấy nút cha thích hợp, sau đó chúng tôi thêm khóa mới làm nút sang trái hoặc phải, tùy thuộc vào giá trị Sau khi chèn nút, chúng tôi có BST, nhưng nó có thể không phải là Cây AVL. Do đó, chúng tôi kiểm tra các yếu tố cân bằng và cân bằng lại BST cho tất cả các nút trong đường dẫn từ nút mới đến gốc Chúng ta hãy xem thao tác chèn
Điều quan trọng cần nhớ là một khóa là duy nhất trong cây — không có hai nút nào chia sẻ cùng một khóa Độ phức tạp thời gian của thuật toán chèn là một hàm của chiều cao. Vì cây của chúng ta cân bằng, chúng ta có thể giả sử rằng độ phức tạp thời gian trong trường hợp xấu nhất là O(log(N)) 5. Xóa một nútĐể xóa một khóa khỏi cây, trước tiên chúng ta phải tìm nó trong BST Sau khi chúng tôi tìm thấy nút (được gọi là Z), chúng tôi phải giới thiệu ứng cử viên mới để thay thế nó trong cây. Nếu Z là lá, ứng cử viên trống. Nếu Z chỉ có một con, thì đứa trẻ này là ứng cử viên, nhưng nếu Z có hai con, quá trình này sẽ phức tạp hơn một chút Giả sử con phải của Z có tên là Y. Đầu tiên, chúng tôi tìm nút ngoài cùng bên trái của Y và gọi nó là X. Sau đó, ta đặt giá trị mới của Z bằng giá trị của X và tiếp tục xóa X khỏi Y Cuối cùng, chúng tôi gọi phương thức cân bằng lại ở cuối để giữ BST là Cây AVL Đây là phương pháp xóa của chúng tôi
Độ phức tạp thời gian của thuật toán xóa là một hàm của chiều cao của cây. Tương tự như phương pháp chèn, chúng ta có thể giả sử rằng độ phức tạp thời gian trong trường hợp xấu nhất là O(log(N)) 6. Tìm kiếm một nútTìm kiếm một nút trong Cây AVL cũng giống như với bất kỳ BST nào Bắt đầu từ gốc của cây và so sánh khóa với giá trị của nút. Nếu khóa bằng giá trị, hãy trả về nút. Nếu khóa lớn hơn thì tìm từ con bên phải, ngược lại tiếp tục tìm từ con bên trái Độ phức tạp thời gian của tìm kiếm là một hàm của chiều cao. Chúng ta có thể giả định rằng độ phức tạp thời gian trong trường hợp xấu nhất là O(log(N)) |