Пересечение двух бинарных деревьев поиска

Привет, Итак, я хочу создать новое дерево, которое в основном представляет собой пересечение (математическое определение пересечения) двух заданных бинарных деревьев поиска. У меня есть метод, который распечатывает все узлы на определенном уровне дерева, и у меня есть метод, который может определить глубину дерева. Я пока вставляю свою работу, хотя она неполная, и я застрял с Логика. Помощь будет оценена.

    public static Bst<Customer> intersect (Bst<Customer> a, Bst<Customer> b){
    Bst<Customer> result = new Bst<Customer>();
    BTNode<Customer> cur1;
    BTNode<Customer> cur2;
    BTNode<Customer> cur3;
    cur1=a.root;
    cur2=b.root;
    cur3=result.root;
    int Resultdepth;
    if(a.maxDepth()<b.maxDepth())
        Resultdepth=a.maxDepth();
    else
        Resultdepth=b.maxDepth();

    if(cur1==null || cur2==null){ // Handeling the root case intially
        result = null;
    }
    else 
      cur3.item.set_account_id(cur1.item.get_accountid()+ cur2.item.get_accountid());

    cur1=cur1.left;
    cur2=cur2.left;
    cur3=cur3.left;       

    while(<some check>){

    }


    return result;

}


    public int maxDepth(){
        return mD(root);
    }

    int mD(BTNode<E> node){
       if (node==null) {
            return(0);
        }
       else {
            int lDepth = mD(node.left);
            int rDepth = mD(node.right);
            // use the larger + 1
            return(Math.max(lDepth, rDepth) + 1);
        }
    }

     // for printing the nodes at a particular level and giving the starting level
      public void PrintAt(BTNode<E> cur, int level, int desiredLevel) {
         if (cur == null) {
            return;
        }
         if (level == desiredLevel) {
             System.out.print(cur.item.toString() + "");
          }
         else {
             PrintAt(cur.left, level+1, desiredLevel);
             PrintAt(cur.right, level+1, desiredLevel);
          }
}

java algorithm binary-search-tree
person dawnoflife    schedule 20.04.2011    source источник
comment
Я не вижу ничего, связанного с пересечением в вашем коде...   -  person Hosam Aly    schedule 20.04.2011
comment
извините, я забыл ввести свой код. теперь он там.   -  person dawnoflife    schedule 20.04.2011
comment
Я настоятельно рекомендую вам не пытаться жестко запрограммировать максимальную глубину с помощью дискретных переменных, таких как cur1, cur2, cur3 и т. д. Ваше решение должно работать для всех случаев. Вы обнаружите, что решение общего случая также проще, чем решение, основанное на предположениях.   -  person BoffinBrain    schedule 20.04.2011

Ответы (4)


arrow_upward
3
arrow_downward

Вы должны пройти оба дерева по порядку одновременно и «синхронно».

Я бы предложил реализовать интерфейс Iterable для вашего класса. Затем вы получаете первые значения из обоих деревьев. Если они равны, поместите его в новое дерево и получите следующие значения от обоих итераторов. Если нет, повторяйте итератор с меньшими значениями до тех пор, пока полученное значение не будет не меньше последнего значения из другого итератора. Промыть и повторить.

person Landei    schedule 20.04.2011
comment
Я бы тоже так поступил. Я не могу придумать более эффективного решения (за исключением, возможно, если бы вы знали больше о средней плотности данных, вы могли бы комбинировать базовый обход дерева с частичным двоичным поиском, когда вы сталкиваетесь с достаточно большим пробелом). - person BoffinBrain; 20.04.2011
comment
хм, я действительно не знаю, как реализовать итерируемый класс, но я кое-что закодировал и в настоящее время отлаживаю его. Я разместил здесь новый вопрос ‹stackoverflow.com/questions/5735806/ › - person dawnoflife; 20.04.2011

arrow_upward
0
arrow_downward

Пересечение двух деревьев - это предположительно узлы, которые есть в обоих деревьях?

Учитывая, что для этого вам придется исследовать дерево, почему бы просто не выполнить обход по порядку, сохранить узлы, а затем выполнить операцию пересечения упорядоченных списков?

person Jeff Foster    schedule 20.04.2011
comment
Джефф, да, это пересечение узлов в двух деревьях. Я действительно не хочу использовать списки в этом случае. Я знаю, что это можно сделать с помощью условных проверок, и я надеюсь, что смогу это сделать. - person dawnoflife; 20.04.2011

arrow_upward
0
arrow_downward

Мое предложение для такого пересечения простое:

Учитывая дерево A и дерево B, чтобы найти дерево C = A \intersect B:

1: Скопируйте либо дерево A, либо дерево B. Предположим, что A для ясности.
Эта копия теперь является вашим деревом C. Теперь давайте 'обрежем' его.
2: Для c = C.root_node и b = B. root_node:
if b==c,
Повторить процедуру с узлами b.left, c.left
Повторить процедуру с узлами b.right, c.right
else,
Удалить c (тем самым удаляя все последующие дочерние элементы, подразумевается, что они неравны)

Если эта реализация будет работать, она позволит избежать использования итераторов и тому подобного и сведется к простому рекурсивному обходу. (Нравится!)

Спросите, хотите ли вы получить дополнительные разъяснения.

С Уважением.

person Michael    schedule 20.04.2011
comment
зачем вы это делаете, если b==c. я не понимаю, чего вы пытаетесь добиться этим - person dawnoflife; 21.04.2011
comment
Я выбрал противоположный подход. Скопируйте ВСЕ, затем удалите разницу. - person Michael; 24.04.2011
comment
@Michael, допустим, есть два дерева A и B. A.root-›data = 5, A.root-›left-›data = 6, A.root-›right-›data = 8 B.root-›data = 5, B.root-›left-›data = 7, B.root-›right-›data = 8 В соответствии с вашим подходом не было бы пересечения - person Anubhav Agarwal; 03.11.2012

arrow_upward
0
arrow_downward

Для рекурсивной реализации поиска пересечения двух бинарных деревьев поиска я придумал следующий код. Я не очень уверен во временной сложности, но она работает нормально.

void BST::findIntersection (ячейка * root1, ячейка * root2) {

if(root1 == NULL ) { 
//  cout<<"Tree 1 node is null , returning"<<endl;  
    return;
}
if(root2 == NULL) {
//  cout<<"Tree 2 node is null , returning"<<endl;  
    return;
}
//cout<<"Comparing tree 1 : "<<root1->data<< "   and tree 2 : " << root2->data<<endl;
if(root1->data==root2->data) {
//  cout<<"tree 1 equal to tree 2 "<<endl;
    insert(root1->data);
//  cout<<"Inserting in new tree : "<<root1->data<<endl;
    findIntersection(root1->left,root2->left);
    findIntersection(root1->right, root2->right);
}
else if(root1->data>root2->data) {
//  cout<<"tree 1 > tree 2 "<<endl;
    findIntersection(root1,root2->right);
    findIntersection(root1->left, root2);
}
else  {
//  cout<<"tree 1 < tree 2 "<<endl;
    findIntersection(root1->right,root2);
    findIntersection(root1, root2->left);
}

}

person Rohit Agrawal    schedule 17.09.2012