درخت bst چیست؟

درخت bst چیست؟

درخت جستجوی باینری
(روی عبارت کلیک کنید)

BST مخفف Binary Search Tree به معنای درخت جستجوی دودویی میباشد.
یک درخت جستجوی دودویی دارای ویژگی های زیر است:
1- هر عنصر دارای یک مقدار خاص است و دو عنصر نباید دارای کلید (مقدار) یکسان باشد.(کلید ها منحصر به فردند.)
2- کلید واقع در زیر درخت غیر تهی باید کمتر از مقدار کلید واقع در ریشه باشد.
3- کلید واقع در زیر درخت راست باید بزرگتر از کلید واقع در ریشه باشد.
4- زیر درختان چپ و راست نیز خود درختان جستجوی دودویی میباشند.
انواع درخت جستجوی دودویی وجود دارد که می توان به درختان قرمز و سیاه، درختان 3-2، درختان BTree ، درختان 4-3-2 اشاره کرد، که هر کدام ویژگی های خاص خود را دارند..






الگوریتم جستجو در یک درخت جستجوی دودویی:

function search (x, r) //the pointer r points to the root of a search tree

The function searches for the value x in this tree //

if r =nil then return nil //x is not in the tree

else if x=r.value then return r

else if x<r.value then return search(x, r.leftchild) //calling itself

else return search (x,r.rightchild) //calling itself recursively