Cây nhị phân tìm kiếm

Cây nhị phân tìm kiếm (BST) là một cây nhị phân mà mỗi nút con bên trái có giá trị nhỏ hơn nút gốc và mỗi nút con bên phải có giá trị lớn hơn nút gốc. Đặc điểm của cây nhị phân tìm kiếm là cả cây con bên trái và cây con bên phải cũng đều là cây nhị phân tìm kiếm.

Thao tác

2.1 Thao tác - Tìm kiếm

Hàm tìm kiếm một phần tử trong cây nhị phân tìm kiếm:

public boolean find(int value) {
    Node current = root;
    while (current != null) {
        if (value < current.value) {
            current = current.left;
        } else if (value > current.value) {
            current = current.right;
        } else {
            return true;
        }
    }
    return false;
}

2.2 Thao tác - Chèn

Hàm chèn một phần tử vào cây nhị phân tìm kiếm:

public boolean add(int value) {
    if (root == null) {
        root = new Node(value);
        return true;
    }
    Node current = root;
    Node parent = null;
    while (current != null) {
        parent = current;
        if (value < current.value) {
            current = current.left;
        } else if (value > current.value) {
            current = current.right;
        } else {
            return false; // Trùng giá trị
        }
    }
    if (value < parent.value) {
        parent.left = new Node(value);
    } else {
        parent.right = new Node(value);
    }
    return true;
}

2.3 Thao tác - Xóa

Hàm xóa một phần tử khỏi cây nhị phân tìm kiếm:

public void delete(int value) {
    Node current = root;
    Node parent = null;
    while (current != null && current.value != value) {
        parent = current;
        if (value < current.value) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    if (current == null) return; // Không tìm thấy giá trị

    if (current.left == null || current.right == null) {
        Node child = (current.left != null) ? current.left : current.right;
        if (parent == null) {
            root = child;
        } else {
            if (current == parent.left) {
                parent.left = child;
            } else {
                parent.right = child;
            }
        }
    } else {
        Node successor = getSuccessor(current);
        if (parent == null) {
            root = successor;
        } else if (current == parent.left) {
            parent.left = successor;
        } else {
            parent.right = successor;
        }
        successor.left = current.left;
    }
}

private Node getSuccessor(Node node) {
    Node successor = node.right;
    Node successorParent = node;
    while (successor.left != null) {
        successorParent = successor;
        successor = successor.left;
    }
    if (successor != node.right) {
        successorParent.left = successor.right;
        successor.right = node.right;
    }
    return successor;
}

Phân tích hiệu suất

Hiệu suất của các thao tác trên cây nhị phân tìm kiếm phụ thuộc vào độ sâu của cây. Trong trường hợp lý tưởng, cây nhị phân tìm kiếm hoàn toàn cân bằng với độ sâu trung bình là log(n). Tuy nhiên, trong trường hợp xấu nhất, cây nhị phân tìm kiếm trở thành một cây đơn nhánh với độ sâu trung bình là n/2.