Thực hành tra giá và cập nhật thực đơn

Mỗi nút lưu `[tên món, giá]`; None vẫn là vị trí không có nút. So sánh tên để đi trái/phải, không so giá khi tra theo tên. Ví dụ dữ liệu giả định: |Tên món|Giá, đồng| |---|---| |Mì rau|25000| |Cơm nấm|20000| |Trà gừng|12000| |Nước lọc|12000| Tên món không trùng; hai món có thể cùng giá. Giá lưu dạng số nguyên để so sánh hoặc tính toán. Tệp menu.inp ghi hai trường cách bởi dấu phẩy, không viết dấu phân cách hàng nghìn trong giá.

Các hàm dùng lại left, right và Tree. record_search trả chỉ số hoặc −1. record_upsert trả True khi cập nhật khóa đã có, False khi thêm khóa mới. Nó dùng bản sao row để lưu dữ liệu. ```python def record_search(T, key): k = 0 while k < len(T) and T[k] is not None: if key == T[k][0]: return k k = left(k) if key < T[k][0] else right(k) return -1 def record_upsert(T, row): key = row[0] k = 0 while k < len(T) and T[k] is not None: if key < T[k][0]: k = left(k) elif key > T[k][0]: k = right(k) else: T[k] = row.copy() return True if k >= len(T): T.extend([None] * (k-len(T)+1)) T[k] = row.copy() return False def record_inorder(T, k, out): if 0 <= k < len(T) and T[k] is not None: record_inorder(T, left(k), out) out.append(T[k].copy()) record_inorder(T, right(k), out) ```