Hai lựa chọn ngẫu nhiên (randomized alternatives) cho cây tìm kiếm xác định (deterministic search trees) là cây tìm kiếm nhị phân ngẫu nhiên (randomized binary search trees - treaps) và danh sách bỏ qua (skip lists). Cả treaps và skip lists đều là cấu trúc dữ liệu thanh lịch (elegant), nơi ngẫu nhiên hóa tạo điều kiện cho thao tác cập nhật đơn giản và hiệu quả.
Trong phần này, chúng ta giải thích cách cả treaps và skip lists có thể được cài đặt như cây tìm kiếm ngón hiệu quả mà không thay đổi cấu trúc dữ liệu. Cả hai cấu trúc hỗ trợ tìm kiếm ngón bằng thời gian kỳ vọng O(log d), nơi kỳ vọng lấy qua 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.
Danh sách bỏ qua (Skip lists)
Trong skip list, có thể finger search phần tử a từ nút chứa phần tử b bằng cách tiếp tục tìm kiếm từ điểm đó. Lưu ý nếu a < b, tìm kiếm tiến hướng lùi, nếu a > b, tìm kiếm tiến hướng tiến. Trường hợp lùi đối xứng với tìm kiếm thông thường, nhưng trường hợp tiến phức tạp hơn. Thông thường tìm kiếm nhanh vì sentinel ở đầu là nút cao nhất. Tuy nhiên, ngón có thể gắn với nút chiều cao 1. Do đó, đôi khi phải leo khi tìm kiếm; điều không xảy ra bình thường. Tuy nhiên, даже với phức tạp này, vẫn đạt O(log d) thời gian tìm kiếm kỳ vọng.
Treaps
Treap được định nghĩa là cây tìm kiếm nhị phân ngẫu nhiên (randomized BST). Tìm kiếm trong treap giống như tìm kiếm trong bất kỳ BST nào. Treaps có tính chất: độ dài đường đi kỳ vọng giữa hai phần tử cách nhau d là O(log d). Do đó, để finger search từ nút chứa phần tử b cho phần tử a, có thể leo lên cây từ b cho đến khi tìm thấy tổ tiên của a, lúc đó tìm kiếm BST thông thường tiếp tục. Việc kiểm tra nút có phải tổ tiên của nút khác không tầm thường, có thể bổ sung cây để hỗ trợ truy vấn dạng này để đạt O(log d) finger search kỳ vọng.