Splay tree er en selvjusterende binær søgetræ datastruktur, hvilket betyder, at træstrukturen justeres dynamisk baseret på de tilgåede eller indsatte elementer. Med andre ord omorganiserer træet sig automatisk, så ofte tilgåede eller indsatte elementer kommer tættere på rodknuden.
- Splay-træet blev først introduceret af Daniel Dominic Sleator og Robert Endre Tarjan i 1985. Det har en enkel og effektiv implementering, der gør det muligt at udføre søge-, indsættelses- og sletningsoperationer i O(log n) amortiseret tidskompleksitet, hvor n er antal elementer i træet.
- Den grundlæggende idé bag splay-træer er at bringe det senest åbnede eller indsatte element til roden af træet ved at udføre en sekvens af trærotationer, kaldet splaying. Splaying er en proces med omstrukturering af træet ved at gøre det senest åbnede eller indsatte element til den nye rod og gradvist flytte de resterende noder tættere på roden.
- Splaytræer er yderst effektive i praksis på grund af deres selvjusterende karakter, hvilket reducerer den samlede adgangstid for ofte tilgåede elementer. Dette gør dem til et godt valg til applikationer, der kræver hurtige og dynamiske datastrukturer, såsom cachesystemer, datakomprimering og netværksroutingalgoritmer.
- Den største ulempe ved sprøjtetræer er dog, at de ikke garanterer en afbalanceret træstruktur, hvilket kan føre til ydeevneforringelse i værst tænkelige scenarier. Splay-træer er heller ikke egnede til applikationer, der kræver garanteret worst-case ydeevne, såsom realtidssystemer eller sikkerhedskritiske systemer.
Overordnet set er splay-træer en kraftfuld og alsidig datastruktur, der giver hurtig og effektiv adgang til ofte tilgåede eller indsatte elementer. De er meget udbredt i forskellige applikationer og giver en fremragende afvejning mellem ydeevne og enkelhed.
Et splaytræ er et selvbalancerende binært søgetræ, designet til effektiv adgang til dataelementer baseret på deres nøgleværdier.
- Nøglefunktionen ved et splaytræ er, at hver gang et element tilgås, flyttes det til roden af træet, hvilket skaber en mere afbalanceret struktur for efterfølgende adgange.
- Splaytræer er kendetegnet ved deres brug af rotationer, som er lokale transformationer af træet, der ændrer form, men bevarer elementernes rækkefølge.
- Rotationer bruges til at bringe det tilgåede element til roden af træet, og også til at genbalancere træet, hvis det bliver ubalanceret efter flere adgange.
Operationer i et splaytræ:
- Indskud: For at indsætte et nyt element i træet, start med at udføre en almindelig binær søgetræindsættelse. Anvend derefter rotationer for at bringe det nyligt indsatte element til roden af træet.
- Sletning : For at slette et element fra træet, skal du først finde det ved hjælp af en binær søgetræsøgning. Derefter, hvis elementet ikke har nogen børn, skal du blot fjerne det. Hvis det har ét barn, så forfrem det barn til dets position i træet. Hvis det har to børn, skal du finde elementets efterfølger (det mindste element i dets højre undertræ), bytte dets nøgle med elementet, der skal slettes, og i stedet slette efterfølgeren.
- Søg : For at søge efter et element i træet, start med at udføre en binær søgetræsøgning. Hvis elementet er fundet, skal du anvende rotationer for at bringe det til roden af træet. Hvis den ikke findes, skal du anvende rotationer på den sidst besøgte node i søgningen, som bliver den nye rod.
- Rotation : De rotationer, der bruges i et splay-træ, er enten en Zig- eller en Zig-Zig-rotation. En Zig-rotation bruges til at bringe en node til roden, mens en Zig-Zig-rotation bruges til at balancere træet efter flere adgange til elementer i det samme undertræ.
Her er en trin-for-trin forklaring af rotationsoperationerne:
- Zig rotation : Hvis en node har et rigtigt barn, skal du udføre en højrerotation for at bringe det til roden. Hvis den har et venstre barn, skal du udføre en venstredrejning.
- Zig-Zig Rotation: Hvis en node har et barnebarn, der også er dets barns højre eller venstre barn, skal du udføre en dobbeltrotation for at balancere træet. Hvis noden f.eks. har et højre barn, og det højre barn har et venstre barn, skal du udføre en højre-venstre-rotation. Hvis knudepunktet har et venstre barn, og det venstre barn har et højre barn, skal du udføre en venstre-højre rotation.
- Bemærk: De specifikke implementeringsdetaljer, herunder de nøjagtige rotationer, der anvendes, kan variere afhængigt af den nøjagtige form af spiltræet.
Rotationer i Splay Tree
- Zig rotation
- Zag Rotation
- Zig – Zig Rotation
- Zag – Zag Rotation
- Zig – Zag Rotation
- Zag – Zig-rotation
1) Zig-rotation:
Zig-rotationen i spredetræer fungerer på samme måde som den enkelte højrerotation i AVL-trærotationer. Denne rotation resulterer i, at noder flytter en position til højre fra deres nuværende placering. Overvej for eksempel følgende scenarie:
Zig-rotation (enkelt rotation)
2) Zag Rotation:
Zag-rotationen i spredetræer fungerer på samme måde som den enkelte venstrerotation i AVL-trærotationer. Under denne rotation skifter noder en position til venstre fra deres nuværende placering. Overvej for eksempel følgende illustration:
len af streng i java
Zag Rotation (Enkelt venstre rotation)
3) Zig-Zig Rotation:
Zig-Zig-rotationen i spredetræer er en dobbelt zig-rotation. Denne rotation resulterer i, at noder flytter to positioner til højre fra deres nuværende placering. Tag et kig på følgende eksempel for en bedre forståelse:
Zig-Zig-rotation (dobbelt højrerotation)
4) Zag-Zag Rotation:
I spredetræer er Zag-Zag Rotation en dobbelt zag-rotation. Denne rotation får noder til at flytte to positioner til venstre fra deres nuværende position. For eksempel:
Zag-Zag rotation (dobbelt venstre rotation)
5) Zig-Zag rotation:
Zig-Zag-rotationen i spredte træer er en kombination af en zig-rotation efterfulgt af en zag-rotation. Som et resultat af denne rotation skifter knudepunkter en position til højre og derefter en position til venstre fra deres nuværende placering. Følgende illustration giver en visuel repræsentation af dette koncept:
et array i java
Zig-zag rotation
6) Zag-Zig Rotation:
Zag-Zig-rotationen i spredetræer er en serie af zag-rotationer efterfulgt af en zig-rotation. Dette resulterer i, at noder flytter en position til venstre, efterfulgt af et skift en position til højre fra deres nuværende placering. Følgende illustration giver en visuel repræsentation af dette koncept:
Zag-Zig Rotation
Nedenfor er C++-koden til at implementere rotationer i Splay-træet:
C++ #include using namespace std; struct Node { int key; Node *left, *right; }; Node* newNode(int key) { Node* node = new Node(); node->nøgle = nøgle; node->venstre = node->højre = nullptr; returknude; } Node* rightRotate(Node* x) { Node* y = x->venstre; x->venstre = y->højre; y->højre = x; returnere y; } Node* leftRotate(Node* x) { Node* y = x->right; x->højre = y->venstre; y->venstre = x; returnere y; } Node* splay(Node* root, int key) { if (root == nullptr || root->key == key) returner root; if (rod->tast> nøgle) { if (rod->venstre == nullptr) returnerer rod; if (rod->venstre->tast>tast) { root->venstre->venstre = splay(rod->venstre->venstre, nøgle); root = højreRotate(rod); } andet hvis (rod->venstre->tast< key) { root->venstre->højre = splay(rod->venstre->højre, nøgle); hvis (rod->venstre->højre != nullptr) root->venstre = venstreRoter(rod->venstre); } returnere (rod->venstre == nullptr) ? root : rightRotate(rod); } else { if (root->right == nullptr) returner root; if (rod->højre->tast>tast) { root->højre->venstre = splay(rod->højre->venstre, nøgle); if (rod->højre->venstre != nullptr) root->højre = højreRoter(rod->højre); } andet hvis (rod->højre->tast< key) { root->højre->højre = splay(rod->højre->højre, nøgle); root = venstreRoter(rod); } returnere (root->right == nullptr) ? root : leftRotate(rod); } } Node* insert(Node* root, int key) { if (root == nullptr) return newNode(key); root = splay(rod, nøgle); hvis (rod->nøgle == nøgle) returnerer rod; Node* node = newNode(nøgle); if (rod->tast> nøgle) { node->højre = rod; node->venstre = rod->venstre; root->venstre = nullptr; } andet { node->venstre = rod; node->right = root->right; root->right = nullptr; } returknude; } void preOrder(Node* node) { if (node != nullptr) { cout<< node->nøgle<< ' '; preOrder(node->venstre); forudbestilling(node->højre); } } int main() { Node* root = nullptr; root = indsæt(rod, 100); root = indsæt(rod, 50); root = indsæt(rod, 200); root = indsæt(rod, 40); root = indsæt(rod, 60); cout<< 'Preorder traversal of the modified Splay tree:' << endl; preOrder(root); return 0; }> Java // Java Program for the above approach class Node { public int key; public Node left, right; } class SplayTree { static Node newNode(int key) { Node node = new Node(); node.key = key; node.left = node.right = null; return node; } static Node rightRotate(Node x) { Node y = x.left; x.left = y.right; y.right = x; return y; } static Node leftRotate(Node x) { Node y = x.right; x.right = y.left; y.left = x; return y; } static Node splay(Node root, int key) { if (root == null || root.key == key) return root; if (root.key>key) { if (root.left == null) returnerer root; if (root.left.key> key) { root.left.left = splay(root.left.left, key); root = højreRotate(rod); } andet hvis (root.venstre.tast< key) { root.left.right = splay(root.left.right, key); if (root.left.right != null) root.left = leftRotate(root.left); } return (root.left == null) ? root : rightRotate(root); } else { if (root.right == null) return root; if (root.right.key>key) { root.right.left = splay(root.right.left, key); if (root.right.left != null) root.right = rightRotate(root.right); } andet hvis (root.right.key< key) { root.right.right = splay(root.right.right, key); root = leftRotate(root); } return (root.right == null) ? root : leftRotate(root); } } static Node insert(Node root, int key) { if (root == null) return newNode(key); root = splay(root, key); if (root.key == key) return root; Node node = newNode(key); if (root.key>key) { node.right = root; node.left = root.venstre; root.left = null; } andet { node.left = root; node.right = root.right; root.right = null; } returknude; } static void preOrder(Node node) { if (node != null) { System.out.println(); System.out.print(node.key + ' '); forudbestilling(node.venstre); forudbestilling(node.right); } } public static void main(String[] args) { Node root = null; root = indsæt(rod, 100); root = indsæt(rod, 50); root = indsæt(rod, 200); root = indsæt(rod, 40); root = indsæt(rod, 60); System.out.println('Forudbestil gennemgang af det ændrede Splay-træ:'); forudbestilling(rod); } } // Denne kode er bidraget af princekumaras> Python3 class Node: def __init__(self, key): self.key = key self.left = None self.right = None def new_node(key): return Node(key) def right_rotate(x): y = x.left x.left = y.right y.right = x return y def left_rotate(x): y = x.right x.right = y.left y.left = x return y def splay(root, key): if root is None : return new_node(key) if root.key == key: return root if root.key>nøgle: hvis root.left er Ingen: returner root hvis root.left.key> nøgle: root.left.left = splay(root.left.left, key) root = right_rotate(root) elif root.left.key< key: root.left.right = splay(root.left.right, key) if root.left.right: root.left = left_rotate(root.left) return root.left if root.left is None else right_rotate(root) else: if root.right is None: return root if root.right.key>key: root.right.left = splay(root.right.left, key) if root.right.left: root.right = right_rotate(root.right) elif root.right.key< key: root.right.right = splay(root.right.right, key) root = left_rotate(root) return root.right if root.right is None else left_rotate(root) def insert(root, key): if root is None: return new_node(key) root = splay(root, key) if root.key == key: return root node = new_node(key) if root.key>nøgle: node.right = root node.left = root.left root.left = Ingen andre: node.left = root node.right = root.right root.right = Ingen returner node def pre_order(node): if node: print (node.key, end=' ') pre_order(node.left) pre_order(node.right) if __name__ == '__main__': root = Ingen root = indsæt(rod, 100) root = indsæt(rod , 50) root = insert(root, 200) root = insert(root, 40) root = insert(root, 60) print('Forudbestil gennemgang af det ændrede Splay-træ:') pre_order(root)> C# // C# program for the above approach using System; class Node { public int key; public Node left, right; } class SplayTree { static Node newNode(int key) { Node node = new Node(); node.key = key; node.left = node.right = null; return node; } static Node rightRotate(Node x) { Node y = x.left; x.left = y.right; y.right = x; return y; } static Node leftRotate(Node x) { Node y = x.right; x.right = y.left; y.left = x; return y; } static Node splay(Node root, int key) { if (root == null || root.key == key) return root; if (root.key>key) { if (root.left == null) returnerer root; if (root.left.key> key) { root.left.left = splay(root.left.left, key); root = højreRotate(rod); } andet hvis (root.venstre.tast< key) { root.left.right = splay(root.left.right, key); if (root.left.right != null) root.left = leftRotate(root.left); } return (root.left == null) ? root : rightRotate(root); } else { if (root.right == null) return root; if (root.right.key>key) { root.right.left = splay(root.right.left, key); if (root.right.left != null) root.right = rightRotate(root.right); } andet hvis (root.right.key< key) { root.right.right = splay(root.right.right, key); root = leftRotate(root); } return (root.right == null) ? root : leftRotate(root); } } static Node insert(Node root, int key) { if (root == null) return newNode(key); root = splay(root, key); if (root.key == key) return root; Node node = newNode(key); if (root.key>key) { node.right = root; node.left = root.venstre; root.left = null; } andet { node.left = root; node.right = root.right; root.right = null; } returknude; } static void preOrder(Node node) { if (node != null) { Console.Write(node.key + ' '); forudbestilling(node.venstre); forudbestilling(node.right); } } public static void Main(string[] args) { Node root = null; root = indsæt(rod, 100); root = indsæt(rod, 50); root = indsæt(rod, 200); root = indsæt(rod, 40); root = indsæt(rod, 60); Console.WriteLine( 'Forudbestil gennemgang af det ændrede Splay-træ:'); forudbestilling(rod); } } // Denne kode er bidraget af Prince Kumar> Javascript // Javascript code addition class Node { constructor(key) { this.key = key; this.left = null; this.right = null; } } class SplayTree { static newNode(key) { const node = new Node(key); return node; } static rightRotate(x) { const y = x.left; x.left = y.right; y.right = x; return y; } static leftRotate(x) { const y = x.right; x.right = y.left; y.left = x; return y; } static splay(root, key) { if (root == null || root.key == key) { return root; } if (root.key>key) { if (root.left == null) { returner root; } if (root.left.key> key) { root.left.left = SplayTree.splay(root.left.left, key); root = SplayTree.rightRotate(rod); } andet hvis (root.venstre.tast< key) { root.left.right = SplayTree.splay(root.left.right, key); if (root.left.right != null) { root.left = SplayTree.leftRotate(root.left); } } return root.left == null ? root : SplayTree.rightRotate(root); } else { if (root.right == null) { return root; } if (root.right.key>key) { root.right.left = SplayTree.splay(root.right.left, key); if (root.right.left != null) { root.right = SplayTree.rightRotate(root.right); } } andet hvis (root.right.key< key) { root.right.right = SplayTree.splay(root.right.right, key); root = SplayTree.leftRotate(root); } return root.right == null ? root : SplayTree.leftRotate(root); } } static insert(root, key) { if (root == null) { return SplayTree.newNode(key); } root = SplayTree.splay(root, key); if (root.key == key) { return root; } const node = SplayTree.newNode(key); if (root.key>key) { node.right = root; node.left = root.venstre; root.left = null; } andet { node.left = root; node.right = root.right; root.right = null; } returknude; } static preOrder(node) { if (node != null) { console.log(node.key + ' '); SplayTree.preOrder(node.venstre); SplayTree.preOrder(node.right); } } } lad root = null; root = SplayTree.insert(root, 100); root = SplayTree.insert(root, 50); root = SplayTree.insert(root, 200); root = SplayTree.insert(root, 40); root = SplayTree.insert(root, 60); console.log('Forudbestil gennemgang af det ændrede Splay-træ:'); SplayTree.preOrder(rod); // Koden er bidraget af Nidhi goel.> Produktion
Preorder traversal of the modified Splay tree:>
Ulemper ved splay tree datastruktur:
- Ubalancerede træer: Splaytræer kan blive ubalancerede og ineffektive, hvis træet gentagne gange roteres i samme retning.
- Hukommelsesbrug: Splay-træer kan bruge meget hukommelse sammenlignet med andre datastrukturer, fordi hver node indeholder yderligere information.
- Kompleksitet: Splay-træer kan have en høj tidskompleksitet for grundlæggende operationer såsom indsættelse og sletning, fordi træerne skal omorganiseres efter hver operation.
- Omorganiseringsomkostninger: Den spredeoperation, der kræves i hver operation, kan være tidskrævende og resultere i en høj overhead.
- Tilfælde med begrænset brug : Splay-træer er ikke egnede til alle datastrukturer og har begrænsede anvendelsestilfælde, fordi de ikke håndterer duplikerede nøgler effektivt.
Anvendelser af splay-træet:
- Caching : Splay-træer kan bruges til at implementere cachehukommelsesstyring, hvor de oftest tilgåede elementer flyttes til toppen af træet for hurtigere adgang.
- Databaseindeksering : Splay-træer kan bruges til at indeksere databaser for hurtigere søgning og genfinding af data.
- Filsystemer : Splay-træer kan bruges til at gemme filsystemmetadata, såsom allokeringstabellen, mappestruktur og filattributter.
- Datakomprimering: Splay-træer kan bruges til at komprimere data ved at identificere og indkode gentagne mønstre.
- Tekstbehandling : Splay-træer kan bruges i tekstbehandlingsapplikationer, såsom stavekontrol, hvor ord gemmes i et splay-træ til hurtig søgning og genfinding.
- Grafalgoritmer: Splay-træer kan bruges til at implementere grafalgoritmer, såsom at finde den korteste vej i en vægtet graf.
- Online spil: Splay-træer kan bruges i onlinespil til at gemme og administrere højscore, ranglister og spillerstatistikker.
Sikker på, her er nogle fordele og ulemper ved sprøjtetræer, samt nogle anbefalede bøger til at lære mere om emnet:
Fordele ved Splay Trees:
Splay-træer har amortiseret tidskompleksitet af O(log n) for mange operationer, hvilket gør dem hurtigere end mange andre balancerede trædatastrukturer i nogle tilfælde.
Splay-træer er selvjusterende, hvilket betyder, at de automatisk balancerer sig selv, når genstande indsættes og fjernes. Dette kan hjælpe med at undgå den præstationsforringelse, der kan opstå, når et træ kommer i ubalance.
Ulemper ved Splay Trees:
Splay-træer kan have worst-case tidskompleksitet på O(n) for nogle operationer, hvilket gør dem mindre forudsigelige end andre balancerede trædatastrukturer som AVL-træer eller rød-sorte træer.
Splay-træer er muligvis ikke egnede til visse applikationer, hvor forudsigelig ydeevne er påkrævet.
Anbefalede bøger om Splay Trees:
Datastrukturer og algoritmeanalyse i Java af Mark Allen Weiss
Introduktion til algoritmer af Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest og Clifford Stein
Datastrukturer og algoritmer i C++ af Michael T. Goodrich og Roberto Tamassia
Konklusion:
Afslutningsvis er Splay Trees en dynamisk selvbalancerende binær søgetræ-datastruktur, der giver en effektiv måde at søge, indsætte og slette elementer på. De adskiller sig fra traditionelle balancerede binære søgetræer som AVL og rød-sorte træer, da de omorganiserer træet efter hver operation for at bringe den nyligt tilgåede node til roden. Dette er med til at reducere træets højde og resulterer i hurtigere operationer. Splay Trees er meget fleksible og kan tilpasses til forskellige anvendelsestilfælde. Selvom de kan have en højere overhead med hensyn til rotationer, gør deres enkelhed og alsidighed dem til nyttige værktøjer til at løse en lang række problemer.
lambda funktion java