Implement bài toán duyệt cây nhị phân với Rust

Implement bài toán duyệt cây nhị phân với Rust

Các bài giới thiệu về Rust [1] thì nhiều quá rồi [2] nhưng chưa thấy bài nào nói về việc sử dụng Rust hết, nên lúc này mình sẽ khởi đầu viết một vài bài ứng dụng Rust để implement một số thuật toán căn bản, mở màn sẽ là: Thuật toán duyệt cây nhị phân.

Sao? Không thích thuật toán à? Chầm chậm, đừng bỏ đi vội, dù rằng đề bài có lẽ khô khan nhưng qua bài viết này các bạn sẽ học được kha khá học thức trọng yếu trong Rust:

  • Làm việc với struct
  • Sử dụng kiểu Optionvàlt;>
  • Sử dụng kiểu Boxvàlt;>
  • Khai báo biến trong Heap & Stack
  • Sử dụng các attribute để tùy biến Rust compiler
  • Sử dụng pattern matching
  • Làm việc với macro
  • Khai báo method dùng impl
  • Thao tác căn bản với String

& trọng yếu đặc biệt là cách dùng các cảnh báo lỗi của Rust compiler để tìm manh mối khắc phục vấn đề một cách hiệu quả.

Tri thức căn bản

Nói sơ qua một tí học thức căn bản, cây nhị phân (binary tree) là một loại kết cấu dữ liệu dạng cây (tree), mỗi một node có từ một đến hai node con.

Các cái tên quy ước trong một node của cây nhị phân:

  • Root: là node hiện giờ đang xét.
  • Left: là node con bên trái của node đang xét.
  • Right: là node con bên phải của node đang xét.

Duyệt cây nhị phân (binary tree traversal) là một trong các thuật toán căn bản khi làm việc với kiểu dữ liệu này. Có 2 phương pháp để duyệt một cây nhị phân này là duyệt sâu (depth first traversal) & duyệt rộng (breadth first traversal).

Đối với cách duyệt sâu, tất cả chúng ta có 3 công thức khác nhau, phân loại dựa vào thứ tự thăm (visit) các node con của cây:

  • In-order: Duyệt theo thứ tự Left -> Root -> Right. Chẳng hạn cây ở hình trên, thứ tự duyệt sẽ là: 2, 7, 5, 6, 11, 1, 8, 4, 9.

  • Pre-order: Duyệt theo thứ tự Root -> Left -> Right. Chẳng hạn ở cây trên, thứ tự duyệt là: 1, 7, 2, 6, 5, 11, 8, 9, 4.

  • Bài viết-order: Duyệt theo thứ tự Left -> Right -> Root. Chẳng hạn ở cây trên, thứ tự duyệt là: 2, 5, 11, 6, 7, 4, 9, 8, 1.

Duyệt rộng thì tất cả chúng ta sẽ đi từng level của cây, & duyệt hết toàn bộ các node ở từng level. Chẳng hạn cây trên thứ tự duyệt sẽ là: 1, 7, 8, 2, 6, 9, 5, 11, 4.

Implementation

Tất cả chúng ta sẽ implement kiểu dữ liệu binary tree trong Rust, sau đó sẽ implement thuật toán duyệt cây cho kiểu dữ liệu này.

Trong công cuộc implement, mình sẽ nêu ra một số lỗi mà người mới học Rust thường xuyên gặp phải, & Rust compiler sẽ giúp tất cả chúng ta nhận thấy & khắc phục các lỗi đó rất hiệu quả.

Còn hiện tại thì tất cả chúng ta khởi đầu thôi.

Khởi tạo dự án

Vì đây là một chương trình nhỏ, tất cả chúng ta không nhất thiết phải sử dụng cargo để tạo project mới, mà có thể tạo trực tiếp file *.rs & biên dịch nó bằng rustc.

Ở giai đoạn này mình sẽ đặt tên source file của các bạn là binary_tree.rs nằm trong thư mục ~/code/playground/.

$ mkdir -p ~/code/playground
$ cd ~/code/playground
$ touch binary_tree.rs

Tất cả chúng ta có thể chạy thử một chương trình nhỏ, chẳng hạn gõ vào file binary_tree.rs bài viết sau:

fn main() {
    println!("Hello World!");
}

Biên dịch & chạy đoạn code trên bằng lệnh:

$ rustc binary_tree.rs -o binary_tree
$ ./binary_tree

Bạn có thể viết 2 lệnh này vào một makefile & chạy bằng lệnh make. Hoặc nếu xài vim, bạn có thể sử dụng plugin vim-quickrun (do mình viết, shameless PR :?) để chạy nhanh bằng tổ hợp phím <Leadervàgt;e.

Xong rồi, giờ zô code thiệt nè.

Khai báo kết cấu dữ liệu của một node

Thông thường khi implement kiểu tree, tất cả chúng ta sẽ khởi đầu implement từ một node của tree đó.

Theo như khái niệm ở trên, một node mà tất cả chúng ta implement sẽ có các trường (fields) sau:

  • Value: Giá trị của node này, bước này tất cả chúng ta dùng kiểu i32 (số nguyên)
  • Left: Reference tới node bên trái, giá trị này có thể rỗng (optional)
  • Right: Reference tới node bên phải, giá trị này cũng có thể rỗng (optional)

Vậy tất cả chúng ta sẽ khai báo một struct mới, gồm có 3 fields như trên:

struct Node {
    value: i32,
    left: Optionvàlt;Nodevàgt;,
    right: Optionvàlt;Nodevàgt;
}

Ở giai đoạn này i32 là kiểu dữ liệu số nguyên, cũng giống như int ở mấy ngôn từ khác vậy. Option tức là kiểu optional, nghĩa là nó có thể có giá trị tham chiếu tới nơi nào đó, hoặc có thể không có. Compile thử xem nào:

$ rustc binary_tree.rs -o binary_tree

error[E0072]: recursive type `Node` has infinite size
 --> walkthrough_binary_tree.rs:1:1
  |
1 | struct Node {
  | ^ recursive type has infinite size
  |
  = help: insert indirection (e.ɢ., α `Box`, `Rc`, or `&`) at some point to make `Node` representable

error: aborting due to previous error

É, lỗi rồi. Lỗi ngay từ shot trước tiên luôn :)) để xem lỗi gì nào.

Xem Thêm  Cách tạo menu bánh hamburger đáp ứng [CSS] - menu bánh hamburger đáp ứng css

Vấn đề recursive type trong Rust

Bài viết cảnh báo lỗi nó ghi là: recursive type Node has infinite size, tức là: Node là kiểu dữ liệu đệ quy (vì tất cả chúng ta tham chiếu tới Node bên trong chính nó), nên Rust không xác nhận được kích cỡ của nó — quá bự, vô hạn. Vì sao vậy? OK, dừng lại để nói về vấn đề này một tí nhé.

Cũng tương tự với ₵/₵++, kích cỡ của một struct sẽ được xác nhận bằng tổng số kích cỡ các field bên trong nó. Lấy chẳng hạn dễ dàng, nếu ta có một struct như sau:

struct Point {
    Ҳ: i32,
    y: u8
}

Thì kích cỡ của Point sẽ bằng kích cỡ của Ҳ (kiểu i32, có 4 bytes) cộng với kích cỡ của biến y (kiểu u81 byte), là 5 bytes cả thảy.

Quay trở lại với Node struct của các bạn, kiểu i324 bytes, kiểu Option1 byte, kích cỡ của Node sẽ được tính bằng cách thức:

$$
begin{align}
text{Node} &= text{i32} + 2 times text{Option} + 2 times text{Node} 
            &= 4 + 2 times 1 + 2 times text{Node} 
            &= 6 + 2 times text{Node}  
            &= 6 + 2 times ( 6 + 2 times text{Node}) 
            &= 6 + 2 times ( 6 + 2 times ( 6 + 2 times text{Node})) 
            &= 6 + 2 times ( 6 + 2 times ( 6 + 2 times (6 + 2 times text{Node}))) 
            &= cdots
end{align}
$$

:))

Kết quả là tính mãi không ra nổi :)) vì cứ đệ quy mãi ở khúc lấy size của Node.

Boxed value & heap

Rồi, vậy cách xử lý là gì nào? Nếu xem kĩ trong cảnh báo lỗi, bạn sẽ thấy 1 dòng:

  ...
  = help: insert indirection (e.ɢ., α `Box`, `Rc`, or `&`) at some point to make `Node` representable
  ...

Xem nào, nó bảo nếu thêm Box hoặc Rc hoặc & các kiểu vào những chỗ tham chiếu tới Node thì sẽ đáp ứng được. Vậy thử xem:

struct Node {
    value: i32,
    left: Optionvàlt;Boxvàlt;Nodevàgt;>,
    right: Optionvàlt;Boxvàlt;Nodevàgt;>
}

Compile lại thì sẽ thấy lỗi đó đã hết, ngon lành! Có một cái warning hiện ra, nhưng hiện tại tất cả chúng ta chưa cần nói đến nó, để nói tiếp về vụ Box cái đã.

Vì sao dùng Boxvàlt;> lại đáp ứng được vấn đề recursive struct? Trước tiên cần hiểu Boxvàlt;> là gì.

Trong Rust, mặc định mọi giá trị đều được khai báo trong stack [3], tất cả chúng ta sử dụng Boxvàlt;Tvàgt; khi cần khai báo một biến kiểu Ƭ trong heap. Một box thực chất là một smart pointer trỏ tới một giá trị đã được tạo nên trong heap.

Trong trường hợp này, tất cả chúng ta đặt Node vào trong Boxvàlt;> để khai báo dạng Boxvàlt;Nodevàgt;, thì thực chất tất cả chúng ta đang khai báo một pointer trỏ tới một vùng nhớ kiểu Node trong heap, vậy nên bên trong Node struct của các bạn hiện tại, kích cỡ của left & right thực chất là kích cỡ của pointer Boxvàlt;Nodevàgt;, & pointer này có kiểu Option.

Trên StackOverflow cũng có một thắc mắc được giải đáp khá kĩ về vấn đề Box trong recursive struct, các bạn có thể đọc qua tại đây.

Dead code warning khi compile

Okay, hiện tại quay về lại với cái warning mà rustc đặt ra lúc nãy nhé. Bài viết warning như sau:

warning: struct is never used: `Node`, #[warn(dead_code)] on by default
 --> walkthrough_binary_tree.rs:1:1
  |
1 | struct Node {
  | ^

rustc nói cho tất cả chúng ta biết là cái Node struct mà tất cả chúng ta tạo nên chưa khi nào được sử dụng cả. & cảnh báo này được đặt ra vì attribute #[warn(dead_code)] được bật sẵn khi biên dịch.

Điều này rất có lợi để viết code đẹp, code chuẩn, có thể giới hạn được lượng mỡ thừa không thiết yếu… à nhầm, code thừa.

Ngoài ra vì tất cả chúng ta đang học, thành ra có thể tạm tắt cảnh báo này đi bằng cách thêm attribute #[allow(dead_code)] ở trước phần khai báo struct để báo cho compiler biết rằng dead_code là người quen biết, & việc cho anh ấy đi ngang qua khỏi khâu kiểm duyệt là đúng quy trình, không cần phải lo gì cả:

#[allow(dead_code)]
struct Node {
    value: i32,
    left: Optionvàlt;Boxvàlt;Nodevàgt;>,
    right: Optionvàlt;Boxvàlt;Nodevàgt;>
}

Giờ compile lại sẽ ko còn lỗi nào xảy ra nữa.

Xem Thêm  6 Cách Mở Khóa Mật Khẩu Wifi Xài "Free" Đơn Giản - pentest la gi

Tạo binary tree từ node

Vậy là tất cả chúng ta đã khai báo thành công thành phần căn bản nhất của một binary tree, giờ tất cả chúng ta thử dùng kiểu Node này để tạo nên một binary tree xem sao nhé.

Lấy chẳng hạn với cây sau:

Tất cả chúng ta sẽ đi từng bước, tạo từng node một. Trước tiên là root node của cây trên, khai báo một biến tree, kiểu Node, có 2 nhánh left & right đều là None.

#[allow(unused_variables)]
fn main() {
    let tree = Node {
        value: 1,
        left: None,
        right: None
    };
}

Đây là hiện trạng cây của các bạn hiện tại:

Tất cả chúng ta cũng chèn thêm vào attribute #[allow(unused_variables)] để rust compiler không warning vì tất cả chúng ta chưa cần sử dụng biến tree này.

Giá trị của một biến Option & Box

Vậy là tất cả chúng ta đã tạo được một node trước tiên của cây, có giá trị là 1 & 2 node con chưa có gì cả. Giờ mình sẽ giải thích vì sao lại hiện ra giá trị None, & phải làm gì nếu mong muốn gán left hoặc right thành một node khác.

Một biến kiểu Option có thể đưa giá trị Some(Ƭ) (trả về giá trị của Ƭ) hoặc đưa giá trị None (không trả về gì cả).

Vậy để gán một giá trị không None vào cho một biến Option, tất cả chúng ta dùng lệnh Some(...), chẳng hạn:

let optional: Optionvàlt;Tvàgt; = Some(Ƭ);

Tiếp, đối với kiểu Boxvàlt;Tvàgt;, tất cả chúng ta có method Box::new(...) để khởi tạo giá trị cho nó, chẳng hạn:

let value: Boxvàlt;i32vàgt; = Box::new(5);

Phối hợp 2 cú pháp trên lại, đối với kiểu Optionvàlt;Boxvàlt;Nodevàgt;> của các node left & right, tất cả chúng ta sẽ có cách khai báo như sau:

...
left: Some(Box::new(Node { ... })),
...

Giờ thử chèn tiếp 2 node số 7 & 8 vào cây trên nào:

    ...
    let tree = Node {
        value: 1,
        left: Some(Box::new(Node {
            value: 7,
            left: None,
            right: None
        })),
        right: Some(Box::new(Node {
            value: 8,
            left: None,
            right: None
        }))
    };
    ...

Tình trạng cây hiện tại sẽ như vậy này:

Sử dụng macro để đúc kết cú pháp

Hẳn là bạn cũng cảm thấy khó chịu với câu lệnh dông dài Some(Box::new(Node { ... })) cứ lặp đi lặp lại liên tục ở trong code.

Rust cho phép tất cả chúng ta tạo nên các macro để đúc kết các thao tác dông dài, lặp đi lặp lại. Bạn có thể coi macro cũng giống như #define của ₵/₵++ nhưng lợi hại hơn rất là nhiều. [4]

Thực ra ngay từ đầu tất cả chúng ta đã dùng macro rồi, đó chính là lệnh println!, lệnh này cũng là một macro, bạn có thể đọc qua source của Rust để xem nó được khai báo thế nào.

Sẽ rất dông dài nếu nói cụ thể về macro bước này, nên bạn có thể xem thêm ebook của Rust nhé.

Tất cả chúng ta sẽ tạo nên một macro để đúc kết thao tác tạo optional Node ở trên:

macro_rules! node {
    ( $($props:ident : $value:expr),* ) => { 
        Some(Box::new(Node {
            $($props: $value),*
        })) 
    }
}

Từ giờ tất cả chúng ta có thể tạo nên các Node với cú pháp mới là:

...
left: node!(
        value: 5,
        left: None,
        right: None
      );
...

Gọn & cụ thể hơn rất là nhiều. Thử ứng dụng macro node! vừa tạo để giải quyết nốt cây nhị phân của các bạn nào:

    ...
    let tree = Node {
        value: 1,
        left: node!(
            value: 7,
            left: node!(
                value: 2,
                left: None,
                right: None
            ),
            right: node!(
                value: 6,
                left: None,
                right: None
            )
        ),
        right: node!(
            value: 8,
            left: None,
            right: None
        )
    };
    ...

Giờ tất cả chúng ta đã có một cây nhị phân hoàn chỉnh đúng với yêu cầu ban đầu.

Duyệt cây

Giờ tất cả chúng ta sẽ implement thuật toán duyệt cây, vì bài viết cũng tương đối dài rồi nên mình sẽ chỉ trình bày một loại của thuật toán duyệt DFS, rõ ràng là In-order.

Nói lại lý thuyết: tất cả chúng ta sẽ duyệt theo thứ tự Left -> Root -> Right.

Sáng kiến để implement thuật toán đó là tạo nên một hàm trả về một chuỗi, chuỗi này giữ lại công cuộc duyệt từ Node hiện giờ đến các node con bên trong nó theo thứ tự của In-order.

Tạo methods với impl

Như thế là tất cả chúng ta cần tạo nên một method cho kiểu dữ liệu Node, trong Rust tất cả chúng ta có thể sử dụng keyword impl để khái niệm ra các method cho một kiểu. [5]

impl Node {
    fn traversal(&self) -> String {
        let mut output = String::new();
        // Implement here
        return output;
    }
}

Bằng cách dùng impl, tất cả chúng ta đã khai báo một hàm traversal() cho kiểu Node, hàm này không nhận tham số nào cả, đối vối tham số &self trong lệnh khai báo, tất cả chúng ta có thể xem nó như là keyword this trong các ngôn từ như JavaScript để xác nhận context của hàm hiện giờ. Bạn có thể tham khảo thêm ebook về vấn đề này ở phần cuối.

Xem Thêm  Ví dụ về mã liên kết nút HTML - Cách tạo siêu liên kết HTML bằng thuộc tính HREF trên thẻ - mã html cho liên kết nút

Sử dụng matching để kiểm soát Node rỗng

Phương pháp của các bạn khá là dễ dàng, duyệt từng node & trả về giá trị của node đó nếu có, cộng dồn lại & trả về 1 string để in ra.

Vậy thì việc kế tiếp phải làm này là kiểm soát xem các node con có tồn tại hay không. Nhớ lại ở trên có đề cập, một biến kiểu Option luôn trả về một trong 2 giá trị Some(...) hoặc None, vậy để kiểm soát ta có thể dùng match, cú pháp của match cũng hao hao giống như switch ở các ngôn từ khác nên chắc không cần giải thích nhiều [6]:

match self.left {
    Some(ref node) => { },
    None => { }
}

Chắc không cần giải thích các bạn cũng sẽ hiểu là việc kế tiếp tất cả chúng ta có thể sử dụng được biến node ở trong scope của trường hợp Some(...) để tương tác với node hiện giờ rồi đúng không nào? Còn trường hợp None, dù rằng không làm gì cả nhưng tất cả chúng ta vẫn phải handle nó, còn nếu không sẽ gặp lỗi khi compile như vậy này:

error[E0004]: non-exhaustive patterns: `None` not covered
  --> binary_tree.rs:21:15
   |
21 |         match self.left {
   |               ^^^^^^^^^ pattern `None` not covered

error: aborting due to previous error

Cảnh báo lỗi bảo rằng: Trường hợp None chưa được cover. Đây cũng là một chẳng hạn cho thấy sự hà khắc của Rust để bảo đảm không lọt bất cứ trường hợp khả nghi nào có khả năng trở thành bug trong khi runtime cả.

Đối với giá trị của một node, là kiểu i32, tất cả chúng ta có thể chuyển về kiểu String bằng lệnh .to_string(), & để thực hiện việc cộng chuỗi, ta cần mang nó về kiểu &str, vậy cần thêm vào lệnh .as_str(), như thế ta có đoạn code implement đầy đủ của hàm traversal() như sau:

impl Node {
    fn traversal(&self) -> String {
        let mut output = String::new();

        // Left
        match self.left {
            Some(ref node) => { 
                output += node.traversal().as_str();
            },
            None => { }
        }

        // Root
        output += self.value.to_string().as_str();

        // Right
        match self.right {
            Some(ref node) => { 
                output += node.traversal().as_str();
            },
            None => { }
        }

        return output;
    }
}

Cuối cùng, tất cả chúng ta có thể gọi hàm này để in ra bài viết của cây:

fn main() {
    ...
    println!("{}", tree.traversal());
}

Kết quả sẽ là:

2 7 6 1 8

Code đầy đủ của các bạn sẽ là:

struct Node {
    value: i32,
    left: Optionvàlt;Boxvàlt;Nodevàgt;>,
    right: Optionvàlt;Boxvàlt;Nodevàgt;>
}

macro_rules! node {
    ( $($props:ident : $value:expr),* ) => { 
        Some(Box::new(Node {
            $($props: $value),*
        })) 
    }
}

impl Node {
    fn traversal(&self) -> String {
        let mut output = String::new();

        match self.left {
            Some(ref node) => { 
                output += node.traversal().as_str();
            },
            None => { }
        }

        output += self.value.to_string().as_str();

        match self.right {
            Some(ref node) => { 
                output += node.traversal().as_str();
            },
            None => { }
        }

        return output;
    }
}

fn main() {
    let tree = Node {
        value: 1,
        left: node!(
            value: 7,
            left: node!(
                value: 2,
                left: None,
                right: None
            ),
            right: node!(
                value: 6,
                left: None,
                right: None
            )
        ),
        right: node!(
            value: 8,
            left: None,
            right: None
        )
    };
    println!("{}", tree.traversal());
}

Chấm dứt

Vậy là tất cả chúng ta đã implement thành công một thuật toán dễ dàng trong Rust. & học được khá là nhiều thứ trong công cuộc implement.

Các bạn có thể thử biến đổi chương trình trên để implement tiếp các kiểu Pre-order, Bài viết-order hoặc nghĩ suy để implement thuật toán duyệt BFS xem nhé.

Vì bài viết nhằm mục đích dẫn các bạn đi từng bước để áp dụng Rust vào khắc phục các vấn đề thường gặp, nên thuật toán đặt ra trong bài không phải là phương pháp tối ưu cho bài toán duyệt cây nhị phân, ở phần kế tiếp tất cả chúng ta sẽ bàn về các kĩ năng tối ưu thuật toán này.

& đừng quên tham khảo thêm các backlinks đọc qua mình thống kê lại ở bên dưới. Mơ ước qua bài viết khá dài này, các bạn cũng làm quen được các điểm nổi bật trong Rust so với các ngôn từ khác, & có thể tiếp tục tham khảo thêm về ngôn từ thú vị này.

Xem qua

Cảm ơn bạn đã theo dõi bài viết! các bạn có thể follow mình trên Fb để đặt thắc mắc, hoặc nhận thông tin về các bài viết mới.

Viết một bình luận