Je AVL strom s opakovanými hodnoty a dual porovnanie

Question 1

Potrebujem vytvoriť štruktúru dát (pomocou hlavne AVL stromov) objektov s dve hodnoty: úroveň (nie je jednoznačný) a id (je jedinečné).

Potrebujem podporu, vyhľadávanie podľa id, tlač uznesením úrovniach, ako aj zlúčenie dvoch takýchto stromov a udržanie týchto funkcií s nový strom.

Už mám niekoľko riešení v mysli, ale ja som chcel požiadať o konkrétnej jeden:

Bude to fungovať na vykonávanie tejto štruktúry s jedinečným AVL strom, kde sa dva uzly sú prvé v porovnaní podľa ich úroveň, a potom ich ids? Väčšinou som sa snažia uvedomiť si, ako zlúčenie dvoch takýchto stromov môže pracovať, a to najmä v prípade, že máme strom, kde všetky objekty sú na úrovni x a strom B, kde všetky objekty sú na úrovni r.

EDIT: Aj pre vyhľadávanie id okrem toho tam bude strom len zoradené podľa id.

Mohla táto metóda funguje?

Question 2

v jednotnom AVL strom, kde sa dva uzly sú prvé v porovnaní podľa ich úroveň, a potom ich ids?

Bohužiaľ nie. Ak si myslíte, že nebudete môcť efektívne nájsť uzol pomocou svojho id -- budete musieť pozrieť cez všetky možné "úrovne", ktoré ste nechceli zadať, takže predpokladám, že môžu byť unbounded.

Myslím, že môžete vložiť každého uzla do dvoch samostatných AVL stromov miesto. Jeden AVL strom bude objednať uzlami úrovni, ostatné podľa ich id. Všetky otázky, vložené, vypustení a zlúči sa môže vykonať na každom strome samostatne.

Inými slovami by ste vytvoriť dva indexy cez vaše údaje.

Kód:

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: Aj pre vyhľadávanie id okrem toho tam bude strom len zoradené podľa id.

Potom ste v podstate vyjadrujú to isté, čo ja. Avšak svoj strom, ktorý je zoradený podľa kompozitný (level, id) kľúč je zbytočné; všetko, čo potrebujete, je strom zoradené podľa (level) a strom zoradené podľa (id) (skalárnym kľúče). Nie je potrebné, okrem operácií, ktoré ste poskytli, ak chcete zoradiť podľa (level, id) a (id).

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

v jednotnom AVL strom, kde sa dva uzly sú prvé v porovnaní podľa ich úroveň, a potom ich ids?

Bohužiaľ nie. Ak si myslíte, že nebudete môcť efektívne nájsť uzol pomocou svojho id -- budete musieť pozrieť cez všetky možné "úrovne", ktoré ste nechceli zadať, takže predpokladám, že môžu byť unbounded.

Myslím, že môžete vložiť každého uzla do dvoch samostatných AVL stromov miesto. Jeden AVL strom bude objednať uzlami úrovni, ostatné podľa ich id. Všetky otázky, vložené, vypustení a zlúči sa môže vykonať na každom strome samostatne.

Inými slovami by ste vytvoriť dva indexy cez vaše údaje.

Kód:

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: Aj pre vyhľadávanie id okrem toho tam bude strom len zoradené podľa id.

Potom ste v podstate vyjadrujú to isté, čo ja. Avšak svoj strom, ktorý je zoradený podľa kompozitný (level, id) kľúč je zbytočné; všetko, čo potrebujete, je strom zoradené podľa (level) a strom zoradené podľa (id) (skalárnym kľúče). Nie je potrebné, okrem operácií, ktoré ste poskytli, ak chcete zoradiť podľa (level, id) a (id).

Vďaka za odpoveď, žiaľ, len som zabudol spomenúť, že okrem toho budem mať strom zoradené podľa id pre túto funkciu. Myslel som, že vás riešenie práve som premýšľal o tejto konkrétnej riešenie spolužiaka, povedal mi, čo si myslím, že nebude fungovať, pretože zlúčenie,
@user3917631: strom zoradené podľa (úroveň, id) je tiež zoradené podľa (úroveň). Ak teda máte strom zoradené podľa (id) okrem jedným z tých, budete môcť robiť operácie, efektívne práve tak, ako som opísal. To je trochu zbytočné, aby zoradiť podľa (úroveň, id), ak všetko, čo potrebujete, je (úroveň).
Ja viem, som len otázkou z záujmu, môže to fungovať? Je možné mať dva stromy sú zoradené podľa (úroveň, id) ako celé čísla a zlúčiť ich v O(n) (n počet kombinácii uzlov).
@user3917631: áno, je to možné, a nie je odlišný od zlúčenie dvoch stromov zoradené podľa niečo iné. Binárne vyhľadávacie stromy sú v porovnaní založené, tak oni nemajú "starostlivosť" to, čo používate pre kľúčom tak dlho, ako je to úplne usporiadaný súbor. N-tice celočíselných hodnôt je nastaviť. Článok wikipédie na AVL stromov popisuje robiť efektívne zlúčiť; tam sa to volá únie. Avšak, možno budete chcieť uložiť uzol výška namiesto rovnováhy faktor k tomu, že.

Je AVL strom s opakovanými hodnoty a dual porovnanie

Otázka

Najlepšiu odpoveď

V iných jazykoch

Táto stránka je v iných jazykoch

Populárne v tejto kategórii

Obľúbené otázky v tejto kategórii