Tìm trung vị của BST trong O(n) thời gian và O(1) không gian trong C++

Khái niệm

Cho cây tìm kiếm nhị phân (BST). Tìm trung vị.

• Số nút chẵn: trung vị = (n/2-th + (n+1)/2-th) / 2
• Số nút lẻ: trung vị = (n+1)/2-th

Ví dụ BST lẻ (7 nút): Inorder: 2,4,5,7,8,9,10 → trung vị = 7.

Ví dụ BST chẵn (6 nút): Inorder: 2,4,5,7,8,9 → trung vị = (5+7)/2 = 6.

Phương pháp Morris Inorder Traversal

Cần inorder của BST (đã sắp xếp) để tìm trung vị. Duyệt inorder đệ quy hoặc stack dùng không gian O(n) hoặc O(h). Yêu cầu O(1) không gian → dùng Morris Inorder Traversal.

Morris Inorder:

1. current = root
2. While current != NULL: - Nếu current không có con trái: xử lý current, current = current->right. - Ngược lại: tìm tiền nhiệm inorder (rightmost của left subtree), gán right của nó = current, current = current->left. - Khi quay lại (right của tiền nhiệm đã trỏ về current): gỡ link, xử lý current, current = current->right.

Triển khai tìm trung vị:

1. Đếm số nút bằng Morris Inorder.
2. Duyệt Morris Inorder lần 2, đếm nút, khi đếm bằng vị trí trung vị thì trả về giá trị. Với số chẵn, cần con trỏ prev lưu nút trước.

Ví dụ

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

struct Node1 {
    int data1;
    struct Node1 *left1, *right1;
};

Node1* newNode(int item1) {
    Node1* temp1 = new Node1;
    temp1->data1 = item1;
    temp1->left1 = temp1->right1 = NULL;
    return temp1;
}

Node1* insert(Node1* node1, int key1) {
    if (node1 == NULL) return newNode(key1);
    if (key1 < node1->data1)
        node1->left1 = insert(node1->left1, key1);
    else if (key1 > node1->data1)
        node1->right1 = insert(node1->right1, key1);
    return node1;
}

int counNodes(Node1* root1) {
    Node1 *current1, *pre1;
    int count1 = 0;
    if (!root1) return count1;
    current1 = root1;
    while (current1 != NULL) {
        if (current1->left1 == NULL) {
            count1++;
            current1 = current1->right1;
        } else {
            pre1 = current1->left1;
            while (pre1->right1 != NULL && pre1->right1 != current1)
                pre1 = pre1->right1;
            if (pre1->right1 == NULL) {
                pre1->right1 = current1;
                current1 = current1->left1;
            } else {
                pre1->right1 = NULL;
                count1++;
                current1 = current1->right1;
            }
        }
    }
    return count1;
}

int findMedian(Node1* root1) {
    if (!root1) return 0;
    int count1 = counNodes(root1);
    int currCount1 = 0;
    Node1 *current1 = root1, *pre1, *prev1 = NULL;
    while (current1 != NULL) {
        if (current1->left1 == NULL) {
            currCount1++;
            if (count1 % 2 != 0 && currCount1 == (count1 + 1) / 2)
                return current1->data1;
            else if (count1 % 2 == 0 && currCount1 == (count1 / 2) + 1)
                return (prev1->data1 + current1->data1) / 2;
            prev1 = current1;
            current1 = current1->right1;
        } else {
            pre1 = current1->left1;
            while (pre1->right1 != NULL && pre1->right1 != current1)
                pre1 = pre1->right1;
            if (pre1->right1 == NULL) {
                pre1->right1 = current1;
                current1 = current1->left1;
            } else {
                pre1->right1 = NULL;
                prev1 = pre1;
                currCount1++;
                if (count1 % 2 != 0 && currCount1 == (count1 + 1) / 2)
                    return current1->data1;
                else if (count1 % 2 == 0 && currCount1 == (count1 / 2) + 1)
                    return (prev1->data1 + current1->data1) / 2;
                prev1 = current1;
                current1 = current1->right1;
            }
        }
    }
}

int main() {
    // BST lẻ: 7,4,2,5,9,8,10
    Node1* root1 = NULL;
    root1 = insert(root1, 7);
    insert(root1, 4); insert(root1, 2); insert(root1, 5);
    insert(root1, 9); insert(root1, 8); insert(root1, 10);
    cout << "Trung vị BST (số lẻ nút): " << findMedian(root1) << endl;
    // BST chẵn: 7,4,2,5,9,8
    Node1* root2 = NULL;
    root2 = insert(root2, 7);
    insert(root2, 4); insert(root2, 2); insert(root2, 5);
    insert(root2, 9); insert(root2, 8);
    cout << "Trung vị BST (số chẵn nút): " << findMedian(root2);
    return 0;
}

Đầu ra

Trung vị BST (số lẻ nút): 7
Trung vị BST (số chẵn nút): 6