شجرة بحث ثنائية

شجرة بحث ثنائية

معلومات عامة

صنف فرعي من	شجرة البحث شجرة ثنائية
البداية	1960
يدرسه	نظرية البيان
المكتشف أو المخترع	Andrew Donald Booth (en)
زمن الاكتشاف أو الاختراع	1960
أسوأ حالة تعقيد مكاني	$O(n)$
متوسط التعقيد المكاني	$O(n)$
موصوف في وصلة	https://xlinux.nist.gov/dads/HTML/binarySearchTree.html

في علم الحاسوب، شجرة بحث ثنائية (بالإنجليزية: Binary Search Tree)‏ اختصارًا (BST)، والتي يطلق عليها أيضًا أحيانًا شجرة بحث ثنائية مرتبة أو منظمة، هي شجرة ثنائية التي لديها هذه الخصائص التالية:

• الشجرة الجزئية اليسرى لعقدة ما تحتوي فقط على عقد مع قيم أقل من قمية العقدة نفسها.
• الشجرة الجزئية اليمنى لعقدة ما تحتوي فقط على عقد مع قيم أكبر من قمية العقدة نفسها.
• كلتا الشجرتين الجزئيتين اليمنى واليسرى هما شجرتا بحث ثنائيتان.

بشكل عام، المعلومات التي تمثلها كل عقدة هي سجلات وليست فقط عناصر بيانات أحادية.

الميزة الرئيسية لأشجار البحث الثنائيين على بنى بيانات هي أن خوارزميات الترتيب وخوارزميات البحث المتعلقة بالإمكان أن تكون كفؤ جدا.

عمليات

العمليات على شجرة البحث الثنائية تطلب مقارنات بين العقد. هذه المقارنات تتم عن طريق استدعاء مقارن (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

انظر أيضًا

• شجرة (بنية بيانات)
• شجرة ثنائية
• بنية بيانات
• خوارزمية بحث
• شجرة التحليل
• شجرة فنويك (تُعرف أيضاً باسم الشجرة المفهرسة الثنائية).