[Bài đọc] Tree và Binary Tree

Tổng quan
Hoàng Dư Thanh
15-06-2020

Các cấu trúc dữ liệu thông thường xử lý 3 thao tác cơ bản:

  • insertion – các thao tác thêm dữ liệu vào cấu trúc
  • deletion – các thao tác loại bỏ dữ liệu khỏi cấu trúc
  • traversal – các thao tác để duyệt (nhận về) dữ liệu từ cấu trúc

Trong trường hợp của Stack và Queue thì các thao tác này được thực hiện căn cứ vào vị trí (position) của các phần tử. Như vậy, chúng ta sẽ làm gì nếu muốn thực hiện các thao tác này mà không dựa vào vị trí mà dựa vào chính giá trị của các phần tử đó.

Hãy xem xét một danh sách các phần tử sau (được đặt theo một trật tự ngẫu nhiên):

Trong trường hợp này, có thể dễ dàng nhận thấy rằng cả Stack hay Queue đều không phù hợp để lưu trữ các dữ liệu như thế này. Có thể chúng ta sẽ phải duyệt qua toàn bộ cấu trúc chỉ để tìm ra một phần tử, nếu phần tử đó nằm ở cuối cùng trong danh sách. Danh sách càng dài, thì thời gian chúng ta cần để tìm kiếm một phần tử càng lâu. Trong trường hợp này, chúng ta cần sử dụng những cấu trúc dữ liệu khác, cho phép việc tìm kiếm được diễn ra nhanh hơn, đây chính là lúc mà cấu trúc cây (tree) thể hiện được ưu điểm của nó.

Chúng ta có thể hình dung các thao tác với “bảng” dữ liệu ở trên bao gồm:

  • create – tạo một bảng rỗng.
  • insert – thêm một phần tử vào bảng.
  • delete – xoá một phần tử khỏi bảng.
  • retrieve – lấy về một phần tử từ bảng.

Một cách đơn giản để biểu diễn “bảng” này là theo trật tự tuyến tính (linear), giống như là một danh sách bình thường. Việc triển khai danh sách này có thể theo hình thức tuyến tính (sử dụng mảng) hoặc liên kết (như LinkedList).

Nhược điểm của cách triển khai tuyến tính đó là rất hao tốn tài nguyên trong những thao tác thêm và xoá dữ liệu, trong khi đó cách triển khai liên kết (linked) thì cho phép việc cấp phát ngẫu nhiên. Tuy nhiên, việc tìm kiếm thì cấu trúc tuyến tính lại tốt hơn so với cấu trúc liên kết.

Cấu trúc cây (tree)

Cấu trúc Tree cho phép chúng ta tận dụng ưu điểm của cả 2 cấu trúc tuyến tính (linear) và liên kết (linked). Do vậy, cấu trúc Tree được sử dụng rất nhiều trong các hệ quản trị cơ sở dữ liệu để hỗ trợ cho việc đánh chỉ mục, giúp cho thao tác truy vấn dữ liệu được nhanh hơn.

Chúng ta có thể thấy rằng cấu trúc Tree hoạt động theo nguyên tắc phân cấp, trong đó có mối quan hệ cha-con giữa các nút (node). Node mà không có cha thì được gọi là root (nút gốc), node mà không có con thì được gọi là leaf (nút lá). Những node có chung cha thì được gọi là siblings (anh em). Khái niệm edges (cạnh) được dùng để chỉ đến đường kết nối giữa các node.

Cấu trúc Tree đơn giản nhất đó là cấu trúc mà ở đó mỗi node chỉ có nhiều nhất là 2 node con, loại này thường được gọi là Cây nhị phân (binary tree). Chúng ta có thể xây dựng một cây nhị phân đơn giản như sau:

Lớp BinaryNode đại diện cho một node ở trong Tree:

<?php
class BinaryNode
{
    public $value;    // contains the node item
    public $left;     // the left child BinaryNode
    public $right;     // the right child BinaryNode

    public function __construct($item) {
        $this->value = $item;
        // new nodes are leaf nodes
        $this->left = null;
        $this->right = null;
    }
}

Thuộc tính $value chứa giá trị của node, thuộc tính $left trỏ đến node con bên trái, thuộc tính $right trỏ đến node con bên phải.

Lớp BinaryTree:

class BinaryTree
{
    protected $root; // the root node of our tree

    public function __construct() {
        $this->root = null;
    }

    public function isEmpty() {
        return $this->root === null;
    }
}

Thêm node vào trong Tree

Có một số cách khác nhau để thêm các node vào cho Tree, mỗi cách làm đều có thể có những ưu/nhược điểm khác nhau liên quan đến hiệu năng của các thao tác thêm/xoá/duyệt cây.

Để cho dễ hiểu, chúng ta hãy xem xét một ví dụ đơn giản dựa trên mã giả (pseudocode):

  1. Nếu cây rỗng (empty) thì chèn new_node thành root node (nút gốc)
  2. Nếu cây không rỗng
  • Nếu (current_note rỗng), chèn phần tử new_node vào đây và dừng lại;
  • Còn không thì nếu (new_node > current_node), thử chèn phần tử new_node vào phía bên phải (sau đó lặp lại bước 2)
  • Còn không thì nếu (new_node < current_node), thử chèn phần tử new_node vào phía bên trái (sau đó lặp lại bước 2)
  • Còn không thì có nghĩa là new_node đã có sẵn trong tree rồi

Đây là một cách triển khai đơn giản, theo chiến thuật “chia để trị”. Tất cả những phần tử nhỏ hơn phần tử hiện tại thì chuyển sang bên trái, tất cả những phần tử lớn hơn thì chuyển sang bên phải, tất cả những phần tử trùng lặp (đã tồn tại trước đó) thì sẽ bị từ chối (không thêm vào). Chúng ta cũng dễ dàng thấy rằng chiến thuật như vậy rất phù hợp với thuật toán đệ quy (recursive), bởi vì mỗi nhánh của tree sẽ là một sub-tree (cây con).

<?php
class BinaryTree
{
...
    public function insert($item) {
        $node = new BinaryNode($item);
        if ($this->isEmpty()) {
            // special case if tree is empty
            $this->root = $node;
        }
        else {
            // insert the node somewhere in the tree starting at the root
            $this->insertNode($node, $this->root);
        }
    }
  
    protected function insertNode($node, &$subtree) {
        if ($subtree === null) {
            // insert node here if subtree is empty
            $subtree = $node;
        }
        else {
            if ($node->value > $subtree->value) {
                // keep trying to insert right
                $this->insertNode($node, $subtree->right);
            }
            else if ($node->value < $subtree->value) {
                // keep trying to insert left
                $this->insertNode($node, $subtree->left);
            }
            else {
                // reject duplicates
            }
        }
    }
}

Duyệt qua các phần tử của tree

Chúng ta có một số chiến lược khác nhau để xuất phát từ root node và duyệt qua lần lượt từng node một của tree:

  • pre-order – duyệt node hiện tại rồi sau đó sang cây bên trái và cây bên phải
  • in-order (đối xứng) – duyệt bên trái trước, sau đó duyệt node hiện tại, rồi duyệt node bên phải
  • post-order – duyệt bên trái trước, sau đó bên phải, rồi duyệt node hiện tại
  • level-order (duyệt theo bề rộng) – duyệt node hiện tại, sau đó duyệt tất cả các node anh em (siblings), rồi chuyển sang duyệt những node ở level tiếp theo

Chiến lược đầu tiên còn được gọi là depth-first (duyệt theo chiều sâu), trong đó chúng ta bắt đầu ở root node (hoặc bất cứ node nào được gán làm root node), sau đó duyệt đến level càng sâu càng tốt, trước khi quay ngược trở lại.

Mỗi một chiến lược ở trên đều phù hợp cho những tình huống riêng, chẳng hạn chiến lược pre-order phù hợp cho tình huống chèn node hoặc sao chéo các sub-tree. Chiến lược in-order thì thường được dùng trong tìm kiếm nhị phân, trong khi post-order thì được dùng để xoá node.

Để minh hoạ cho chiến lược in-order, chúng ta thử thay đổi một chút mã nguồn ở trên.

<?php
class BinaryNode
{
...
    // perform an in-order traversal of the current node
    public function dump() {
        if ($this->left !== null) {
            $this->left->dump();
        }
        var_dump($this->value);
        if ($this->right !== null) {
            $this->right->dump();
        }
    }
}

class BinaryTree
{
...
    public function traverse() {
        // dump the tree rooted at "root"
        $this->root->dump();
    }
}

Bây giờ, nếu chúng ta gọi phương thức traverse() thì sẽ nhận được lần lượt các node theo trật tự bắt đầu từ root node.

Kết luận

Trong phần này, chúng ta chỉ mới đề cập nhiều đến dạng đơn giản nhất của cấu trúc cây, đó là cây nhị phân. Đối với cấu trúc cây nói chung, còn rất nhiều các thuật toán khác cần triển khai để có thể đáp ứng được các thao tác thông thường, và đảm bảo được một hiệu năng tốt cho các thao tác đó.

Leave a Reply

Your email address will not be published.