Cấu trúc dữ liệu tìm kiếm bằng ngón tay động ngoài việc tìm kiếm bằng ngón tay còn thực hiện việc chèn và xóa các phần tử ở vị trí do ngón tay đưa ra.
Cây tìm kiếm ngón tay được định nghĩa là một biến thể của cây B hỗ trợ tìm kiếm ngón tay trong thời gian O (log d) và cập nhật trong thời gian O (1), giả sử rằng chỉ duy trì O (1) ngón tay di chuyển được.
Di chuyển theo vị trí d của ngón tay yêu cầu thời gian là O (log d).
Các công trình xây dựng cây tìm kiếm ngón tay (có nghĩa là cây AVL, cây đỏ đen) coi là một số lượng ngón tay cố định không đổi hoặc chỉ hỗ trợ cập nhật theo thời gian cố định được phân bổ.
Các công trình hỗ trợ số lượng ngón tay tùy ý và có cập nhật trường hợp xấu nhất đã được tạo.
Cây tìm kiếm hỗ trợ cập nhật ở một vị trí tùy ý trong trường hợp xấu nhất là O (1) thời gian, nhưng chỉ hỗ trợ tìm kiếm trong thời gian O (log n).
Các cấu trúc hỗ trợ tìm kiếm theo thời gian O (log d) và chèn và xóa theo thời gian O (log d n).
Cây tìm kiếm ngón tay sử dụng các lần chèn thời gian cố định trong trường hợp xấu nhất và xóa theo thời gian O (log d n).
Theo một giải pháp thay thế hiệu quả về không gian cho cấp độ được liên kết (2,4) - cây, cho phép một ngón tay duy nhất, có thể được tiến hành với cùng chi phí hiệu suất như (2,4) -trees. Trong giải pháp này, không cần liên kết cấp và con trỏ mẹ, thay vào đó, một cấu trúc dữ liệu không gian O (log n) đặc biệt, bàn tay, được tạo cho ngón tay, cho phép ngón tay được di chuyển một cách hiệu quả.
Cây ghép được định nghĩa là một loại cây tìm kiếm nhị phân tự điều chỉnh hỗ trợ tìm kiếm, chèn và xóa theo thời gian O (log n) được phân bổ. Cây splay đó có thể được triển khai dưới dạng cây tìm kiếm ngón tay hiệu quả.
Với chi phí khởi tạo O (n), chi phí phân bổ của một lần truy cập ở khoảng cách d so với lần truy cập trước đó trong cây splay là O (log d) trong đó các lần truy cập bao gồm tìm kiếm, chèn và xóa.
Lưu ý rằng câu lệnh chỉ triển khai khi có một ngón tay, ngón tay này luôn trỏ đến phần tử được truy cập cuối cùng.
Tất cả các cấu trúc được đề cập ở trên có thể được áp dụng trên máy con trỏ trong đó thao tác duy nhất được phép trên các phần tử là so sánh hai phần tử.
Đối với mô hình Máy tính Truy cập Ngẫu nhiên (RAM), cây tìm kiếm ngón tay được phát triển với thời gian cập nhật không đổi và thời gian tìm kiếm O (log d). Kết quả này đạt được bằng cách lập bảng các cấu trúc cây nhỏ, nhưng chỉ thực hiện so sánh các phần tử.
