c++ - 通过 "inorder"和 "reverse inorder"方法同时遍历二叉搜索树的多线程方法，比较元素对

Question

在一些情况下，能够比较二叉搜索树中的最后一个元素和第一个元素，元素对，将被证明是有用的。

例如:找到 2 个总和为给定数字的元素。 (最快的方法是尝试将最小和最大的数字相加，然后根据与给定数字的结果总和推进每一端)

^我知道这可以通过使用 2 个堆栈以迭代 方式遍历树来完成。我只是在想是否有一种方法可以使用 2 线程 来做这样的事情:

pthread_mutex_t MTree1, Mtree2;
pthread_t thread[2];
pthread_attr attr;
int data1, data2;
int tempInorder, tempRevInorder;
int requiredSUM

void mergBST(node*root)
{
    pthread_mutex_init(&Mtree1, NULL);
    pthread_mutex_init(&Mtree2, NULL);
    pthread_attr_setdetachestate(&attr,PTHREAD_CREATE_JOINABLE);

    pthread_create(&thread[0],&attr, mergeBSTImplInOrder, void*(root));
    pthread_create(&thread[1],&attr, mergeBSTImplRevInOrder, void*(root));

}

 void mergeBSTImplInOrder(void *root)
    {
        root=(node*) root;
        if(!root) return;

        mergeBSTImpl(root->left);

        tempInorder=root->data

            /*This is where there has to be conditional checks such that execution would stop right here so I can compare varables **tempInorder** **tempRevInorder** with the variable "requiredSUM"*/

        mergeBSTImpl(root->right);
    }


 void mergeBSTImplRevInOrder(void *root)
    {
        root=(node*) root;
        if(!root) return;
        mergeBSTImpl(root->right);

        tempRevInorder=root->data;
        //A similar situation as the other function.

        mergeBSTImpl(root->left);
    }

那么...我尝试做的事情在逻辑上是否可行？这是我在 stackoverflow 中的第一篇文章。我希望我把格式和事情弄对了。如果没有，请客气。 =)

堆栈方法至少占用O(logm + logn) 空间。线程方式实际上可以用更简单的代码和 O(1) 空间

来完成

以防万一，我要完成的是:

2 functions, each running it's own thread:
Fn1(say): One, a function that recurses in an Inorder fashion.
Fn2(say): Two, a function that recurses in a reverse Inorder fashion.

Each time either of the function reads data from the BST, it stores them in static variables, and it has to check if two elements saved from the 2 functions are there to compare. One from itself, the other from the other function. if there are 2 elements yet, then it finds the sum of the elements with requiredSUM. In case the sum of variable is bigger, it lets the other function continue till it gets the next one (which would be the second smallest element). This function stays till the other function gets its new element. Comparison takes place. If this time, the sum is smaller than requiredSUM, this function carries on and the other function waits till this function gets the next element (the 2nd smallest element). Comparison takes place and this goes on till the 2 elements summing to the required target Sum is found.

这是一种算法，用于查找排序数组中总和为指定值的所有整数对。除了 我们现在有 BST 而不是排序数组。只是为了展示，我将通过以下方式解决问题的数组版本:

#include <iostream>
#include <algorithm>

using namespace std;

void print_pairs(int * ptr, int num, int sum) 
{
    std::sort(ptr, ptr + num);
    int first = 0;
    int last = num - 1;

    while (first < last) 
    {
        int s = ptr[first] + ptr[last];
        if (s == sum) 
        {
            //cout<<ptr[first]<<“ “<< ptr[last]<<endl;
            ++first;
            --last;
        }
        else 
        {
            if (s < sum) 
                ++first; 
            else 
                --last;
        }
    }
}

int main() 
{
int test[] = {9, 3, 6, 5, 7, -1, 13, 14, -2, 12, 0};
print_pairs(test, sizeof(test) / sizeof(int), 12);
return 0;
}

Answer 1

我的感觉是线程 不能解决您的问题。保持前后遍历状态的两个游标状态或类似迭代器的对象将为您提供相同的结果。

线程是一种协调执行的方式，而不是一种分割代码的方式。在任何情况下，您都应该尽可能避免使用线程，在这种情况下(线程永远不会同时运行)，线程不会为解决方案增加值(value)

如果你硬要说，那你要的就是条件变量。

条件是一个线程将阻塞直到其他线程发出继续信号的位置。条件链接到互斥量。

所以在 thread1 上你会:

thread1stopped=false; // let this start running
while (true) {
    pthread_mutex_lock(&mutex2); // lock on the other thread mutex
    while(!thread2stopped) {
        pthread_cond_wait(&cond2, &mutex2); // wait for the signal
    }
    pthread_mutex_unlock(&mutex2); // unlock the other thread mutex

    // Now we're running:
    // ... do whatever I need to do
    // ... until I need to stop.
    pthread_mutex_lock(&mutex1); // lock my mutex
    thread1stopped=true;         // change the state
    pthread_cond_signal(&cond1); // signal to the other thread
    pthread_mutex_unlock(&mutex1); // unlock my mutex
    pthread_mutex_lock(&mutex1); // lock my mutex
    thread1stopped=false;
    pthread_mutex_unlock(&mutex1); // unlock my mutex
 }

另一个可以

thread2stopped=true; // let this start stopped
while (true) {
    pthread_mutex_lock(&mutex1); // lock on the other thread mutex
    while(!thread1stopped) {
        pthread_cond_wait(&cond1, &mutex1); // wait for the signal
    }
    pthread_mutex_unlock(&mutex1); // unlock the other thread mutex

    // Now we're running:
    // ... do whatever I need to do
    // ... until I need to stop.
    pthread_mutex_lock(&mutex2); // lock my mutex
    thread2stopped=true;         // change the state
    pthread_cond_signal(&cond2); // signal to the other thread
    pthread_mutex_unlock(&mutex2); // unlock my mutex
    pthread_mutex_lock(&mutex2); // lock my mutex
    thread2stopped=false;
    pthread_mutex_unlock(&mutex2); // unlock my mutex
 }

这个有效:

  Thread1             Thread2
      .                   .
   --------           --------
   | exec |           | lock1| thread1stopped==false
   |      |           | wait | (wait unlocks)
   --------           |      |
      .               |      |
   --------           |      |
   |lock1 |           |      |
   |true  |           |      |
   |signal|---------->|unlock|
   --------           --------
      .                   .
   --------           --------
   | lock2|           | exec |
   | wait |           |      |
   |      |           --------
   |      |               .
   |      |           --------
   |      |           |lock2 |
   |      |           |true  |
   |unlock|<----------|signal|
   --------           --------

还没有真正尝试过这段代码，所以可能存在问题、死锁、竞争条件......但我希望它能给你一个起点。