Τι είναι ένας κατάλογος παράλειψης (skip list) και πώς επιτυγχάνει O(log n) αναζήτηση;

Question

Accepted Answer

Ένας **κατάλογος παράλειψης** είναι μια διατεταγμένη συνδεδεμένη λίστα που επαυξάνεται με πολλά επίπεδα **"εξπρές λωρίδες"**. Τα υψηλότερα επίπεδα παρακάμπτουν πολλούς κόμβους, οπότε η αναζήτηση κατεβαίνει και κινείται δεξιά, επιτυγχάνοντας **O(log n)** αναμενόμενο χρόνο — όπως μια πιθανολογική, απλούστερη εναλλακτική σε ένα ισορροπημένο δέντρο. ## Δομή ```text L3: head ------------------------> 30 -------> NIL L2: head ----------> 17 ---------> 30 -------> NIL L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (full list) ``` Κάθε κόμβος προωθείται σε υψηλότερα επίπεδα με πιθανότητα `p` (συχνά 0,5), οπότε κατά μέσο όρο κάθε επίπεδο έχει τους μισούς κόμβους από αυτούς που είναι παρακάτω. ## Αναζήτηση ```text search(25): start top-left, move RIGHT while next <= target, else drop DOWN a level. Repeat to level 0. ``` ```python import random def random_level(p=0.5, max_level=16): lvl = 1 while random.random() < p and lvl < max_level: lvl += 1 # coin flips decide a node's height return lvl ``` ## Πολυπλοκότητα | Λειτουργία | Αναμενόμενη | Χώρος | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Ανταλλαγές έναντι ισορροπημένων δέντρων - **Δυνατότητες:** πολύ ευκολότερη εφαρμογή από red-black/AVL· χωρίς περιστροφές· εύκολες concurrent εκδόσεις (χρησιμοποιούνται σε Redis sorted sets, Java `ConcurrentSkipListMap`). - **Ατέλειες:** πιθανολογικές εγγυήσεις (όχι χειρότερη περίπτωση)· επιπλέον δείκτες ανά κόμβο. ## Γιατί έχει σημασία Οι κατάλογοι παράλειψης παρέχουν λειτουργίες O(log n) διατεταγμένες που μοιάζουν με δέντρο με πολύ λιγότερο κώδικα και εύκολη ταυτόχρονη χωρίς κλειδώματα, γι' αυτό τα πραγματικά συστήματα όπως το Redis τα επιλέγουν. Είναι ένα εξαιρετικό παράδειγμα χρήσης **τυχαιοποίησης** για αντικατάσταση περίπλοκης ντετερμινιστικής λογικής ισορρόπησης.