Cho một bộ dữ liệu trong cây tìm kiếm nhị phân, như các số từ 1 đến 10, có thể có nhiều cây tìm kiếm nhị phân cân bằng tồn tại không?Có thể có nhiều BST hợp lệ cho một tập dữ liệu nhất định không?
Hoặc chỉ có một BST cân bằng duy nhất cho tập hợp dữ liệu đó?
Cảm ơn
Tất cả phụ thuộc vào cấu trúc dữ liệu cây nhị phân cụ thể được sử dụng, các thuật toán chèn, các tiêu chí cân bằng và trật tự chèn, nhưng có - nó có thể có nhiều tương đương và BSTs cân bằng giá trị trong một chuỗi giá trị đã cho.
Ví dụ, đây là một hợp lệ Red/Black Tree nơi những con số 1-10 được chèn thứ tự tăng dần:
Mặt khác, đây là một hợp lệ AVL Tree, nơi những con số 1-10 được chèn chính xác theo trình tự giống như trong Red/Black Tree:
rõ ràng, cây không phải là giống hệt nhau - nhưng một trật tự d cân bằng tài sản giữ cho cả hai.
Vì vậy, giả sử tôi đang sử dụng cây AVL, liệu có nhiều cây AVL cho cùng một tập hợp các số không? Nếu vậy, là thứ tự chèn hành động khiến các cây khác nhau tồn tại? – user2305684
@ user2305684 nếu chúng tôi hạn chế cây cho một triển khai cụ thể, có, chúng tôi vẫn có thể nhận được các kết quả khác nhau tùy thuộc vào thứ tự chèn. Nhưng chúng ta có thể chắc chắn rằng nếu các phần tử được chèn vào cùng thứ tự cho cùng một cấu trúc dữ liệu và thuật toán, thì cây kết quả sẽ giống nhau –