Usunięcie uporządkowanej sekwencji liczb z BST

Question

Miałem to pytanie podczas egzaminu i nie mogłem znaleźć szybkiej odpowiedzi.

Istnieje tablica A zawierająca niektóre uporządkowane liczby A = [1,3,6,9,11] i BST z numerami jako kluczem. Muszę zapewnić efektywny algorytm rekursywny, aby usunąć liczby w A z BST.

Problem, który mam, nie polega na usuwaniu węzłów, ale na tym, jak wykorzystać fakt, że tablica jest uporządkowana podczas usuwania węzłów.

Czy ktoś może mi pomóc z pewnymi wskazówkami?

Answer 1

Oto jedno z możliwych podejść.

Można jednocześnie przemierzać BST (używając standard recursive algorithm) i A (od lewej do prawej). Każde z tych przemieszczeń da elementy w porządku rosnącym. Szukacie pasujących elementów, aby usunąć je z drzewa.

Algorytm naiwny będzie miał złożoność czasu O(size(BST)).

W niektórych przypadkach można zupełnie nie patrzeć na lewy poddrzewo: wartość "bieżącego" węzła w drzewie daje górną granicę wartości w lewym poddrzewie, więc jeśli jest mniejsza niż wartość "bieżący" element A, pomiń lewy poddrzewo.

Algorytm można również zatrzymać, gdy wyczerpią się A.

Answer 2

Niech BST będzie reprezentowany przez jego węzeł główny.

Funkcja delete-array-from-bst argumentów array i bst jest:

• jeśli array lub bst jest pusta: powrotu
• podzielić tablicy do trzech subarrays wartości mniejszy, równy lub większy niż bst Wartość węzła głównego
• recurse na subarray z mniejszymi wartościami z lewym sub-BST, następnie na subarray z większymi wartościami na prawym pod-BST, na końcu usunąć tę samą wartość, jeśli aplikacja kabel

Dzielenie tablicy jest wyszukiwaniem binarnym, dzięki czemu nie ma potrzeby porównywania wartości każdej tablicy z węzłem głównym. Podrozdziały mogą współdzielić strukturę z oryginalną tablicą. Usunięcie tej ostatniej wartości gwarantuje, że nie trafisz na najgorszy przypadek usuwania dla każdej wartości w tablicy.