Chèn và tìm khóa trên BST

Chèn một khóa bắt đầu từ gốc. Nếu nhỏ hơn khóa hiện tại thì sang trái, lớn hơn thì sang phải. Gặp khóa bằng nhau thì dừng vì mô hình cơ bản không nhận khóa trùng. Gặp ô trống hoặc chỉ số ngoài mảng thì đặt khóa mới tại vị trí đó, bổ sung None nếu cần. Hàm trả True nếu thêm mới, False nếu khóa đã có. Chỉ dùng các khóa so sánh được với nhau; None dành cho ô trống. ```python def insert(T, v): k = 0 while k < len(T) and T[k] is not None: if v < T[k]: k = left(k) elif v > T[k]: k = right(k) else: return False if k >= len(T): T.extend([None] * (k-len(T)+1)) T[k] = v return True ```

Tìm khóa v cũng đi từ gốc theo so sánh. Nếu bằng thì trả **chỉ số**, không phải chính khóa; gặp vị trí không có nút thì trả −1. Lệnh tìm toàn cây là `search(T,0,v)`. ```python def search(T, k, v): while 0 <= k < len(T) and T[k] is not None: if v == T[k]: return k k = left(k) if v < T[k] else right(k) return -1 def search_recursive(T, k, v): if not 0 <= k < len(T) or T[k] is None: return -1 if v == T[k]: return k if v < T[k]: return search_recursive(T, left(k), v) return search_recursive(T, right(k), v) ```