যখন আমরা বিমূর্ত ডেটা টাইপ অভিধান প্রয়োগ করার চেষ্টা করি, তখন নোডটি মানগুলির সাথে যুক্ত হয়। একটি অভিধান মূলত কীগুলির একটি সেট, যা অবশ্যই মোট ক্রম থেকে আঁকা উপাদান হতে হবে। অতিরিক্ত তথ্য থাকতে পারে, যা প্রতিটি কীর সাথে যুক্ত থাকে, কিন্তু এটি কোনো ধারণাগত বোঝার দিকে নিয়ে যায় না।
যদি অভিধানটি গাছ ব্যবহার করে প্রয়োগ করা হয়, তাহলে প্রতিটি নোড অনন্য কী ধারণ করবে। এখানে গাছের প্রতিটি নোড u-এর জন্য, প্রতিটি কী u.l এর থেকে কঠোরভাবে ছোট। এবং u.r-এর প্রতিটি কী, u.k-এর চেয়ে কঠোরভাবে বড়। একটি গাছ এই অপরিবর্তনীয় অনুসারে সংগঠিত হয় যাকে বাইনারি অনুসন্ধান গাছ হিসাবে উল্লেখ করা হয়।
এই ইনভেরিয়েন্টের একটি বড় সুবিধা হল, ইন-অর্ডার ট্রাভার্সাল ব্যবহার করে লিনিয়ার টাইমে কীগুলির সাজানো তালিকা পাওয়া যাবে। এটিকে পুনরাবৃত্তিমূলকভাবে নিম্নরূপ সংজ্ঞায়িত করা যেতে পারে − একটি খালি গাছ, কিছুই করবেন না, অন্যথায় প্রথমে বাম সাবট্রিতে পুনরাবৃত্তি করুন, মূলটি নিন এবং রিপোর্ট করুন। তারপর ডান সাবট্রিতে ফিরে যান।
আমরা বাইনারি অনুসন্ধান গাছের জন্য একাধিক অপারেশন করতে পারি। অনুসন্ধানী বেত গাছের উচ্চতার উপর ভিত্তি করে করা হয়। সার্চ করা অন্য সব অপারেশনের চেয়ে গুরুত্বপূর্ণ অপারেশন।
