Hai lựa chọn thay thế ngẫu nhiên cho cây tìm kiếm xác định là cây tìm kiếm nhị phân ngẫu nhiên, cây tìm kiếm và danh sách bỏ qua. Cả danh sách treap và danh sách bỏ qua đều được định nghĩa là cấu trúc dữ liệu thanh lịch, trong đó việc ngẫu nhiên hóa tạo điều kiện thuận lợi cho các hoạt động cập nhật đơn giản và hiệu quả.
Trong phần này, chúng tôi giải thích cách cả danh sách treap và danh sách bỏ qua có thể được triển khai dưới dạng cây tìm kiếm ngón tay hiệu quả mà không cần thay đổi cấu trúc dữ liệu. Cả hai cấu trúc dữ liệu đều hỗ trợ tìm kiếm bằng ngón tay bằng cách sử dụng thời gian O (log d) dự kiến, trong đó kỳ vọng được thực hiện trên các lựa chọn ngẫu nhiên do thuật toán tạo ra trong quá trình xây dựng cấu trúc dữ liệu.
Bỏ qua danh sách
Trong danh sách bỏ qua, người ta có thể tìm kiếm phần tử a từ một nút chứa phần tử b bằng cách tiếp tục tìm kiếm từ điểm này. Lưu ý rằng nếu a
Treaps
Treap được định nghĩa là cây tìm kiếm nhị phân ngẫu nhiên (BST). Tìm kiếm trong một treap tương tự như tìm kiếm một phần tử trong bất kỳ BST nào khác. Tuy nhiên, treap có đặc tính là độ dài đường dẫn dự kiến giữa hai phần tử của xa được ký hiệu là O (log d). Do đó, để tìm kiếm ngón tay từ nút chứa phần tử b cho phần tử a, người ta có thể leo lên cây từ phần tử b cho đến khi tìm thấy tổ tiên của phần tử a, lúc đó tìm kiếm BST bình thường vẫn tiến hành như bình thường. Mặc dù việc tính toán xem một nút có phải là tổ tiên của nút khác hay không, nhưng người ta có thể tăng cường cây để hỗ trợ các truy vấn dạng này để cung cấp thời gian tìm kiếm ngón tay O (log d) dự kiến.