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

Tìm nhị phân nhanh nhưng cần array đã sắp xếp, mà chèn vào array thì phải dời chỗ, tốn O(n). Cây nhị phân tìm kiếm giữ dữ liệu luôn có thứ tự, vừa tìm vừa thêm đều nhanh.

Khái niệm

🎄 Cây nhị phân tìm kiếm (binary search tree, BST): mỗi node có tối đa hai con, mọi giá trị ở nhánh trái nhỏ hơn giá trị của node, mọi giá trị ở nhánh phải lớn hơn hoặc bằng giá trị của node.

Node trên cùng gọi là gốc, node không có con gọi là lá.

⛰️ Chiều cao cây: số node trên đường dài nhất từ gốc xuống lá, cũng là số bước tìm hoặc thêm trong trường hợp xấu nhất.

Cây cân đối cao khoảng log n, nên tìm và thêm là O(log n). Node ở đây giống node của linked list, chỉ khác là có hai tham chiếu left, right thay vì một next.

Ví dụ

// Main.java
void main() {
    TreeNode root = null;
    long[] prices = {7000, 3000, 12000, 5000, 25000};
    for (long price : prices) {
        root = insert(root, price);
    }
    printInOrder(root); // 3000 5000 7000 12000 25000
}

TreeNode insert(TreeNode node, long value) {
    if (node == null) {
        return new TreeNode(value);
    }
    if (value < node.getValue()) {
        node.setLeft(insert(node.getLeft(), value));
    } else {
        node.setRight(insert(node.getRight(), value));
    }
    return node;
}

void printInOrder(TreeNode node) {
    if (node == null) {
        return;
    }
    printInOrder(node.getLeft());
    System.out.print(node.getValue() + " ");
    printInOrder(node.getRight());
}

// TreeNode.java
class TreeNode {
    private long value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(long value) {
        this.value = value;
    }

    public long getValue() { return value; }
    public TreeNode getLeft() { return left; }
    public TreeNode getRight() { return right; }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}

insert là đệ quy: nhỏ hơn thì đi trái, không thì đi phải, gặp chỗ trống (null) thì đặt node mới.
printInOrder in nhánh trái, rồi node, rồi nhánh phải, nên giá in ra luôn tăng dần.

Cây sau khi thêm 7000, 3000, 12000, 5000, 25000

Java có TreeMap<K, V> và TreeSet<E>: bên trong là cây tự cân đối, nên luôn O(log n) và duyệt ra theo thứ tự key.

Thử ngay

Giữ TreeNode.java, thay Main.java bằng đoạn dưới đây: insert giữ nguyên, thêm method height đo chiều cao, rồi so hai cây cùng 7 số nhưng thêm theo thứ tự khác nhau:

// Main.java
void main() {
    int[] ascending = {1, 2, 3, 4, 5, 6, 7};
    int[] shuffled = {4, 2, 6, 1, 3, 5, 7};

    TreeNode sorted = null;
    for (int x : ascending) {
        sorted = insert(sorted, x);
    }
    TreeNode mixed = null;
    for (int x : shuffled) {
        mixed = insert(mixed, x);
    }
    System.out.println(height(sorted));
    System.out.println(height(mixed));
}

TreeNode insert(TreeNode node, long value) {
    if (node == null) {
        return new TreeNode(value);
    }
    if (value < node.getValue()) {
        node.setLeft(insert(node.getLeft(), value));
    } else {
        node.setRight(insert(node.getRight(), value));
    }
    return node;
}

int height(TreeNode node) {
    if (node == null) {
        return 0;
    }
    return 1 + Math.max(
        height(node.getLeft()),
        height(node.getRight()));
}

Math.max trả về số lớn hơn trong hai số.

Đoán trước khi chạy: hai cây cao bao nhiêu?

Xem kết quả

7
3

Thêm theo thứ tự tăng dần, số nào cũng lớn hơn nên đi sang phải hết: cây thành một đường thẳng như linked list, tìm mất O(n). Thêm xen kẽ thì cây cân đối, chỉ cao 3.

Lỗi hay gặp

Tự viết BST rồi nạp dữ liệu đã sắp xếp. Dữ liệu lấy từ database hay file thường đã sắp xếp sẵn, nên cây lệch hẳn về một bên và mất hết ưu điểm.

// SAI — nạp giá đã sắp xếp: cây lệch thành O(n)
TreeNode root = null;
long[] sortedPrices = {3000, 5000, 7000};
for (long price : sortedPrices) {
    root = insert(root, price);
}

// ĐÚNG — TreeSet tự cân đối, luôn O(log n)
var prices = new TreeSet<Long>(
    List.of(3000L, 5000L, 7000L));
System.out.println(prices.contains(5000L)); // true

Tóm tắt

BST: trái nhỏ hơn, phải lớn hơn hoặc bằng. Duyệt trái, node, phải thì ra thứ tự tăng.
Tìm và thêm tốn số bước bằng chiều cao: cây cân đối là O(log n).
Nạp dữ liệu đã sắp xếp vào BST tự viết thì cây lệch thành O(n).
Dùng TreeMap, TreeSet của Java: cây tự cân đối.

Khái niệm

Node trên cùng gọi là gốc, node không có con gọi là lá.

⛰️ Chiều cao cây: số node trên đường dài nhất từ gốc xuống lá, cũng là số bước tìm hoặc thêm trong trường hợp xấu nhất.

Cây cân đối cao khoảng log n, nên tìm và thêm là O(log n). Node ở đây giống node của linked list, chỉ khác là có hai tham chiếu left, right thay vì một next.

Ví dụ

// Main.java
void main() {
    TreeNode root = null;
    long[] prices = {7000, 3000, 12000, 5000, 25000};
    for (long price : prices) {
        root = insert(root, price);
    }
    printInOrder(root); // 3000 5000 7000 12000 25000
}

TreeNode insert(TreeNode node, long value) {
    if (node == null) {
        return new TreeNode(value);
    }
    if (value < node.getValue()) {
        node.setLeft(insert(node.getLeft(), value));
    } else {
        node.setRight(insert(node.getRight(), value));
    }
    return node;
}

void printInOrder(TreeNode node) {
    if (node == null) {
        return;
    }
    printInOrder(node.getLeft());
    System.out.print(node.getValue() + " ");
    printInOrder(node.getRight());
}

// TreeNode.java
class TreeNode {
    private long value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(long value) {
        this.value = value;
    }

    public long getValue() { return value; }
    public TreeNode getLeft() { return left; }
    public TreeNode getRight() { return right; }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}

insert là đệ quy: nhỏ hơn thì đi trái, không thì đi phải, gặp chỗ trống (null) thì đặt node mới.
printInOrder in nhánh trái, rồi node, rồi nhánh phải, nên giá in ra luôn tăng dần.

Cây sau khi thêm 7000, 3000, 12000, 5000, 25000

Java có TreeMap<K, V> và TreeSet<E>: bên trong là cây tự cân đối, nên luôn O(log n) và duyệt ra theo thứ tự key.

Thử ngay

// Main.java
void main() {
    int[] ascending = {1, 2, 3, 4, 5, 6, 7};
    int[] shuffled = {4, 2, 6, 1, 3, 5, 7};

    TreeNode sorted = null;
    for (int x : ascending) {
        sorted = insert(sorted, x);
    }
    TreeNode mixed = null;
    for (int x : shuffled) {
        mixed = insert(mixed, x);
    }
    System.out.println(height(sorted));
    System.out.println(height(mixed));
}

TreeNode insert(TreeNode node, long value) {
    if (node == null) {
        return new TreeNode(value);
    }
    if (value < node.getValue()) {
        node.setLeft(insert(node.getLeft(), value));
    } else {
        node.setRight(insert(node.getRight(), value));
    }
    return node;
}

int height(TreeNode node) {
    if (node == null) {
        return 0;
    }
    return 1 + Math.max(
        height(node.getLeft()),
        height(node.getRight()));
}

Math.max trả về số lớn hơn trong hai số.

Đoán trước khi chạy: hai cây cao bao nhiêu?

Xem kết quả

7
3

Lỗi hay gặp

// SAI — nạp giá đã sắp xếp: cây lệch thành O(n)
TreeNode root = null;
long[] sortedPrices = {3000, 5000, 7000};
for (long price : sortedPrices) {
    root = insert(root, price);
}

// ĐÚNG — TreeSet tự cân đối, luôn O(log n)
var prices = new TreeSet<Long>(
    List.of(3000L, 5000L, 7000L));
System.out.println(prices.contains(5000L)); // true

Tóm tắt

BST: trái nhỏ hơn, phải lớn hơn hoặc bằng. Duyệt trái, node, phải thì ra thứ tự tăng.
Tìm và thêm tốn số bước bằng chiều cao: cây cân đối là O(log n).
Nạp dữ liệu đã sắp xếp vào BST tự viết thì cây lệch thành O(n).
Dùng TreeMap, TreeSet của Java: cây tự cân đối.

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Tự kiểm tra

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

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Tự kiểm tra