Cấu trúc dữ liệu cây: Khám phá Cây nhị phân tìm kiếm (BST)

Chào mừng bạn đến với bài viết thứ 7 trong chuỗi bài về cấu trúc dữ liệu và giải thuật. Hôm nay, chúng ta sẽ khám phá một cấu trúc dữ liệu phi tuyến tính vô cùng quan trọng: cây (Tree). Đặc biệt, chúng ta sẽ tập trung vào Cây nhị phân tìm kiếm (Binary Search Tree - BST).

Giới thiệu về cấu trúc dữ liệu cây

Cây là một cấu trúc dữ liệu phi tuyến tính. Nó mô phỏng cấu trúc phân cấp. Ví dụ như cây phả hệ, hệ thống thư mục trong máy tính. Cây bao gồm các nút (node) và các cạnh (edge). Các nút chứa dữ liệu. Các cạnh biểu diễn mối quan hệ giữa các nút.

Đặc điểm của cây:

• Có một nút gốc (root).
• Mỗi nút có thể có không hoặc nhiều nút con.
• Mỗi nút (trừ nút gốc) có duy nhất một nút cha.
• Không có chu trình (cycle).

Các khái niệm cơ bản về cây:

• Nút gốc (Root): Là nút trên cùng của cây. Nó không có nút cha.
• Nút cha (Parent): Là nút có một hoặc nhiều nút con.
• Nút con (Child): Là nút được liên kết với một nút cha.
• Nút lá (Leaf): Là nút không có nút con.
• Mức (Level): Là khoảng cách từ nút gốc đến một nút. Nút gốc có mức là 0.
• Chiều cao (Height): Là mức lớn nhất của bất kỳ nút nào trong cây.
• Cây con (Subtree): Là một phần của cây, bao gồm một nút và tất cả các hậu duệ của nó.

Cây nhị phân tìm kiếm (Binary Search Tree - BST)

Cây nhị phân tìm kiếm là một loại cây nhị phân đặc biệt. Nó tuân theo một quy tắc quan trọng: Với mỗi nút, tất cả các nút trong cây con bên trái của nó có giá trị nhỏ hơn giá trị của nút đó. Tất cả các nút trong cây con bên phải của nó có giá trị lớn hơn giá trị của nút đó.

Ví dụ:

Xét một cây nhị phân tìm kiếm có nút gốc là 8. Tất cả các nút bên trái 8 sẽ có giá trị nhỏ hơn 8. Tất cả các nút bên phải 8 sẽ có giá trị lớn hơn 8.

Ưu điểm của BST:

• Tìm kiếm, chèn và xóa các phần tử hiệu quả (trong trường hợp cây cân bằng).
• Dữ liệu được sắp xếp một cách tự nhiên.

Cài đặt BST trong Java:

class Node {
 int data;
 Node left, right;

 public Node(int data) {
 this.data = data;
 left = right = null;
 }
}

class BinarySearchTree {
 Node root;

 BinarySearchTree() {
 root = null;
 }

 // Chèn một nút vào BST
 void insert(int data) {
 root = insertRec(root, data);
 }

 Node insertRec(Node root, int data) {
 if (root == null) {
 root = new Node(data);
 return root;
 }

 if (data < root.data) {
 root.left = insertRec(root.left, data);
 } else if (data > root.data) {
 root.right = insertRec(root.right, data);
 } else {
 // Giá trị đã tồn tại, không chèn.
 }

 return root;
 }

 // Tìm kiếm một nút trong BST
 boolean search(int data) {
 return searchRec(root, data);
 }

 boolean searchRec(Node root, int data) {
 if (root == null) {
 return false;
 }

 if (data == root.data) {
 return true;
 }

 if (data < root.data) {
 return searchRec(root.left, data);
 } else {
 return searchRec(root.right, data);
 }
 }

 // Các phép duyệt cây (sẽ trình bày sau)
 }

Các phép duyệt cây

Duyệt cây là quá trình thăm tất cả các nút trong cây theo một thứ tự nhất định. Có ba phép duyệt cây chính:

1. Duyệt tiền thứ tự (Pre-order): Thăm nút gốc, sau đó duyệt cây con bên trái, rồi duyệt cây con bên phải.
2. Duyệt trung thứ tự (In-order): Duyệt cây con bên trái, sau đó thăm nút gốc, rồi duyệt cây con bên phải.
3. Duyệt hậu thứ tự (Post-order): Duyệt cây con bên trái, sau đó duyệt cây con bên phải, rồi thăm nút gốc.

Ví dụ với BST:

Cho một BST có cấu trúc như sau:

 4
 / \
 2 5
 / \
 1 3

• Pre-order: 4 2 1 3 5
• In-order: 1 2 3 4 5 (các nút được sắp xếp theo thứ tự tăng dần)
• Post-order: 1 3 2 5 4

Cài đặt các phép duyệt cây trong Java:

// Duyệt tiền thứ tự (Pre-order)
void preOrderTraversal(Node node) {
 if (node != null) {
 System.out.print(node.data + " ");
 preOrderTraversal(node.left);
 preOrderTraversal(node.right);
 }
}

// Duyệt trung thứ tự (In-order)
void inOrderTraversal(Node node) {
 if (node != null) {
 inOrderTraversal(node.left);
 System.out.print(node.data + " ");
 inOrderTraversal(node.right);
 }
}

// Duyệt hậu thứ tự (Post-order)
void postOrderTraversal(Node node) {
 if (node != null) {
 postOrderTraversal(node.left);
 postOrderTraversal(node.right);
 System.out.print(node.data + " ");
 }
}

Ứng dụng của các phép duyệt cây:

• Pre-order: Sao chép cây, biểu diễn biểu thức tiền tố.
• In-order: Sắp xếp các phần tử trong BST, biểu diễn biểu thức trung tố.
• Post-order: Xóa cây, biểu diễn biểu thức hậu tố.

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu về cấu trúc dữ liệu cây, đặc biệt là Cây nhị phân tìm kiếm (BST). Chúng ta đã nắm vững các khái niệm cơ bản như nút gốc, nút cha, nút con, nút lá, và các phép duyệt cây: tiền thứ tự, trung thứ tự, hậu thứ tự. Hãy tiếp tục khám phá các cấu trúc dữ liệu và giải thuật khác để nâng cao kỹ năng lập trình của bạn. Chúc bạn thành công!