Drzewo AVL z powtarzającymi się wartościami i podwójnym porównaniem

Question 1

Muszę stworzyć strukturę danych (używając głównie drzewa AVL) obiektów z dwóch wartości: poziom (nie jest wyjątkowy) i identyfikator (wyjątkowy).

Muszę utrzymać wyszukiwanie według identyfikatora, drukowanie w kolejności poziomów, a także łączenie dwóch takich drzew i utrzymanie tych funkcji z nowym drzewem.

Mam już kilka rozwiązań na oku, ale chciałem zapytać o konkretnym:

Czy będzie działać realizacja tej struktury za pomocą jedynego drzewa AVL, w którym dwa węzły najpierw porównywane są zgodnie z ich poziomem, a następnie ich identyfikatorami? W zasadzie ja ze wszystkich sił staram się zrozumieć, jak może działać połączenie dwóch takich drzew, zwłaszcza w przypadku, jeśli mamy drzewo A, gdzie wszystkie obiekty mają poziom x, i drzewo B, gdzie wszystkie obiekty mają poziom y.

EDIT: Także dla wyszukiwania identyfikatora dodatkowo będzie drzewo, posortowanych tylko na podstawie identyfikatora.

Czy ta metoda się udać?

Question 2

jedyne drzewo AVL, w którym najpierw porównywane są dwa węzły zgodnie z ich poziomem, a następnie ich identyfikatory?

Niestety, nie ma. Jeśli to zrobisz, nie będzie w stanie skutecznie znaleźć witrynę w jego identyfikatora-trzeba będzie zobaczyć wszystkie możliwe "poziomy", które nie podałeś, więc zakładam, że mogą być nieograniczone.

Myślę, że warto zamiast tego wstawić każdy węzeł w dwa oddzielne drzewa AVL. Jedno drzewo AVL będzie organizować węzły na poziomie, z drugiej-na ich identyfikatora. Wszystkie wnioski, wstawianie, usuwanie i łączenie można wykonywać w każdym drzewie oddzielnie.

Innymi słowy, można utworzyć dwa indeksy nad swoimi danymi.

W kodzie:

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że dla wyszukiwania identyfikatora dodatkowo będzie drzewo, posortowanych tylko na podstawie identyfikatora.

Wtedy, w rzeczywistości, opisujesz to samo, co ja. Jednak drzewo, posortowanych według wieloczęściowego (level, id) klucz расточителен; wszystko, czego potrzebujesz, to drzewo, posortowanych według (level) i drzewo, posortowanych według (id) (skalarne klucze). Wśród przekazanych operacji nie ma potrzeby sortuj według (level, id) i (id).

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

jedyne drzewo AVL, w którym najpierw porównywane są dwa węzły zgodnie z ich poziomem, a następnie ich identyfikatory?

Niestety, nie ma. Jeśli to zrobisz, nie będzie w stanie skutecznie znaleźć witrynę w jego identyfikatora-trzeba będzie zobaczyć wszystkie możliwe "poziomy", które nie podałeś, więc zakładam, że mogą być nieograniczone.

Myślę, że warto zamiast tego wstawić każdy węzeł w dwa oddzielne drzewa AVL. Jedno drzewo AVL będzie organizować węzły na poziomie, z drugiej-na ich identyfikatora. Wszystkie wnioski, wstawianie, usuwanie i łączenie można wykonywać w każdym drzewie oddzielnie.

Innymi słowy, można utworzyć dwa indeksy nad swoimi danymi.

W kodzie:

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że dla wyszukiwania identyfikatora dodatkowo będzie drzewo, posortowanych tylko na podstawie identyfikatora.

Wtedy, w rzeczywistości, opisujesz to samo, co ja. Jednak drzewo, posortowanych według wieloczęściowego (level, id) klucz расточителен; wszystko, czego potrzebujesz, to drzewo, posortowanych według (level) i drzewo, posortowanych według (id) (skalarne klucze). Wśród przekazanych operacji nie ma potrzeby sortuj według (level, id) i (id).

Dziękuję za odpowiedź, niestety, zapomniałem wspomnieć, że dodatkowo mam drzewo, posortowanych według identyfikatora dla tej funkcji. Pomyślałem o swojej decyzji,zastanawiałem się dowiedzieć o tym konkretnym rozwiązaniu, które mi powiedział kolega, i myślę, że to się nie uda z powodu fuzji,
@user3917631: drewno, posortowanych według (poziom, identyfikatora), również jest posortowana według (poziom). Tak więc, jeśli masz drzewo, posortowanych według (identyfikatora) w dodatku do każdego z nich, będziesz w stanie skutecznie wykonywać operacje, jak opisałem. Trochę marnotrawstwo sortuj według (poziom, identyfikatora), jeśli wszystko, czego potrzebujesz, to (poziom).
Wiem, pytam tylko z ciekawości, czy to może zadziałać? Czy jest możliwe, aby dwa drzewa zostały posortowane według (poziom, identyfikatora) obu liczbą liczb i połączyli je w O(n) (n ilość połączonych węzłów).
@user3917631: tak, jest to możliwe, i nie różni się od połączenia dwóch drzew, posortowane według czegoś jeszcze. Drzewa binarnego wyszukiwania opierają się na porównaniu, więc im wszystko jedno, co używasz do swojego kluczyka, jeśli jest w pełni uporządkowany zestaw. Orszak liczb całkowitych jest zbiorem. Artykuł Wikipedii o drzewach AVL opisuje, jak skutecznie wykonać połączenie; tam to się nazywa stowarzyszeniem. Jednak do tego można zapisać wysokości węzła zamiast współczynnika równowagi.

Drzewo AVL z powtarzającymi się wartościami i podwójnym porównaniem

Pytanie

Najlepsza odpowiedź

W innych językach

Ta strona jest w innych językach

Popularne w tej kategorii

Najczęściej zadawane pytania w tej kategorii