Khi xây dựng cấu trúc dữ liệu cây tìm kiếm nhị phân cho hệ thống quản lý danh mục sản phẩm, làm thế nào để thực hiện việc chèn một nút mới vào Binary Search Tree mà vẫn đảm bảo tính chất cơ bản của cây?

Question

Accepted Answer

Để chèn một nút mới vào Binary Search Tree (BST), chúng ta cần tuân thủ nguyên tắc: giá trị của nút bên trái nhỏ hơn nút cha và giá trị của nút bên phải lớn hơn hoặc bằng nút cha.
Cơ chế hoạt động

So sánh giá trị cần chèn với nút hiện tại (bắt đầu từ Root).
Nếu giá trị nhỏ hơn nút hiện tại, di chuyển sang cây con bên trái.
Nếu giá trị lớn hơn hoặc bằng nút hiện tại, di chuyển sang cây con bên phải.
Lặp lại quá trình cho đến khi gặp một con trỏ null (vị trí trống), tại đây tạo nút mới và gắn vào vị trí đó.

Ví dụ mã nguồn thực thi bằng JavaScript
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

insert(value) {
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return this;
    }
    let current = this.root;
    while (true) {
      if (value === current.value) return undefined;
      if (value < current.value) {
        if (current.left === null) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else {
        if (current.right === null) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }
}
Kinh nghiệm thực chiến
Ở cấp độ Junior, lập trình viên thường hay quên xử lý trường hợp giá trị trùng lặp (duplicate values). Trong hệ thống Enterprise, việc xử lý duplicate cần được định nghĩa rõ ràng: hoặc bỏ qua, hoặc tăng biến đếm số lượng (frequency counter) tại nút đó để tránh làm lãng phí bộ nhớ Heap.

Khi xây dựng cấu trúc dữ liệu cây tìm kiếm nhị phân cho hệ thống quản lý danh mục sản phẩm, làm thế nào để thực hiện việc chèn một nút mới vào Binary Search Tree mà vẫn đảm bảo tính chất cơ bản của cây?

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi binary tree liên quan cùng chủ đề