Un arbore AVL cu repetate valori și dual comparație

Question 1

Am nevoie pentru a crea o structură de date (folosind în principal arbori AVL) de obiecte cu două valori: nivel (nu unic) și id-ul (este unic).

Am nevoie pentru a sprijini căutarea de id-ul, imprimarea prin ordin de niveluri, precum și fuzionează două astfel de copaci și de a menține aceste funcționalități cu noul copac.

Am deja mai multe soluții în minte, dar am vrut să întreb despre unul specific:

Va lucra pentru a pune în aplicare această structură cu un singur arbore AVL în cazul în care două noduri sunt în primul rând față în funcție de nivelul lor, și apoi id-urile lor? Cea mai mare parte mă chinui să dau seama cum fuzionează două astfel de copaci ar putea lucra, mai ales în caz avem Un copac în cazul în care toate obiectele sunt de nivel x copac și B în cazul în care toate obiectele sunt de nivel y.

EDIT: de Asemenea, pentru căutarea de identitate în plus, va exista un copac numai sortate în funcție de id-ul.

Ar putea aceasta metoda?

Question 2

singular AVL tree în cazul în care două noduri sunt în primul rând față în funcție de nivelul lor, și apoi id-urile lor?

Din păcate, nu. Dacă faci asta, nu va fi capabil de a găsi eficient un nod de id-vei avea nevoie să se uite prin toate posibile "niveluri", care nu specifica presupun că ele pot fi nemărginit.

Cred că poate doriți să introduceți fiecare nod în două AVL copaci în loc. Un arbore AVL va pentru nodurile de nivel, celălalt de id-ul lor. Toate întrebările, inserții, deleții și fuzionează se poate face pe fiecare arbore separat.

Cu alte cuvinte v-ar crea două indicii asupra datelor.

În cod:

struct Node {
    int id;
    int level;

    // by id
    int id_bf;
    Node *id_left, *id_right;

    // by level
    int level_bf;
    Node *level_left, *level_right;
};

EDIT: de Asemenea, pentru căutarea de identitate în plus, va exista un copac numai sortate în funcție de id-ul.

Apoi descrie, în esență, același lucru ca și mine. Cu toate acestea copac care s-a rezolvat de compozit (level, id) cheia este risipitoare; tot ce ai nevoie este un copac clasificate în funcție de (level) și un copac clasificate în funcție de (id) (scalar chei). Nu e nevoie, printre operațiunile prevăzute, la fel de (level, id) și (id).

Yakov Galka · Answer 1 · 2021-11-23T19:29:44

singular AVL tree în cazul în care două noduri sunt în primul rând față în funcție de nivelul lor, și apoi id-urile lor?

Din păcate, nu. Dacă faci asta, nu va fi capabil de a găsi eficient un nod de id-vei avea nevoie să se uite prin toate posibile "niveluri", care nu specifica presupun că ele pot fi nemărginit.

Cred că poate doriți să introduceți fiecare nod în două AVL copaci în loc. Un arbore AVL va pentru nodurile de nivel, celălalt de id-ul lor. Toate întrebările, inserții, deleții și fuzionează se poate face pe fiecare arbore separat.

Cu alte cuvinte v-ar crea două indicii asupra datelor.

În cod:

struct Node {
    int id;
    int level;

    // by id
    int id_bf;
    Node *id_left, *id_right;

    // by level
    int level_bf;
    Node *level_left, *level_right;
};

EDIT: de Asemenea, pentru căutarea de identitate în plus, va exista un copac numai sortate în funcție de id-ul.

Apoi descrie, în esență, același lucru ca și mine. Cu toate acestea copac care s-a rezolvat de compozit (level, id) cheia este risipitoare; tot ce ai nevoie este un copac clasificate în funcție de (level) și un copac clasificate în funcție de (id) (scalar chei). Nu e nevoie, printre operațiunile prevăzute, la fel de (level, id) și (id).

Multumesc pentru raspuns, din păcate, am uitat să menționez că, în plus, voi avea un copac clasificate în funcție de id-ul pentru această funcționalitate. M-am gândit de soluție tine, am fost doar întrebam despre această soluție special un coleg de clasa mi-a spus ceea ce cred că nu va funcționa, deoarece de fuziune,
@user3917631: un copac clasificate în funcție de (nivel, id) este, de asemenea, clasificate în funcție de (nivel). Astfel, dacă aveți un copac clasificate în funcție de (id) în plus față de oricare dintre aceste, va fi capabil să facă în mod eficient operațiuni exact cum am descris-o. Este o risipă, la fel de (nivel, id) dacă tot ce ai nevoie este (nivel).
Știu, îți cer doar din interes, se poate lucra? Este posibil să aibă doi copaci clasificate în funcție de (nivel, id) ambele numere întregi și a le îmbina în O(n) (n numărul de combinat noduri).
@user3917631: da, este posibil, și nu diferit de fuzionează doi copaci sortate de nimic altceva. Arbori de căutare binare sunt comparații, deci nu au "grija" de ceea ce utilizați pentru cheia ta, atâta timp cât e un complet set ordonat. Un tuplu de numere întregi este de A stabili. Articolul de pe Wikipedia AVL arborii descrie cum să facă eficient de îmbinare; acolo se numește uniune. Cu toate acestea, poate doriți să magazin nod înălțime în loc de un factor de echilibru pentru a face asta.

Un arbore AVL cu repetate valori și dual comparație

Problema

Cel mai bun răspuns

În alte limbi

Această pagină este în alte limbi

Popular în această categorie

Întrebări frecvente în această categorie