شجرة بحث ثنائية
من ويكيبيديا، الموسوعة الحرة
من ويكيبيديا، الموسوعة الحرة
في علم الحاسوب، شجرة بحث ثنائية (بالإنجليزية: Binary Search Tree) اختصارًا (BST)، والتي يطلق عليها أيضًا أحيانًا شجرة بحث ثنائية مرتبة أو منظمة، هي شجرة ثنائية التي لديها هذه الخصائص التالية: [2]
| صنف فرعي من | |
|---|---|
| البداية |
1960  |
| يدرسه | |
| المكتشف أو المخترع | |
| زمن الاكتشاف أو الاختراع |
1960 |
| أسوأ حالة تعقيد مكاني | |
| متوسط التعقيد المكاني | |
بشكل عام، المعلومات التي تمثلها كل عقدة هي سجلات وليست فقط عناصر بيانات أحادية.
الميزة الرئيسية لأشجار البحث الثنائيين على بنى بيانات هي أن خوارزميات الترتيب وخوارزميات البحث المتعلقة بالإمكان أن تكون كفؤ جدا.
العمليات على شجرة البحث الثنائية تطلب مقارنات بين العقد. هذه المقارنات تتم عن طريق استدعاء مقارن (comparator)، والذي هو عبارة عن دالة التي تحسب الترتيب لأي قيمتين. ويكون معرفا حسب اللغة المنفذة بها الشجرة.
البحث في شجرة بحث ثنائية على قيمة معينة يمكن أن يكون عوديا (recursive) أو تكرايا (iterative). الشرح هنا يغطي الطريقة العودية.
نبدأ بفحص العقدة الجذر. إذا كانت الشجرة null، إذن القيمة المراد البحث عنها لا توجد في الشجرة. وإلا، إذا كانت القيمة مساوية للجذر، ينجح البحث. إذا كانت القيمة أصغر من الجذر، نبحث في الشجرة الفرعية اليسرى. بصورة مشابهة، إذا كانت أكبر من الجذر، نبحث في الشجرة الفرعية اليمنى. نكرر هذه العملية حتى يتم إيجاد القيمة أو نصل إلا شجرة فرعية null. إذا لم يتم إيجاد القيمة المراد البحث عنها قبل أن نصل إلى شجرة فرعية null، إذن العنصر غير موجود في الشجرة.
هذه هي خوارزمية البحث في لغة بايثون:
# 'node' refers to the parent-node in this case
def search_binary_tree(node, key):
if node is None:
return None # key not found
if key < node.key:
return search_binary_tree(node.leftChild, key)
elif key > node.key:
return search_binary_tree(node.rightChild, key)
else: # key is equal to node key
return node.value # found key
أو بلغة هاسكل:
searchBinaryTree _ NullNode = Nothing
searchBinaryTree key (Node nodeKey nodeValue (leftChild, rightChild)) =
case compare key nodeKey of
LT -> searchBinaryTree key leftChild
GT -> searchBinaryTree key rightChild
EQ -> Just nodeValue
هذه العملية تطلب زمن (O(log n بالحالة المتوسطة، ولكن تطلب (O(n بأسوء حالة.
على افتراض أن BinarySearchTree هي كلاس يحتوي على دالة
(search(int
ومؤشر إلى العقدة الجذر، الخوارزمية أيضا منفذة بالطريقة التكرارية.
bool BinarySearchTree::search(int val)
{
Node *next = this->root();
while (next != NULL) {
if (val == next->value()) {
return true;
} else if (val < next->value()) {
next = next->left();
} else {
next = next->right();
}
}
// غير موجود
return false;
}
يبدأ الإدخال كما يبدأ البحث; إذا لم تكن القيمة المراد إدخالها مساوية للجذر، نبحث في الشجرة الفرعية اليسرى أو اليمنى كما من قبل. أخيرا، سنصل إلى عقدة خارجية ونضيف القيمة كابن يميني أو يساري، اعتمادا على قيمة العقدة. وبعبارة أخرى، نفحص الجذر وندخل العقدة الجديدة في الشجرة الفرعية اليسرى إذا كانت قيمتها أصغر من قمية الجذر، أو في الشجرة الفرعية اليمنى إذا كانت قيمتها أكبر من قيمة الجذر.
هكذا يمكن تنفيذ إدخال في شجرة البحث الثنائية بسي++:
/* Inserts the node pointed to by "newNode" into the subtree rooted at "treeNode" */
void InsertNode(Node* &treeNode, Node *newNode)
{
if (treeNode == NULL)
treeNode = newNode;
else if (newNode->key < treeNode->key)
InsertNode(treeNode->left, newNode);
else
InsertNode(treeNode->right, newNode);
}
وهنا تنفيذ بالطريقة التكرارية للإدخال في شجرة البحث الثنائية في جافا:
private Node m_root;
public void insert(int data) {
if (m_root == null) {
m_root = new TreeNode(data, null, null);
return;
}
Node root = m_root;
while (root != null) {
// Not the same value twice
if (data == root.getData()) {
return;
} else if (data < root.getData()) {
// insert left
if (root.getLeft() == null) {
root.setLeft(new TreeNode(data, null, null));
return;
} else {
root = root.getLeft();
}
} else {
// insert right
if (root.getRight() == null) {
root.setRight(new TreeNode(data, null, null));
return;
} else {
root = root.getRight();
}
}
}
}
وهنا تنفيذ بالطريقة العودية للإدخال:
private Node m_root;
public void insert(int data){
if (m_root == null) {
m_root = TreeNode(data, null, null);
}else{
internalInsert(m_root, data);
}
}
private static void internalInsert(Node node, int data){
// Not the same value twice
if (data == node.getValue()) {
return;
} else if (data < node.getValue()) {
if (node.getLeft() == null) {
node.setLeft(new TreeNode(data, null, null));
}else{
internalInsert(node.getLeft(), data);
}
}else{
if (node.getRight() == null) {
node.setRight(new TreeNode(data, null, null));
}else{
internalInsert(node.getRight(), data);
}
}
}
بالإمكان استخدام شجرة البحث الثنائية لتنفيذ خوارزمية بحث كفئة. ندخل كل القيم المراد ترتيها إلى شجرة بحث ثنائية، وبعد ذلك نمر على الشجرة بالترتيب بانين النتيجة:
def build_binary_tree(values):
tree = None
for v in values:
tree = binary_tree_insert(tree, v)
return tree
def get_inorder_traversal(root):
'''
Returns a list containing all the values in the tree, starting at *root*.
Traverses the tree in-order(leftChild, root, rightChild).
'''
result = []
traverse_binary_tree(root, lambda element: result.append(element))
return result
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
