W dniu 15.03.2018 o 18:43, M.M. pisze:
> Jakich cech brakuje Ci w standardowych implementacjach drzew, że
> implementujesz po swojemu?

Elementy różnych typów, podmiana elementu na podgałąź

do góry

On Thursday, March 15, 2018 at 7:31:14 PM UTC+1, Borneq wrote:
> W dniu 15.03.2018 o 18:43, M.M. pisze:
> > Jakich cech brakuje Ci w standardowych implementacjach drzew, że
> > implementujesz po swojemu?
>
> Elementy różnych typów,
Np. jakich typów?

> podmiana elementu na podgałąź

Potrzebujesz drzewa z wyważaniem czy bez?

Pozdrawiam

do góry

W dniu 15.03.2018 o 22:15, M.M. pisze:
> Np. jakich typów?
>
>> podmiana elementu na podgałąź
>
> Potrzebujesz drzewa z wyważaniem czy bez?

To zupełnie co innego niż AVL, drzewa czerwono-czarne,itp.
Drzewa bez wyważania, coś takiego jak AST do trzymania wyrażeń
arytmetycznych, zwykle Lisp czy Closure się do tego nadaje.
Na przykład teraz zobaczyłem że źle zrobiłem klonowanie: teraz jak
podczepiam poddrzewko to wchodzi wgłąb niego i klonuje w razie potrzeby.
Może być zapętlenie gdy do drzewa w pewnym miejscu podczepiam całe
drzewo. Radzę sobie przez ustawienie znacznika, i w ten sposób przerywam
z błędem. Ale nie chcę przerywać z błędem tylko nie klonować w razie
potrzeby po jednym, tylko najpierw sklonować całe drzewko (obiekty
różnych typów,kopiowanie danych ale linki dzieci-ojciec odpowiednio się
zmienią na nowe obiekty) a potem je podczepić.

do góry

On Thursday, March 15, 2018 at 10:41:22 PM UTC+1, Borneq wrote:
> W dniu 15.03.2018 o 22:15, M.M. pisze:
> > Np. jakich typów?
> >
> >> podmiana elementu na podgałąź
> >
> > Potrzebujesz drzewa z wyważaniem czy bez?
>
> To zupełnie co innego niż AVL, drzewa czerwono-czarne,itp.
> Drzewa bez wyważania, coś takiego jak AST do trzymania wyrażeń
> arytmetycznych, zwykle Lisp czy Closure się do tego nadaje.
> Na przykład teraz zobaczyłem że źle zrobiłem klonowanie: teraz jak
> podczepiam poddrzewko to wchodzi wgłąb niego i klonuje w razie potrzeby.
> Może być zapętlenie gdy do drzewa w pewnym miejscu podczepiam całe
> drzewo. Radzę sobie przez ustawienie znacznika, i w ten sposób przerywam
> z błędem. Ale nie chcę przerywać z błędem tylko nie klonować w razie
> potrzeby po jednym, tylko najpierw sklonować całe drzewko (obiekty
> różnych typów,kopiowanie danych ale linki dzieci-ojciec odpowiednio się
> zmienią na nowe obiekty) a potem je podczepić.

Jest to na tyle łatwe, że można szybko samemu zrobić. Moja implementacja
drzewek czerwono czarnych trochę czasu mi zajęła, ale ma kilka dodatkowych
bajerów, no i samo wyważanie wymaga trochę wysiłku.

Wracając do pierwszego pytania, jak usuwać węzeł. Usuwa się po prostu,
przez zwolnienie pamięci. Ale jeśli węzeł ma dzieci, to nie można ich
zgubić. Co zrobić z dziećmi? Zależy od zastosowania.

Hmmm a po co usuwasz węzeł w drzewie do reprezentacji wyrażeń
arytmetycznych?

Pozdrawiam

do góry

W dniu 15.03.2018 o 23:00, M.M. pisze:
> Hmmm a po co usuwasz węzeł w drzewie do reprezentacji wyrażeń
> arytmetycznych?

Po to by zastąpić zmienną całym wyrażeniem.
Coś takiego:
ma symbolicznie robić operację postawiania:
na przykład gdy liczymy pierwiastek z n to ze wzoru (wybierając x
początkowe)
x:= (x+n/x)/2
druga iteracja, podstawiamy wszędzie gdzie x całe wyrażenie:
otrzymujemy ((x+n/x)/2+n/((x+n/x)/2))/2
możemy dalej
(((x+n/x)/2+n/((x+n/x)/2))/2+n/(((x+n/x)/2+n/((x+n/x
)/2))/2))/2

Działa już klonowanie (można podczepić całe drzewko do swojej podgałęzi,
jeszcze nie mam tu replace- jest innej wersji , gdzie nie działało
klonowanie), trzeba dorobić dziedziczenie:
#include <memory>
#include <string>
#include <vector>
#include <assert.h>

using namespace std;

class Node
{
vector<shared_ptr<Node>> childs;
Node* parent = nullptr;//not shared_ptr! because of memory leaks of
circular dependency
int level = 0;
public:
string name;
Node(string name)
{
this->name = name;
}
~Node()
{
printf("delete %s\n",name.c_str());
}
shared_ptr<Node> cloneOne()
{
shared_ptr<Node> result = make_shared<Node>(name+"a");
return result;
}

shared_ptr<Node> cloneTree()
{
shared_ptr<Node> newElem = cloneOne();
for (size_t i = 0; i<childs.size(); i++)
{
shared_ptr<Node> subElem = childs[i]->cloneTree();
newElem->AddOneChild(subElem);
}
return newElem;
}

void erase()
{
printf("erase from %s\n", name.c_str());
childs.clear();
}
void deleteChild(int index)
{
printf("delete child %d from %s - %s\n", index, name.c_str(),
childs[index]->name.c_str());
childs.erase(childs.begin()+index);
}

void setLevel(int level)
{
this->level = level;
for (size_t i = 0; i<childs.size(); i++)
childs[i]->setLevel(level+1);
}

void AddOneChild(shared_ptr<Node> node)
{
childs.push_back(node);
node->parent = this;
}

void AddTree(shared_ptr<Node> node)
{
shared_ptr<Node> clone = node->cloneTree();
AddOneChild(clone);
clone->setLevel(level+1);
}
shared_ptr<Node>& at(int index)
{
return childs[index];
}
void print()
{
for (int i = 0; i<level; i++)
printf(" ");
printf("%s->",name.c_str());
if (parent) printf("%s", parent->name.c_str());
printf("\n");
for (size_t i=0; i<childs.size(); i++)
childs[i]->print();
}
};

int main()
{
shared_ptr<Node>root,rootB;
root = make_shared<Node>("1");
root->AddTree(make_shared<Node>("2"));
root->AddTree(make_shared<Node>("3"));
root->at(0)->AddTree(make_shared<Node>("4"));
root->at(0)->AddTree(make_shared<Node>("5"));
root->at(1)->AddTree(make_shared<Node>("6"));
root->at(1)->AddTree(make_shared<Node>("7"));
root->at(1)->AddTree(root);
root->print();
return 0;
}

do góry

Replace:
nie można najpierw usuwać a potem dodawać , bo w międzyczasie zmieniłoby
się drzewo. Trzeba sklonować, potem usunąć i wstawić.
void InsertOneChild(int index, shared_ptr<Node> node)
{
childs.insert(childs.begin() + index, node);
node->parent = this;
}

void ReplaceChild(int index, shared_ptr<Node> subtree)
{
shared_ptr<Node> clone = subtree->cloneTree();
deleteChild(index);
InsertOneChild(index, clone);
clone->setLevel(level + 1);
}


int main()
{
shared_ptr<Node>root,rootB;
root = make_shared<Node>("1");
root->AddTree(make_shared<Node>("2"));
root->AddTree(make_shared<Node>("3"));
root->at(0)->AddTree(make_shared<Node>("4"));
root->at(0)->AddTree(make_shared<Node>("5"));
root->at(1)->AddTree(make_shared<Node>("6"));
root->at(1)->AddTree(make_shared<Node>("7"));
root->print();
root->ReplaceChild(0,root);
root->print();
return 0;
}

do góry

On Thursday, March 15, 2018 at 11:46:10 PM UTC+1, Borneq wrote:
> W dniu 15.03.2018 o 23:00, M.M. pisze:
> > Hmmm a po co usuwasz węzeł w drzewie do reprezentacji wyrażeń
> > arytmetycznych?
>
> Po to by zastąpić zmienną całym wyrażeniem.

Zastanów się, czy na stosie tego nie można zrobić. Bo jeśli się da, to
zaoszczędzisz sobie mnóstwa pracy. Rozumiesz... notacja polska, albo
jeszcze lepiej odwrotna notacja polska pana Łukasiewicza, ze stosu
zdejmujesz operandy, potem operator, wykonujesz operację i wyniki
wrzucasz znowu na stos i tak w kółko aż na stosie zostanie wynik.

Pozdrawiam


> Coś takiego:
> ma symbolicznie robić operację postawiania:
> na przykład gdy liczymy pierwiastek z n to ze wzoru (wybierając x
> początkowe)
> x:= (x+n/x)/2
> druga iteracja, podstawiamy wszędzie gdzie x całe wyrażenie:
> otrzymujemy ((x+n/x)/2+n/((x+n/x)/2))/2
> możemy dalej
> (((x+n/x)/2+n/((x+n/x)/2))/2+n/(((x+n/x)/2+n/((x+n/x
)/2))/2))/2
>
> Działa już klonowanie (można podczepić całe drzewko do swojej podgałęzi,
> jeszcze nie mam tu replace- jest innej wersji , gdzie nie działało
> klonowanie), trzeba dorobić dziedziczenie:
> #include <memory>
> #include <string>
> #include <vector>
> #include <assert.h>
>
> using namespace std;
>
> class Node
> {
> vector<shared_ptr<Node>> childs;
> Node* parent = nullptr;//not shared_ptr! because of memory leaks of
> circular dependency
> int level = 0;
> public:
> string name;
> Node(string name)
> {
> this->name = name;
> }
> ~Node()
> {
> printf("delete %s\n",name.c_str());
> }
> shared_ptr<Node> cloneOne()
> {
> shared_ptr<Node> result = make_shared<Node>(name+"a");
> return result;
> }
>
> shared_ptr<Node> cloneTree()
> {
> shared_ptr<Node> newElem = cloneOne();
> for (size_t i = 0; i<childs.size(); i++)
> {
> shared_ptr<Node> subElem = childs[i]->cloneTree();
> newElem->AddOneChild(subElem);
> }
> return newElem;
> }
>
> void erase()
> {
> printf("erase from %s\n", name.c_str());
> childs.clear();
> }
> void deleteChild(int index)
> {
> printf("delete child %d from %s - %s\n", index, name.c_str(),
> childs[index]->name.c_str());
> childs.erase(childs.begin()+index);
> }
>
> void setLevel(int level)
> {
> this->level = level;
> for (size_t i = 0; i<childs.size(); i++)
> childs[i]->setLevel(level+1);
> }
>
> void AddOneChild(shared_ptr<Node> node)
> {
> childs.push_back(node);
> node->parent = this;
> }
>
> void AddTree(shared_ptr<Node> node)
> {
> shared_ptr<Node> clone = node->cloneTree();
> AddOneChild(clone);
> clone->setLevel(level+1);
> }
> shared_ptr<Node>& at(int index)
> {
> return childs[index];
> }
> void print()
> {
> for (int i = 0; i<level; i++)
> printf(" ");
> printf("%s->",name.c_str());
> if (parent) printf("%s", parent->name.c_str());
> printf("\n");
> for (size_t i=0; i<childs.size(); i++)
> childs[i]->print();
> }
> };
>
> int main()
> {
> shared_ptr<Node>root,rootB;
> root = make_shared<Node>("1");
> root->AddTree(make_shared<Node>("2"));
> root->AddTree(make_shared<Node>("3"));
> root->at(0)->AddTree(make_shared<Node>("4"));
> root->at(0)->AddTree(make_shared<Node>("5"));
> root->at(1)->AddTree(make_shared<Node>("6"));
> root->at(1)->AddTree(make_shared<Node>("7"));
> root->at(1)->AddTree(root);
> root->print();
> return 0;
> }

do góry