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

عمليات

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