Rozvětvený strom

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 8. září 2016; kontroly vyžadují 19 úprav .
rozšiřující se strom
Typ Dřevo
Rok vynálezu 1985
Autor Daniel Slitor a Robert Andre Tarjan
Složitost v O-symbolech
Průměrný Při nejhorším
Spotřeba paměti Na) Na)
Vyhledávání O(log n) O(log n)
Vložit O(log n) O(log n)
Odstranění O(log n) O(log n)

Splay tree nebo skew tree je  binární vyhledávací strom , který udržuje vlastnost balance. Tento strom patří do třídy "samoregulačních stromů", které udržují nezbytnou rovnováhu větvení stromu, aby bylo zajištěno, že vyhledávání, přidávání a mazání lze provádět v logaritmickém čase z počtu uložených prvků. To se provádí bez použití jakýchkoli dalších polí v uzlech stromu (jako například v stromech Red-black nebo AVL-trees , kde je ve vrcholech uložena barva vrcholu a hloubka podstromu). Místo toho se operace roztažení, jejíž součástí jsou rotace, provádí při každém přístupu ke stromu.

Účetní náklady na jednu operaci se stromem jsou.

Rozšiřující se strom vynalezli Robert Tarjan a Daniel Slator v roce 1983.

Operace

Roztažení (expanze)

Základní obsluha stromu. Spočívá v přesunutí vrcholu do kořene pomocí sekvenčního provádění tří operací: Zig, Zig-Zig a Zig-Zag. Vrchol, který chceme přesunout do kořene, označme jako x , jeho rodič - p a rodič p (pokud existuje) - g .

Zig: provede se, když p je kořen. Strom je otočen podél hrany mezi x a p . Existuje pouze jako okrajový případ a běží pouze jednou na konci, když byla počáteční hloubka x lichá.

Zig-Zig: Provede se, když x i p jsou leví (nebo pravý) synové. Strom se otáčí podél okraje mezi g a p a poté podél okraje mezi p a x .

Cik-cak: Běží , když x je pravé dítě a p  je levé dítě (nebo naopak). Strom se otáčí podél hrany mezi p a x a poté podél hrany mezi x a g .

Hledat (hledat prvek)

Vyhledávání se provádí jako v normálním binárním vyhledávacím stromu. Když je prvek nalezen, spustíme pro něj Splay.

Vložit (přidání prvku)

Spusťte Split() na přidávaném prvku (viz Split(), připomenutí: používá nejbližší větší nebo stejný prvek existujícího stromu) a zavěste výsledné stromy za prvek, který se má přidat.

Delete (smazání prvku)

Najdeme prvek ve stromu, uděláme pro něj Splay, uděláme z jeho dětí aktuální strom sloučení.

Merge (sloučení dvou stromů)

Abychom sloučili stromy T1 a T2, ve kterých jsou všechny klíče v T1 menší než klíče v T2, uděláme Splay pro maximální prvek T1, pak kořen T1 nebude mít správného potomka. Poté uděláme z T2 správné dítě T1.

Split (rozdělení stromu na dvě části)

Chcete-li strom rozdělit podle x, najděte nejmenší prvek, který je větší nebo roven x, a vytvořte pro něj Splay. Poté se oddělíme od kořene levého potomka a vrátíme 2 výsledné stromy.

Implementace

Jednou implementací rozšiřujícího stromu by byla implementace, která používá 3 ukazatele v každém vrcholu: ukazatel na pravé a levé potomky a také na rodiče. Tím se zabrání rekurzivní implementaci, která zase ušetří paměť. Nevýhodou je v tomto případě větší počet zadání pro aktualizaci ukazatelů, což může ovlivnit výsledný výkon.

Níže je implementace rozšiřujícího stromu pomocí 3 ukazatelů na uzel. Také v této implementaci je operace Splay použita ve všech základních operacích prováděných na stromě - při vkládání, mazání a vyhledávání pro dosažení lepší rovnováhy stromu.

#ifndef SPLAYTREE_H #define SPLAYTREE_H šablona < typename T > class SplayTree { soukromý : struct SplayNode { Uzel * leftChild ; Uzel * rightChild Uzel * rodič ; T data ; Uzel ( const T & key = T ()) : leftChild ( nullptr ), rightChild ( nullptr ), parent ( nullptr ), key ( key ) {} ~ Uzel () { smazat levéDítě ; smazat rightDítě ; } } * kořen ; soukromý : SplayNode * _Successor ( SplayNode * localRoot ) const { SplayNode * následník = localRoot ; if ( následník -> rightChild != nullptr ) { následník = _Minimum ( následník -> rightChild ); } jinak { while ( následník != kořen || následník != následník -> rodič -> levé dítě ) { následník = nástupce -> rodič ; } } návrat nástupce ; } SplayNode * _Predecessor ( SplayNode * localRoot ) const { SplayNode * předchůdce = localRoot ; if ( předchůdce -> leftChild != nullptr ) { předchůdce = _Maximum ( předchůdce -> leftChild ); } jinak { while ( předchůdce != kořen || předchůdce != předchůdce -> rodič -> pravé dítě ) { předchůdce = předchůdce -> rodič ; } } vrátit předchůdce ; } SplayNode * _Minimum ( SplayNode * localRoot ) const { SplayNode * minimum = localRoot ; while ( minimum -> leftChild != nullptr ) minimum = minimum -> leftChild ; návratnost minimum ; } SplayNode * _Maximum ( SplayNode * localRoot ) const { SplayNode * maximum = localRoot ; while ( maximum -> rightChild != nullptr ) maximum = maximum -> rightChild ; maximální návratnost ; } SplayNode * _Search ( const T & key ) { SplayNode * searchElement = root ; while ( searchElement != nullptr ) { if ( hledanyPrvek -> data < klic ) vyhledanyPrvek = vyhledanyPrvek -> rightChild ; else if ( klíč < hledanýPrvek -> data ) hledanýPrvek = hledanýPrvek -> leftChild ; else if ( searchElement -> data == key ) { _Přehrát ( hledanýPrvek ); vrátit hledanýPrvek ; } } return nullptr ; } void _LeftRotate ( SplayNode * localRoot ) { SplayNode * rightChild = localRoot -> rightChild ; localRoot -> rightChild = rightChild -> leftChild ; if ( rightChild -> leftChild != nullptr ) rightChild -> leftChild -> parent = localRoot ; _Transplant ( localRoot , rightChild ); rightChild -> leftChild = localRoot ; rightChild -> leftChild -> parent = rightChild ; } void _RightRotate ( SplayNode * localRoot ) { SplayNode * leftChild = localRoot -> leftChild ; localRoot -> leftChild = leftChild -> rightChild ; if ( leftChild -> rightChild != nullptr ) leftChild -> rightChild -> parent = localRoot ; _Transplant ( localRoot , leftChild ); leftChild -> rightChild = localRoot ; leftChild -> rightChild -> parent = leftChild ; } void _Transplant ( SplayNode * localParent , SplayNode * localChild ) { if ( localParent -> parent == nullptr ) root = localChild ; else if ( localParent == localParent -> parent -> leftChild ) localParent -> parent -> leftChild = localChild ; else if ( localParent == localParent -> parent -> rightChild ) localParent -> parent -> rightChild = localChild ; if ( localChild != nullptr ) localChild -> parent = localParent -> parent ; } void _Splay ( SplayNode * pivotElement ) { while ( pivotElement != root ) { if ( pivotElement -> parent == root ) { if ( pivotElement == pivotElement -> parent -> leftChild ) { _RightRotate ( pivotElement -> parent ); } else if ( pivotElement == pivotElement -> parent -> rightChild ) { _LeftRotate ( pivotElement -> parent ); } } jinak { // Krok cik-cik. if ( pivotElement == pivotElement -> parent -> leftChild && pivotElement -> parent == pivotElement -> parent -> parent -> leftChild ) { _RightRotate ( pivotElement -> parent -> parent ); _RightRotate ( pivotElement -> parent ); } else if ( pivotElement == pivotElement -> parent -> rightChild && pivotElement -> parent == pivotElement -> parent -> parent -> rightChild ) { _LeftRotate ( pivotElement -> parent -> parent ); _LeftRotate ( pivotElement -> parent ); } // Krok cik-cak. else if ( pivotElement == pivotElement -> parent -> rightChild && pivotElement -> parent == pivotElement -> parent -> parent -> leftChild ) { _LeftRotate ( pivotElement -> parent ); _RightRotate ( pivotElement -> parent ); } else if ( pivotElement == pivotElement -> parent -> leftChild && pivotElement -> parent == pivotElement -> parent -> parent -> rightChild ) { _RightRotate ( pivotElement -> parent ); _LeftRotate ( pivotElement -> parent ); } } } } veřejnost : SplayTree () { root = nullptr ; } virtuální ~ SplayTree () { odstranit kořen ; } void Insert ( const T & key ) { SplayNode * preInsertPlace = nullptr ; SplayNode * insertPlace = root ; while ( insertPlace != nullptr ) { preInsertPlace = insertPlace ; if ( insertPlace -> data () < key ) insertPlace = insertPlace -> rightChild ; else if ( klíč <= insertPlace -> data ) insertPlace = insertPlace -> leftChild ; } SplayNode * insertElement = new SplayNode ( klíč ); insertElement -> parent = preInsertPlace ; if ( preInsertPlace == nullptr ) root = insertElement ; else if ( preInsertPlace -> data < insertElement -> data ) preInsertPlace -> rightChild = insertElement ; else if ( insertElement -> data < preInsertPlace -> data ) preInsertPlace -> leftChild = insertElement ; _Splay ( insertElement ); } void Odebrat ( const T & key ) { SplayNode * removeElement = _Search ( klíč ); if ( removeElement != nullptr ) { if ( removeElement -> rightChild == nullptr ) _Transplant ( removeElement , removeElement -> leftChild ); else if ( removeElement -> leftChild == nullptr ) _Transplant ( removeElement , removeElement -> rightChild ); jinak { SplayNode * newLocalRoot = _Minimum ( removeElement -> rightChild ); if ( newLocalRoot -> parent != removeElement ) { _Transplant ( newLocalRoot , newLocalRoot -> rightChild ); newLocalRoot -> rightChild = removeElement -> rightChild ; newLocalRoot -> rightChild -> parent = newLocalRoot ; } _Transplant ( removeElement , newLocalRoot ); newLocalRoot -> leftChild = removeElement -> leftChild ; newLocalRoot -> leftChild -> parent = newLocalRoot ; _Splay ( newLocalRoot ); } delete removeElement ; } } bool Hledat ( const T & key ) { return _Search ( key ) != nullptr ; } bool isEmpty () const { return root == nullptr ; } T následník ( const T & key ) { if ( _Nástupce ( _Hledat ( klíč )) != nullptr ) { return _Successor ( _Search ( klíč )) -> getValue (); } jinak { návrat -1 ; } } T předchůdce ( const T & key ) { if ( _Predecessor ( _Search ( klíč )) != nullptr ) { return _Predecessor ( _Search ( klíč )) -> getValue (); } jinak { návrat -1 ; } } }; #endif //SPLAYTREE_H

Poznámka

Rozšiřující se strom poskytuje samomodifikující strukturu – strukturu charakterizovanou tendencí udržovat často přístupné uzly blízko vrcholu stromu, zatímco zřídka přístupné uzly se pohybují blíže k listům. Doba přístupu k často navštěvovaným uzlům bude tedy kratší a doba přístupu k uzlům, které se často nenavštěvují, bude delší než průměr.

Rozšiřující se strom nemá žádné explicitní vyrovnávací funkce, ale proces zkosení uzlů směrem ke kořenu pomáhá udržovat strom vyvážený.

Viz také

  • Vyvážené (samobalanční) stromy:
  • Seznam datových struktur (stromů)

Literatura

  • Thomas H. Kormen aj. Algoritmy: konstrukce a analýza. - 2. vyd. - M . : Williams Publishing House , 2007. - S. 1296. - ISBN 5-8459-0857-4 .
  • Daniel Sleater, Robert Tarjan. Datová struktura pro dynamické stromy. - Journal of Computer and System Sciences, 1983. - S. 262-391.