Answer these queries

23.02.2010 - Tomasz Górzny
TrudnośćTrudnośćTrudnośćTrudność

Implementacja drzew binarnych

Na koniec wypada powiedzieć jeszcze kilka słów o implementacji drzew. Można w każdym węźle trzymać wskaźniki na jego potomków, ale to nie jest najlepsze rozwiązanie. Lepiej zamiast tego przechowywać je w tablicy wg tego schematu:

Tzn jeżeli wierzchołek ma indeks i, to i*2 jest jego lewym synem, a i*2+1 prawym.

Pozwala to zaoszczędzić nieco pamięci na wskaźnikach, trochę przyspiesza obliczenia i pozwala zapisywać rzeczy w bardziej elegancki (choć być może mniej czytelny) sposób - na przykład budować drzewa od dołu w górę.

Powiedzmy, że chcielibyśmy w drzewie przechowywać sumę przedziału. Kod wyglądałby tak:

1
2
3
4
5
D - drzewo przedziałowe - tablica intów o rozmiarze 2*N
for i = 1 .. N
  D[N-1+i] = T[i]
for i = N-1 .. 1
  D[i] = D[i*2] + D[i*2+1]

Praca domowa

  1. Pokaż jak radzić sobie z N nie będącym potęgą dwójki.
  2. Jeżeli jeszcze tego nie zrobiłeś/aś, użyj w poprzednich zadaniach przedstawionego sposobu reprezentacji drzew.

Na dokładkę

Jeżeli jeszcze czujesz niedosyt, polecam zrobienie zadania GSS6 na SPOJu.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com