Drzewa przeszukiwań binarnych

14.12.2009 - Michał Karpiński
Trudność

Ćwiczenia

  1. Napisz rekurencyjną procedurę INSERT.

  2. Mamy drzewo BST z wartościami węzłów od 1 do 1000. Załóżmy, że chcemy wyszukać element o wartości 215. Czy poniższe ciągi mogą zostać sprawdzone w procedurze SEARCH?

    • 2, 423, 150, 220, 215
    • 900, 120, 888, 200, 887, 213, 216, 215
    • 1000, 999, 998, 997, 996...217, 216, 1, 215
    • 120, 356, 256, 116, 215
  3. Czy tworzenie drzewa BST poprzez wstawienie do drzewa pustego metodą INSERT kolejno wartości od 1 do n jest dobrym pomysłem? Dlaczego? Jaka będzie złożoność czasowa operacji elementarnych?

Zadania ze sprawdzaczką

1. Ciągi wyszukiwań

Sprawdzić, czy podany ciąg liczb może być ścieżką wyszukiwania dla drzewa BST o wartościach od 1 do 1000.

Wejście:

Na wejściu podajemy dwie linie. W pierwszej linii znajduje się jedna liczba z przedziału od 1 do 1000, która jest wartością szukanego elementu. Druga linijka zawiera ciąg składający się z 0<N<100 liczb z przedziału od 1 do 1000 oddzielonych spacją. Ciąg zawsze kończy się wyszukiwanym elementem.

Wyjście

Jeśli podany ciąg jest możliwą ścieżką wyszukiwania elementu z pierwszej linii wejścia, to wypisz „TAK”, w przeciwnym wypadku wypisz „NIE”.

Przykład 1

Wejście:
5
1 10 6 5

Wyjście:
TAK

Przykład 2

Wejście:
111
215 34 114 115 111

Wyjście:
NIE

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4.25
Twoja ocena: Brak Ocena: 4.3 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com