প্লে ট্রি একটি স্ব-ভারসাম্যপূর্ণ বাইনারি অনুসন্ধান ট্রি হিসাবে সংজ্ঞায়িত করা হয়েছে অতিরিক্ত সম্পত্তি সহ যা সম্প্রতি অ্যাক্সেস করা উপাদানগুলি আবার অ্যাক্সেস করতে দ্রুত। মৌলিক ক্রিয়াকলাপ যেমন সন্নিবেশ, লুক-আপ এবং অপসারণগুলি স্প্লে ট্রি দ্বারা সঞ্চালিত হয় ও (লগ এন) পরিমার্জিত সময়ে। নন-এলোমেলো অপারেশনের অনেক সিকোয়েন্সের জন্য, স্প্লে ট্রি অন্যান্য সার্চ ট্রির চেয়ে ভালো কাজ করে, এমনকি যখন সিকোয়েন্সের নির্দিষ্ট প্যাটার্ন জানা না থাকে। একটি বাইনারি অনুসন্ধান গাছের সমস্ত স্বাভাবিক ক্রিয়াকলাপ একটি মৌলিক অপারেশনের সাথে যুক্ত হয়, যাকে বলা হয় স্প্লেয়িং৷
ধরা যাক প্রতিটি নোড a-এর জন্য আমরা একটি বাস্তব সংখ্যা কী(a) সংরক্ষণ করি।
যেকোন বাইনারি সার্চ ট্রিতে যেকোন নোডের বাম সাবট্রি a-এ “কী” মান কী(a) এর মানের থেকে ছোট এবং নোড a-এর ডান সাবট্রিতে কী(a) এর মানের থেকে বেশি “কী” মান সহ আইটেম রয়েছে .
স্প্লে ট্রি-তে, আমরা প্রথমে কোয়েরি আইটেমটি অনুসন্ধান করি, একটি সাধারণ বাইনারি অনুসন্ধান গাছের মতো বলে- ক্যোয়ারী আইটেমটিকে মূলের মানের সাথে তুলনা করি, যদি কম হয় তবে বাম সাবট্রিতে পুনরাবৃত্তিমূলকভাবে অনুসন্ধান করি অন্যথায় উচ্চতর হলে, পুনরাবৃত্তভাবে অনুসন্ধান করুন ডান সাবট্রি, এবং যদি এটি সমান হয় তবে আমাদের কাজ শেষ। তারপর, অনানুষ্ঠানিকভাবে বলতে গেলে, আমরা পরপর পূর্বপুরুষের প্রতিটি বিচ্ছিন্ন জোড়ার দিকে তাকাই f a, বলি b =parent(a) এবং c =parent(b), এবং নির্দিষ্ট জোড়ার ঘূর্ণন সম্পন্ন করি। এই ঘূর্ণনের ফলে, c-এর জায়গায় a আসে।
যদি a-এর সঠিক পূর্বপুরুষের বিজোড় সংখ্যা থাকে, তাহলে একটি (যা মূলের সন্তান) এর পূর্বপুরুষকেও আলাদাভাবে মোকাবেলা করতে হবে, টার্মিনাল ক্ষেত্রে- আমরা একটি এবং মূলের মধ্যে প্রান্তটি ঘোরাই। এই ধাপটিকে জিগ স্টেপ হিসাবে চিহ্নিত করা হয়।
যদি a এবং b উভয়ই বাম হয় বা উভয়ই তাদের নিজ নিজ পিতামাতার ডান সন্তান হয়, তাহলে আমরা প্রথমে b এবং এর অভিভাবক c এর মধ্যে প্রান্তটি ঘোরান এবং তারপর a এবং এর পিতামাতার b এর মধ্যে প্রান্তটি ঘোরান৷ এই ধাপটিকে জিগ-জিগ স্টেপ হিসাবে চিহ্নিত করা হয়।
যদি a একটি বাম (যথাক্রমে ডান) শিশু এবং b একটি ডান (যথাক্রমে বাম) শিশু হয়, তাহলে আমরা প্রথমে a এবং b এর মধ্যে প্রান্তটি ঘোরাই এবং তারপর a এবং c এর মধ্যে, এই ধাপটিকে zig-zag ধাপ হিসাবে চিহ্নিত করা হয়। পি>
