Khái Niệm Nền Tảng: Cây Tìm Kiếm

Cây tìm kiếm nhị phân (Binary Search Tree - BST) là cấu trúc dữ liệu cơ bản hỗ trợ các thao tác tìm kiếm, chèn và xóa hiệu quả. Một cây BST hợp lệ tuân thủ các quy tắc sau:

• Nếu con trai bên trái tồn tại, giá trị của nó phải nhỏ hơn nút gốc.
• Nếu con trai bên phải tồn tại, giá trị của nó phải lớn hơn nút gốc.
• Cả hai subtree đều phải là cây tìm kiếm nhị phân hợp lệ.

public class SimpleBST {
    public static class NodeElement {
        private int val;
        private NodeElement leftChild;
        private NodeElement rightChild;

        public NodeElement(int v) {
            this.val = v;
        }
    }

    private NodeElement rootTree;

    public boolean findValue(int targetKey) {
        NodeElement current = rootTree;
        if (current == null) return false;

        while (current != null) {
            if (current.val > targetKey) {
                current = current.leftChild;
            } else if (current.val < targetKey) {
                current = current.rightChild;
            } else {
                return true;
            }
        }
        return false;
    }

    public void insertValue(int newValue) {
        NodeElement newNode = new NodeElement(newValue);
        NodeElement current = rootTree;
        NodeElement parentRef = null;

        if (rootTree == null) {
            rootTree = newNode;
            return;
        }

        while (current != null) {
            if (current.val > newValue) {
                parentRef = current;
                current = current.leftChild;
            } else if (current.val < newValue) {
                parentRef = current;
                current = current.rightChild;
            } else {
                return; // Giá trị đã tồn tại
            }
        }
        // Gán vào đúng vị trí cha
        if (parentRef.val > newValue) {
            parentRef.leftChild = newNode;
        } else {
            parentRef.rightChild = newNode;
        }
    }
}

Mô Hình Tìm Kiếm Trong Ứng Dụng

Tìm kiếm động thường xuất hiện khi cần thêm hoặc xóa dữ liệu liên tục (như tra cứu tên trong danh bạ, kiểm tra trùng lặp). Các cấu trúc như Map và Set tối ưu hóa hoạt động này so với tìm kiếm tuyến tính (O(N)) hay nhị phân (O(logN) nhưng yêu cầu sắp xếp).

Mô hình dữ liệu phổ biến nhất chia làm hai loại:

1. Mô hình Khóa thuần túy (Pure Key): Chỉ quan tâm đến sự tồn tại của phần tử (Ví dụ: Từ điển, List tên trùng).
2. Mô hình Khóa-Giá trị (Key-Value): Mỗi khóa đi kèm một thông tin cụ thể (Ví dụ: Mã nhân viên gắn liền với mức lương).

Set lưu trữ Key, Map lưu trữ cặp Key-Value.

Tìm Hiểu Kỹ Về Giao Diện Map

Đặc Tính Cốt Lõi

Map là tập hợp chứa các cặp đối tượng (Entry). Đặc điểm nhận dạng bao gồm:

• Là giao diện không thừa kế trực tiếp từ Collection (dù đôi khi bị nhầm lẫn).
• Khoá (Key) bắt buộc phải duy nhất, có thể dùng để truy vết.
• Gía trị (Value) có thể trùng lặp nhau.
• Không hỗ trợ duyệt từng phần tử riêng lẻ như List mà phải qua Entry hoặc Key/Value set.

Hàm Mặc Định Thường Dùng

Map<String, Integer> userMap = new HashMap<>();
userMap.put("NguyenVanA", 25);
// Nếu thêm lại khóa cũ, giá trị cũ sẽ bị thay thế
Integer oldVal = userMap.put("NguyenVanA", 26); 
System.out.println(oldVal + ", " + userMap.get("NguyenVanA")); 

Phương Pháp Duyệt Vòng Qua Dữ Liệu

Có hai cách chính để truy xuất nội dung Map:

1. Duyệt qua khóa (KeySet): Lấy tập khóa, lặp qua từng khóa và gọi hàm get. Hiệu năng thấp hơn vì phải tìm lại giá trị mỗi lần.
2. Duyệt qua Entry Set: Lấy tập hợp các cặp Entry (khóa-giá trị). Cách này tiết kiệm chi phí truy xuất giá trị trực tiếp.

// Duyệt Entry
for (Map.Entry<String, Integer> entry : userMap.entrySet()) {
    String name = entry.getKey();
    Integer age = entry.getValue();
    System.out.println(name + ": " + age);
}

Phân Loại Thực Hiện

Hai lớp thực thi phổ biến là TreeMap và HashMap. TreeMap tự động sắp xếp theo khóa, trong khi HashMap giữ nguyên thứ tự chèn (trong phiên bản cũ) hoặc không đảm bảo thứ tự, tốc độ truy xuất nhanh hơn dựa trên mảng băm.

Lưu Ý Quan Trọng

• Key của TreeMap không được phép là null, trong khi HashMap chấp nhận được.
• Cannot modify keys directly; must remove and re-insert.

Bộ Chứa Set Và Việc Loại Bỏ Trùng Lặp

Thỏa mãn nguyên lý tập hợp toán học, Set chỉ chấp nhận các phần tử duy nhất. Dù kế thừa từ Collection, nó không hỗ trợ truy cập theo chỉ số.

Điểm Khác Biệt Với Map

Set lưu trữ đơn giá trị (Key). Nhiều triển khai Set (như TreeSet) sử dụng cấu trúc Map bên dưới để quản lý (đặt giá trị dummy object làm Value).

Ứng Dụng Thực Tế

Chức năng mạnh mẽ nhất của Set là loại bỏ dữ liệu trùng lặp ngay khi thêm vào. Các thư viện hỗ trợ:

• HashSet: Dựa trên băm, O(1) trung bình.
• LinkedHashSet: Giữ thứ tự nhập thêm.
• TreeSet: Sắp xếp phần tử (không lưu null).

Cơ Chế Bên Trong: Bảng Hash

Để đạt được hiệu suất gần như tức thì O(1) cho các phép tìm kiếm, ta cần ánh xạ địa chỉ nhớ dựa trên giá trị khóa. Hàm chuyển đổi này gọi là Hash Function.

Xử Lý Va Chạm

Do số lượng slot bộ nhớ hữu hạn, va chạm (Collision) xảy ra khi hai khóa khác nhau sinh ra cùng địa chỉ băm. Ta cần chiến lược xử lý:

1. Cấu trúc Đóng (Closed Addressing): Tìm slot trống gần đó (Linear Probing).
2. Cấu Trúc Mở (Open Addressing): Sử dụng danh sách liên kết tại mỗi ô mảng (Chaining).

Hàm Hash Ideal

Thiết kế hàm hash tốt giúp giảm thiểu va chạm. Phổ biến là phương pháp lấy dư số nguyên tố (key % primeNumber). Khi tải dữ liệu tăng quá ngưỡng (Load Factor), cần mở rộng dung lượng mảng để đảm bảo hiệu năng.

Mô Phỏng Thực Thi Cấu Trúc Bucket

Để hiểu sâu, chúng ta hãy tự xây dựng một bộ chuyển đổi Key-Value thô sơ sử dụng kỹ thuật Chain (Liên kết chuỗi) để giải quyết xung đột. Dưới đây là phiên bản tổng quát hóa.

public class CustomHashTable<K, V> {
    private static class PairNode<K, V> {
        K kKey;
        V vValue;
        PairNode<K, V> nextNode;

        public PairNode(K k, V v) {
            this.kKey = k;
            this.vValue = v;
        }
    }

    private PairNode<K, V>>[] buckets;
    private int countSize;
    private double limitFactor = 0.75;
    private int thresholdResize;

    @SuppressWarnings("unchecked")
    public CustomHashTable() {
        int cap = 4; 
        buckets = (PairNode[]) new PairNode[cap];
        thresholdResize = (int)(cap * limitFactor);
    }

    public void updateValue(K key, V value) {
        int index = getIndex(key);
        PairNode cur = buckets[index];
        
        // Kiểm tra trùng lặp
        while (cur != null) {
            if (key.equals(cur.kKey)) {
                cur.vValue = value;
                return;
            }
            cur = cur.nextNode;
        }

        // Thêm mới đầu hàng đợi
        PairNode newNode = new PairNode<>(key, value);
        newNode.nextNode = buckets[index];
        buckets[index] = newNode;
        countSize++;

        if (countSize > thresholdResize) {
            expandSize();
        }
    }

    public V retrieve(K key) {
        int index = getIndex(key);
        PairNode cur = buckets[index];
        while (cur != null) {
            if (key.equals(cur.kKey)) {
                return cur.vValue;
            }
            cur = cur.nextNode;
        }
        return null;
    }

    private int getIndex(K key) {
        if (key == null) return 0;
        int hash = key.hashCode();
        return (buckets.length - 1) & (Math.abs(hash)); 
    }

    private void expandSize() {
        PairNode[] oldBuckets = buckets;
        int newSize = oldBuckets.length * 2;
        buckets = (PairNode[]) new PairNode[newSize];
        thresholdResize = (int)(newSize * limitFactor);

        // Di chuyển lại toàn bộ data sang mảng mới
        for (PairNode head : oldBuckets) {
            PairNode cur = head;
            while (cur != null) {
                PairNode temp = cur.nextNode;
                int newIndex = getIndex(cur.kKey);
                
                // Đưa vào mảng mới (đầu hàng)
                cur.nextNode = buckets[newIndex];
                buckets[newIndex] = cur;
                
                cur = temp;
            }
        }
    }
}