BST Insertion · Nhóm: Cây
Chèn lần lượt từng khoá vào cây tìm kiếm nhị phân: từ gốc đi xuống, nhỏ hơn rẽ trái, lớn hơn rẽ phải, gặp chỗ trống thì đặt nút mới.
Bắt đầu từ gốc, so khoá mới với khoá nút hiện tại.
Nếu nhỏ hơn thì đi xuống con trái, ngược lại đi xuống con phải.
Khi chạm nhánh trống thì tạo nút mới và đặt vào đúng chỗ đó.
BST giữ dữ liệu luôn theo thứ tự, cho phép tìm kiếm, chèn, xoá trong thời gian tỉ lệ chiều cao cây, và duyệt trung thứ ra ngay dãy tăng dần.
def insert(root, key):
if root is None:
return Node(key) # empty spot found, place here
if key < root.val:
root.left = insert(root.left, key) # go left when smaller
else:
root.right = insert(root.right, key) # go right when larger
return root
Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.