Binary Search Tree: Insert and Search

যে tree সংখ্যাগুলো সাজিয়ে রাখে, যাতে left বা right-এ গিয়ে যেকোনো সংখ্যা খুঁজে পাওয়া যায়।

মূল ধারণা (tree আকারে সাজানো phone book)

Binary search tree (BST) প্রতিটি node-এ একটি নিয়ম মানে: left subtree-র সবকিছু ছোট, right subtree-র সবকিছু বড়। এটা আসলে binary search-কে একটা আকার দেওয়া: প্রতিটি node-এ আপনি জিজ্ঞেস করেন "আমার সংখ্যাটা কি ছোট, না বড়?" এবং বাকিটার অর্ধেক বাদ দেন।

Tree balanced থাকলে প্রতিটি ধাপে সমস্যা অর্ধেক হয়, তাই lookup দ্রুত হয়। কিন্তু insert-এর order গুরুত্বপূর্ণ: আগে থেকে sorted সংখ্যা insert করে দেখুন tree-র আকার কী হয়।

Run করে দেখুন

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity, সহজ ভাষায়: search বা insert root থেকে একটা path ধরে যায়, তাই খরচ প্রায় tree-র height-এর সমান। 1,000,000 মানের balanced tree-র height প্রায় 20 (O(log n)); chain-এর মতো tree-র height n (O(n))।