Ở đây chúng ta sẽ thấy cây Giải đấu, cây Người chiến thắng và cây Người thả lỏng. Cây giải đấu là một cây nhị phân hoàn chỉnh với n nút bên ngoài và n - 1 nút bên trong. Các nút bên ngoài đại diện cho người chơi và các nút bên trong đại diện cho người chiến thắng trong trận đấu giữa hai người chơi. Cây này còn được gọi là cây Lựa chọn.
Có một số thuộc tính của cây Giải đấu. Những thứ này giống như bên dưới -
-
Cây này đã bén rễ. Vì vậy, liên kết trong cây và đường dẫn trực tiếp từ cha mẹ đến con cái, và có một phần tử duy nhất không có cha mẹ
-
Giá trị cha nhỏ hơn hoặc bằng nút đó để nói chung cho bất kỳ toán tử so sánh nào, có thể được sử dụng miễn là giá trị tương đối của cha và con là bất biến trong toàn bộ cây
-
Cây có số nút không phải là lũy thừa của 2, chứa các lỗ. Các lỗ có thể xuất hiện ở mọi nơi trên cây.
-
Cây này là sự tổng quát hóa thích hợp của đống nhị phân
-
Gốc sẽ đại diện cho người chiến thắng chung cuộc của giải đấu.
Có hai loại Cây thi đấu -
-
Cây chiến thắng
-
Cây lỏng lẻo
Cây chiến thắng
Cây chiến thắng là một cây nhị phân hoàn chỉnh, trong đó mỗi nút đại diện cho nút nhỏ hơn hoặc lớn hơn trong số hai nút con của nó, được gọi là cây chiến thắng. Gốc đang giữ nút nhỏ nhất hoặc lớn nhất của cây. Người chiến thắng của cây giải đấu là khóa n nhỏ nhất hoặc lớn nhất trong tất cả các dãy. Dễ dàng nhận thấy rằng cây chiến thắng có thể được hình thành trong thời gian O (log n).
Ví dụ - Giả sử có một số phím, 3, 5, 6, 7, 20, 8, 2, 9
Cây nới lỏng
Cây lỏng lẻo là cây nhị phân hoàn chỉnh cho n người chơi trong đó n nút bên ngoài và n - 1 nút bên trong có mặt. Phần lỏng lẻo của trận đấu được lưu trữ trong các nút bên trong. Nhưng trong tổng thể chiến thắng này được lưu trữ tại cây [0]. Looser là một đại diện thay thế, lưu trữ looser của một trận đấu tại nút tương ứng. Một lợi thế của trình đơn giản là, để cấu trúc lại cây sau khi cây chiến thắng được xuất ra, chỉ cần kiểm tra nút trên đường dẫn từ lá đến gốc là đủ chứ không phải là anh em của các nút trên đường dẫn này.
Ví dụ - Để tạo cây lỏng lẻo, trước tiên chúng ta phải tạo cây chiến thắng.
Giả sử có một số khóa, 10, 2, 7, 6, 5, 9, 12, 1. Vì vậy, chúng tôi sẽ tạo cây chiến thắng tối thiểu lúc đầu.
Bây giờ, chúng tôi sẽ lưu trữ phần lỏng lẻo của trận đấu trong mỗi nút bên trong.
