Określ strukturalną równoważność BST ze standardowym traversal - algorytm, wyszukiwanie, struktury danych, drzewo, katalan

Czy można zdecydować się na konstrukcjęrównoważność dwóch binarnych drzew poszukiwań tylko z wynikami przemierzania, przed zamówieniem, w kolejności i kolejności. Załóżmy, że mam tylko tablice wyników wszystkich przejść. Wiem, że aby przejść sam, nie mogę pomóc. Ale nie mogłem sobie wyobrazić innych rezultatów przejścia. Rozumiem, że BFS pomaga. Chcę wiedzieć o przemierzeniach przed i po zamówieniu. I jeśli to możliwe, proszę zamieścić na niej wszelkie linki.

Odpowiedzi:

Odpowiedź to : można odzyskać drzewo wyszukiwania binarnego z jego przejścia przed zamówieniem.

Nie jestem pewien, jakie jest twoje tło matematyczne, więc zapytaj, czy potrzebujesz więcej wyjaśnień.

Dla uproszczenia, „zakładam, że węzeł jest oznaczony liczbą całkowitą 1,2 ... n, gdzie n jest liczbą węzłów. Wtedy przejście przez drzewo t przed porządkiem daje permutację [n] = {1,2,...,n} które mają określoną właściwość: za każdym razem, gdy masz literę b w swojej permutacji, nie możesz znaleźć dwóch kolejnych liter ca po b w permutacji takiej, że a<b<c. Mówi się, że taka permutacja uniknąć wzór b-ac (- oznacza dowolną liczbę liter).

Na przykład 4 2 1 3 unika b-ac, natomiast 3 1 4 2 nie, ponieważ 3 - 4 2.

W rzeczywistości jest to równoważność: permutacja jest wstępnym odczytem drzewa i uniknięcie b-ac.

Wiadomo, że jest tyle drzew o rozmiarze njako permutacja unikająca b-ac, więc jest to wstrzyknięcie. Ich liczba jest znana jako liczba katalońska. Prawdopodobnie możesz znaleźć to jako przykład książki Stanleya „enumeratywne kombinatoryki”.

Oto bardziej algorytmiczne wyjaśnienie:

RecTree: Recovering a tree from is Pre-order traversal:

input: list l
output: tree t

b <- l[0]
find an index i such that
- for 1<=j<=i then l[j] < b and
- for i<j<=n  then l[j] > b
if there isn"t exists such an index return Failure
else return Node(key=b, RecTree(l[1..i]), RecTree(l[i+1..n]))

W konsekwencji

Dwa binarne drzewa przeszukiwania są równe, jeśli i tylko wtedy, gdy mają takie samo przechodzenie przed zamówieniem

Czy to ma dla ciebie sens?

Więcej referencji

• Kataloński numer w On-Line Encyclopedia of Integer Sequences
• Anders Claesson Generalized Pattern Avoidance, European Journal of Combinatorics 22 (2001) 961–971

W BST możesz przejść do lewego dziecka (L), prawego dziecka(R) lub w górę (U). Przejście można następnie opisać ciągiem znaków nad {L, R, U}, np. „LLURUURLURUU”. W przypadku BST o równoważnych strukturach ciągi te będą identyczne.