درخت جستجوی دودویی (Binary Search Tree - BST)، در ریاضیات (Mathematics)
انواع درخت (Tree) را در آموزش زیر شرح دادیم :
درخت جستجوی دودویی (Binary Search Tree - BST) :
این نوع خاصی از درخت دودویی است که با یک خاصیت (Invariant) مهم تعریف می شود: برای هر گره، تمام مقادیر موجود در زیردرخت چپ کوچکتر یا مساوی مقدار گره هستند و تمام مقادیر موجود در زیردرخت راست بزرگتر از مقدار گره هستند. این ویژگی امکان جستجوی سریع را فراهم می کند. میانگین زمان جستجو، درج و حذف در BST متوازن،
\[ O(\log n) \]است. اگر درخت نامتوازن شود، در بدترین حالت (مثل درختی که شبیه لیست پیوندی است) این زمان به
\[ O(n) \]افزایش می یابد. پیمایش (Traversal) این درخت به روش In-Order، خروجی مقادیر را به صورت مرتب شده تحویل می دهد.
نویسنده علیرضا گلمکانی
شماره کلید 5532
گزینه ها 
نظرات 0 0 0