Binary Search Tree

Bấm Insert / Search / Delete để xem pseudocode.

1. Range query có cắt nhánh (README §8.1)

Liệt kê mọi key trong [lo, hi]. Mẹo BST: nếu node < lo → bỏ luôn nhánh trái; nếu node > hi → bỏ luôn nhánh phải. Không quét cả cây → O(h + k). Đây là điều HashMap không làm được. Dùng cây hiện ở khung trên.

Thử: query một khoảng hẹp — các nhánh nằm ngoài khoảng bị cắt không thăm: lý do range query trên BST nhanh hơn quét mảng.