درخت bst چیست؟

[Hussain<ELite>]

درخت bst چیست؟

[whitehat]

درخت جستجوی باینری (http://en.wikipedia.org/wiki/Binary_search_tree)
(روی عبارت کلیک کنید)

[mansourehk]

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