Objednat statistický strom - Order statistic tree - Wikipedia

v počítačová věda, an objednat statistický strom je varianta binární vyhledávací strom (nebo obecněji a B-strom[1]) který podporuje dvě další operace kromě vložení, vyhledávání a odstranění:

  • Vybrat(i) - najít játen nejmenší prvek uložený ve stromu
  • Hodnost(X) - vyhledejte pořadí prvků X ve stromu, tj. jeho index v seřazeném seznamu prvků stromu

Obě operace lze provádět v Ó(log n) nejhorší případ čas, kdy a samovyvažovací strom se používá jako základní datová struktura.

Rozšířená implementace stromu vyhledávání

Chcete-li z běžného vyhledávacího stromu udělat statistický strom objednávky, musí uzly stromu uložit jednu další hodnotu, což je velikost podstromu zakořeněného v daném uzlu (tj. Počet uzlů pod ním). Všechny operace, které upravují strom, musí tyto informace upravit, aby zachovaly neměnný že

size [x] = size [left [x]] + size [right [x]] + 1

kde velikost [nil] = 0 podle definice. Select lze poté implementovat jako[2]:342

funkce Select (t, i) // Vrátí i-tý prvek (s nulovým indexem) prvků v t l ← size [left [t]] + 1 -li i = l návrat t jinak pokud i jiný        návrat Vybrat (vpravo [t], i - l)

Rank lze implementovat jako[3]:342

funkce Rank (T, x) // Vrátí pozici x (jednoindexovaného) v lineárně seřazeném seznamu prvků stromu T r ← size [left [x]] + 1 y ← x zatímco y ≠ T.root -li y = vpravo [p [y]] r ← r + velikost [vlevo [p [y]]] + 1 y ← p [y] vrátit se r

Stromy statistik objednávek lze dále doplnit o informace účetnictví, aby byla zachována rovnováha (např. K získání statistiky objednávky lze přidat výšku stromu Strom AVL nebo barevný bit k získání červená černá statistický strom objednávky). Alternativně lze pole velikosti použít ve spojení s a vyvážení hmotnosti schéma bez dalších nákladů na skladování.[4]

Reference

  1. ^ "Počítané B-stromy". 11. prosince 2004. Citováno 18. ledna 2014.
  2. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. Úvod do algoritmů (2. vyd.). MIT Press a McGraw-Hill. ISBN  0-262-03293-7.
  3. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Úvod do algoritmů (3. vyd.). MIT Press a McGraw-Hill. ISBN  0-262-03384-4.
  4. ^ Roura, Salvador (2001). Nová metoda pro vyvažování binárních vyhledávacích stromů. ICALP. Přednášky z informatiky. 2076. 469–480. doi:10.1007/3-540-48224-5_39. ISBN  978-3-540-42287-7.

externí odkazy