Exponenciální strom - Exponential tree

An exponenciální strom je téměř totožný s a binární vyhledávací strom, s tou výjimkou, že rozměr stromu není na všech úrovních stejný. V normálním binárním vyhledávacím stromu má každý uzel dimenzi (d) z 1 a má 2^d děti. V exponenciálním stromu se dimenze rovná hloubce uzlu, přičemž kořenový uzel má a d = 1. Takže druhá úroveň může obsahovat čtyři uzly, třetí může obsahovat osm uzlů, čtvrtá 16 uzlů atd.

Rozložení

„Exponenciální strom“ může také odkazovat na metodu rozložení uzlů stromové struktury v n (obvykle 2) dimenzionálním prostoru. Uzly jsou umístěny blíže k základní linii než jejich nadřazený uzel, faktorem rovným počtu podřízených uzlů tohoto nadřazeného uzlu (nebo nějakým vážením), a měřítko podle toho, jak blízko jsou. Bez ohledu na to, jak hluboký může být strom, tak vždy existuje prostor pro více uzlů a geometrie podstromu nesouvisí s jeho polohou v celém stromu. Celá má fraktální struktura.

Ve skutečnosti lze tuto metodu vytyčení stromu považovat za aplikaci horní polorovina model hyperbolická geometrie, přičemž izometrie jsou omezeny pouze na překlady.

Viz také

• Rychlejší deterministické třídění a vyhledávání v lineárním prostoru (Originální papír z '95)
• Rozvržení a vizualizace velkých stromů pomocí hyperbolického prostoru
• Implementace a analýza výkonu exponenciálního třídění stromů (Tento článek není správný)

Tento algoritmy nebo datové struktury související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.