In khóa BST trong khoảng [k1, k2] không gian O(1) - Morris Traversal C++

Giới thiệu

In tất cả khóa của BST nằm trong khoảng [k1, k2] theo thứ tự tăng dần, sử dụng Morris Traversal - duyệt inorder không dùng stack/queue, không gian O(1).

Morris Traversal (Threaded Binary Tree)

Ý tưởng: Tận dụng con trỏ NULL của node lá để trỏ về predecessor (node trước trong inorder). Tạo "thread" tạm thời, sau khi duyệt xong thì khôi phục.

Thuật toán

1. current = root
2. Khi current != NULL:
   • Nếu không có con trái: xử lý current, current = current->right
   • Nếu có con trái: tìm predecessor (node phải nhất của cây con trái)
     • Nếu predecessor->right == NULL: tạo thread về current, current = current->left
     • Nếu predecessor->right == current: xóa thread, xử lý current, current = current->right

Mã nguồn hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

void rangeTraversalMorris(Node* root, int k1, int k2) {
    Node* current = root;
    
    while (current) {
        if (!current->left) {
            // Xử lý node hiện tại
            if (current->data >= k1 && current->data <= k2) {
                cout << current->data << " ";
            }
            current = current->right;
        } else {
            // Tìm inorder predecessor
            Node* pred = current->left;
            while (pred->right && pred->right != current) {
                pred = pred->right;
            }
            
            if (!pred->right) {
                // Tạo thread
                pred->right = current;
                current = current->left;
            } else {
                // Xóa thread, xử lý current
                pred->right = nullptr;
                if (current->data >= k1 && current->data <= k2) {
                    cout << current->data << " ";
                }
                current = current->right;
            }
        }
    }
}

void inorderRecursive(Node* root, int k1, int k2) {
    if (!root) return;
    inorderRecursive(root->left, k1, k2);
    if (root->data >= k1 && root->data <= k2) cout << root->data << " ";
    inorderRecursive(root->right, k1, k2);
}

int main() {
    // Tạo BST:
    //       6
    //      / \
    //     3   8
    //    / \ / \
    //   1  4 7  9
    Node* root = new Node(6);
    root->left = new Node(3);
    root->right = new Node(8);
    root->left->left = new Node(1);
    root->left->right = new Node(4);
    root->right->left = new Node(7);
    root->right->right = new Node(9);
    
    int k1 = 4, k2 = 10;
    
    cout << "Morris Traversal (O(1) space): ";
    rangeTraversalMorris(root, k1, k2);
    cout << endl;
    
    cout << "Recursive Inorder (O(h) space): ";
    inorderRecursive(root, k1, k2);
    cout << endl;
    
    return 0;
}

Kết quả chạy chương trình

Morris Traversal (O(1) space): 4 6 7 8 9
Recursive Inorder (O(h) space): 4 6 7 8 9

Phân tích độ phức tạp

Ưu/nhược điểm Morris Traversal

• ✅ Không gian O(1) - không dùng stack/queue
• ✅ Không cấp phát bộ nhớ thêm
• ❌ Phức tạp hơn, khó debug
• ❌ Thay đổi tạm thời cấu trúc cây (tạo thread)
• ❌ Không thread-safe

Khi nào dùng Morris?

• Hệ thống nhúng, bộ nhớ cực hạn
• Cây rất sâu (tránh stack overflow)
• Face-to-face interview (thể hiện kiến thức sâu)

Kết luận

Morris Traversal là kỹ thuật tinh vi duyệt cây không dùng stack. Tuy không phổ biến trong production code, nhưng là bài phỏng vấn kinh điển thể hiện hiểu sâu về con trỏ và cấu trúc cây.