Theo tôi biết thời gian phức tạp giữa các cây AVL và Binary Search Trees giống nhau trong trường hợp trung bình, với AVL đánh bại BST trong trường hợp xấu nhất. Điều này cho tôi một gợi ý rằng AVL luôn vượt trội hơn BST trong mọi cách có thể để tương tác với chúng, có lẽ thêm một chút phức tạp khi nói đến việc thực hiện cân bằng.Cây tìm kiếm nhị phân trên cây AVL
Có lý do nào để mọi người nên sử dụng BST thay vì AVL ở địa điểm đầu tiên không?
Đầu tiên, nhận được hiệu suất tốt nhất có thể là không phải mục tiêu cuối cùng của lập trình. Vì vậy, ngay cả khi tùy chọn B luôn nhanh hơn và tiêu thụ ít bộ nhớ hơn A, điều đó không có nghĩa nó luôn là lựa chọn tốt hơn, nếu nó phức tạp hơn. Mã phức tạp hơn mất nhiều thời gian để viết, khó hiểu hơn và có nhiều khả năng chứa lỗi hơn. Vì vậy, nếu tùy chọn đơn giản nhưng kém hiệu quả A là đủ tốt cho bạn, thì điều đó có nghĩa đó là lựa chọn tốt hơn.
Bây giờ, nếu bạn muốn so sánh cây AVL với cây tìm kiếm nhị phân đơn giản (BST) mà không cân bằng, thì AVL sẽ tiêu thụ nhiều bộ nhớ hơn (mỗi nút phải nhớ yếu tố cân bằng) và mỗi thao tác có thể chậm hơn (vì bạn cần để duy trì hệ số cân bằng và đôi khi thực hiện phép quay).
Như bạn đã nói, BST không cân bằng có trường hợp xấu nhất (tuyến tính) tồi tệ nhất. Nhưng nếu bạn biết rằng trường hợp xấu nhất này sẽ không xảy ra với bạn, hoặc nếu bạn không sao nếu hoạt động chậm trong những trường hợp hiếm hoi, BST không cân bằng có thể tốt hơn AVL.
Chính xác là lý do tôi chờ đợi. Cảm ơn và chấp nhận. –
Giả định của tôi là: khi bạn đề cập đến BST, bạn có nghĩa là một BST không cân bằng.
Có thể lập luận rằng nếu bạn cần cấu trúc dữ liệu điều hướng và bạn biết dữ liệu của mình sẽ không tệ nhất (được sắp xếp) và hơi nhỏ, một BST (không cân bằng) sẽ là đủ.
Nhưng nhiều khả năng đó là trường hợp hiếm hoi.
Cây AVL cũng là BST nhưng có thể tự cân bằng lại. Hành vi này làm cho nó nhanh hơn trong trường hợp xấu nhất. Nó giữ cân bằng lại chính nó như vậy trong trường hợp xấu nhất nó sẽ tiêu thụ O (log n) thời gian khi BST đồng bằng sẽ có O (n). Vì vậy, câu trả lời cho câu hỏi của bạn: Nó luôn luôn là tốt hơn để thực hiện AVL cây hơn chỉ BST đồng bằng.
Vì có thêm chi phí kiểm tra và cập nhật các yếu tố cân bằng và các nút quay, chèn và xóa trong cây AVL có thể khá chậm khi so sánh với BST không cân bằng.
Vì sự cân bằng chặt chẽ, tìm kiếm sẽ không bao giờ mất thời gian tuyến tính, vì vậy bạn có thể muốn sử dụng cây AVL trong các tình huống mà tìm kiếm là hoạt động thường xuyên hơn cập nhật cây.
Cây AVL hết thời trang, ngày nay chúng bị thay thế bởi cây đỏ đen. – starblue