3

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

例如：查找 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 上的第一篇文章。我希望我的格式和事情是正确的。如果不是，请善待。=)

stack 方法至少占用O(logm + logn) 空间。线程方式实际上可以通过更简单的代码和 O(1) 空间来完成

以防万一，我想要完成的是：

2 个函数，每个都运行它自己的线程：
Fn1（比如说）：一个，一个以 Inorder 方式递归的函数。
Fn2（比方说）：二，一个以逆序方式递归的函数。

每次任何一个函数从 BST 读取数据时，它都会将它们存储在静态变量中，并且它必须检查从 2 个函数中保存的两个元素是否可以进行比较。一个来自自身，另一个来自另一个功能。如果还有 2 个元素，则使用 requiredSUM 找到元素的总和。如果变量的总和更大，它会让另一个函数继续，直到它得到下一个（这将是第二小的元素）。这个函数一直存在，直到另一个函数得到它的新元素。进行比较。如果这次总和小于 requiredSUM，则该函数继续执行，另一个函数等待直到该函数获得下一个元素（第二小的元素）。进行比较，直到找到总和为所需目标 Sum 的 2 个元素。

这是一种算法，用于查找排序数组中总和为指定值的所有整数对。除了不是排序数组，我们现在有一个 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]<<“ “&lt;< 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;
}
4

1 回答 1

2

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

线程是一种协调执行的方式，而不是一种打包代码的方式。在任何情况下，您都应该尽可能避免使用线程，这是一种情况（线程从不同时运行），线程不会为解决方案增加价值

如果你坚持，那么你想要的是条件变量。

条件是一个线程将阻塞直到其他线程发出信号继续的地方。条件与互斥锁相关联。

所以在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|
   --------           --------

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

于 2015-03-06T15:04:45.260 回答