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
درخت bst چیست؟
قوانین ایجاد تاپیک در تالار
پاسخ با نقل قول