To AVL strom s opakující se hodnoty a duální srovnání

Question 1

Potřebuji vytvořit datovou strukturu (hlavně pomocí AVL stromy) objektů s dvě hodnoty: úroveň (není unikátní) a id (je jedinečný).

Musím podpora vyhledávání podle id, tisk podle pořadí úrovní, stejně jako sloučení dva takové stromy a udržovat tyto funkce se nový strom.

Já už mám několik řešení v mysli, ale chtěl jsem se zeptat na jednu určitou.

Bude to pracovat na realizaci této struktury s pozoruhodnou AVL stromu, kde dva uzly jsou nejprve porovnány podle jejich úrovně, a pak jejich id? Většinou jsem boj, aby si uvědomili, jak sloučení dvou těchto stromů může fungovat, a to zejména v případě, že máme strom, kde všechny objekty jsou na úrovni x a stromu B, kde všechny objekty jsou na úrovni y.

EDIT: Také pro hledání id kromě toho tam bude strom pouze seřazené podle id.

Může tato metoda fungovat?

Question 2

singulární AVL stromu, kde dva uzly jsou nejprve porovnány podle jejich úrovně, a pak jejich id?

Bohužel ne. Pokud to uděláte, nebudete moci efektivně najít uzlu podle jeho id-budete muset hledat přes všechny možné "úrovní", které jsi neuvedl, takže předpokládám, že může být neomezená.

Myslím, že budete chtít vložit každý uzel do dvou samostatných AVL stromy místo. Jeden AVL strom bude pořadí uzlů podle úrovně, ostatní podle jejich id. Všechny dotazy, inzerce, delece a slučování může být provedeno na každý strom zvlášť.

Jinými slovy byste měli vytvořit dva indexy nad svými daty.

V kódu:

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: Také pro hledání id kromě toho tam bude strom pouze seřazené podle id.

Pak jste v podstatě popisují stejnou věc jako já. Nicméně svůj strom, který je řazena dle kompozitní (level, id) klíč je nehospodárné; vše, co potřebujete, je strom řazena dle (level) a strom řazena dle (id) (skalární klíče). Není třeba, mezi operace, které jste zadali, aby třídit podle (level, id) a (id).

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

singulární AVL stromu, kde dva uzly jsou nejprve porovnány podle jejich úrovně, a pak jejich id?

Bohužel ne. Pokud to uděláte, nebudete moci efektivně najít uzlu podle jeho id-budete muset hledat přes všechny možné "úrovní", které jsi neuvedl, takže předpokládám, že může být neomezená.

Myslím, že budete chtít vložit každý uzel do dvou samostatných AVL stromy místo. Jeden AVL strom bude pořadí uzlů podle úrovně, ostatní podle jejich id. Všechny dotazy, inzerce, delece a slučování může být provedeno na každý strom zvlášť.

Jinými slovy byste měli vytvořit dva indexy nad svými daty.

V kódu:

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: Také pro hledání id kromě toho tam bude strom pouze seřazené podle id.

Pak jste v podstatě popisují stejnou věc jako já. Nicméně svůj strom, který je řazena dle kompozitní (level, id) klíč je nehospodárné; vše, co potřebujete, je strom řazena dle (level) a strom řazena dle (id) (skalární klíče). Není třeba, mezi operace, které jste zadali, aby třídit podle (level, id) a (id).

Díky za odpověď, bohužel jsem se zapomněl zmínit, že navíc budu mít strom řazena dle id pro tuto funkci. Myslel jsem, že z vás řešením právě jsem přemýšlel o tomto konkrétním řešení spolužák mi řekl, což si myslím, že nebude fungovat, protože o sloučení,
@user3917631: strom řazena dle (level, id) je také řazena dle (úroveň). Tedy pokud máte strom řazena dle (id) kromě toho na některou z nich, budete moci dělat operace efektivně, stejně jako jsem popsal. To je trochu zbytečné třídit podle (level, id), pokud vše, co potřebujete, je (úroveň).
Já vím, já se jen ptám ze zájmu, může to fungovat? Je možné mít dva stromy řazena dle (level, id) celá čísla a spojit je v O(n) (n počet kombinovaných uzlů).
@user3917631: ano, je to možné, a neliší se od sloučení dvou stromů řazena dle něco jiného. Binární vyhledávací stromy jsou srovnání založené, takže nemají "péče", co používáte pro váš klíč tak dlouho, jak je to úplně uspořádaná množina. N-tice celých čísel je nastavit. Wikipedia článek o AVL stromech popisuje, jak to udělat efektivní sloučit; tam se tomu říká unie. Nicméně, možná budete chtít uložit uzel výška místo bilance faktor.

To AVL strom s opakující se hodnoty a duální srovnání

Otázka

Nejlepší odpověď

V jiných jazycích

Tato stránka je v jiných jazycích

Populární v této kategorii

Oblíbené položky v této kategorii