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