Splay tree एक self balancing बाइनरी सर्च ट्री है इसकी property होती है कि यह recently एक्सेस किये elements को दोबारा तेजी से access कर सकता है। Splay tree algorithm की खोज Daniel D. Sleator तथा Robert E. Tarjan ने 1985 में की थी।
यह insertion, searching तथा deletion के ऑपेरशन को पूरा करता है। इन सभी ऑपेरशन का औसत समय O(log n) है जहां n, tree में elements की संख्या होती है। Binary tree की तरह ही इस tree में भी एक node के दो child होते है।
Applications of splay tree (इसके अनुप्रयोग)
इसके अनुप्रयोग निम्नलिखित है:-
- Caches को implement करने के लिए इसका प्रयोग किया जाता है।
- इसमें data को store करने की ability नही होती है जिससे इसका प्रयोग memory के minimization में किया जाता है।
- इसका प्रयोग data compression में भी किया जाता है। जैसे:- huffman coding.
- यह garbage collection में भी use होता है।
- इसका use जो है वह windows NT, gcc compiler, fore system network routers, unix malloc आदि में किया जाता है।
Advantage of splay tree
इसके लाभ निम्नलिखित है।
- इसको implement करना अन्य self balancing binary trees की तुलना में आसान है।
- AVL तथा red black trees की तुलना में इसके code आसान है।
- इसमें information के लिए बहुत ही कम memory space की आवश्यकता होती है।
Disadvantage of splay tree
इसकी हानियाँ निम्नलिखित है:-
- Search operations के दौरान बहुत adjustments करनी पड़ती है।
- Individual operation बहुत ही expensive होता है।
- इसका मुख्य disadvantage है इसकी height. क्योंकि इसकी height जो है वह linear हो सकती है।