شجرة بحث اثناني
المحتويات

تعريفًا بالموضوع، في علم الحاسوب، شجرة البحث الاثنانية اختصارًا (BST)، والتي يطلق عليها كذلك أحيانًا شجرة بحث اثنانية مرتبة أو منظمة، هي شجرة ثنائية التي لديها هذه الخصائص التالية:
وفي السياق ذاته، الشجرة الجزئية اليمنى لعقدة ما تحتوي فقط على عقد مع قيم أكبر من قمية العقدة نفسها.
من جانب آخر، كلتا الشجرتين الجزئيتين اليمنى واليسرى هما شجرتا بحث ثنائيتان.
وفي هذا السياق، الميزة الرئيسية لأشجار البحث الثنائيين على بنى بيانات هي أن خوارزميات الفرز وخوارزميات البحث المتعلقة بالإمكان أن تكون كفؤ جدا.
علاوةً على ذلك، بشكل عام، المعلومات التي تمثلها كل عقدة هي سجلات وليست فقط عناصر بيانات أحادية.
من جانب آخر، الشجرة الجزئية اليسرى لعقدة ما تحتوي فقط على عقد مع قيم أقل من قمية العقدة نفسها.
return node.value # found key
أو بلغة هاسكل:
إدخال
void InsertNode(Node* &treeNode, Node *newNode)
علاوةً على ذلك، /* Inserts the node pointed to by "newNode" into the subtree rooted at "treeNode" */
علاوةً على ذلك، يبدأ الإدخال كما يبدأ البحث; إذا لم تكن القيمة المراد إدخالها مساوية للجذر، نبحث في الشجرة الفرعية اليسرى أو اليمنى كما من قبل. أخيرا، سنصل إلى عقدة خارجية ونضيف القيمة كابن يميني أو يساري، اعتمادا على قيمة العقدة. وبعبارة أخرى، نفحص الجذر وندخل العقدة الجديدة في الشجرة الفرعية اليسرى إذا كانت قيمتها أصغر من قمية الجذر، أو في الشجرة الفرعية اليمنى إذا كانت قيمتها أكبر من قيمة الجذر.
هكذا يمكن تنفيذ إدخال في شجرة البحث الاثنانية بسي++:
عمليات
علاوةً على ذلك، العمليات على شجرة البحث الاثنانية تطلب مقارنات بين العقد. هذه المقارنات تتم عن طريق استدعاء مقارن (comparator)، والذي هو عبارة عن دالة التي تحسب الترتيب لأي قيمتين. ويكون معرفا حسب اللغة المنفذة بها الشجرة.
tree = None
for v in values:
tree = binary_tree_insert(tree, v)
}
- 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);
- }
- }
- }
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).
شجرة التحليل
شجرة فنويك (تُعرف كذلك باسم الشجرة المفهرسة الاثنانية).
}
- وهنا تنفيذ بالطريقة التكرارية للإدخال في شجرة البحث الاثنانية في جافا:
- 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);
- }
result = []
- traverse_binary_tree(root, lambda element: result.append(element))
- return result
- مراجع
ترتيب
def build_binary_tree(values):
من جهة ثانية، بالإمكان استخدام شجرة البحث الاثنانية لتنفيذ خوارزمية بحث كفئة. ندخل كل القيم المراد ترتيها إلى شجرة بحث اثنانية، وفيما بعد نمر على الشجرة بالترتيب بانين النتيجة:
treeNode = newNode;
- else if (newNode->key < treeNode->key)
- InsertNode(treeNode->left, newNode);
- else
- InsertNode(treeNode->right, newNode);
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
{
if (treeNode == NULL)
بحث
- هذه هي خوارزمية البحث في لغة بايثون:
- # 'node' refers to the parent-node in this case
- def search_binary_tree(node, key):
- if node is None:
كذلك، البحث في شجرة بحث اثنانية على قيمة معينة يمكن أن يكون عوديا (recursive) أو تكرايا (iterative). الشرح هنا يغطي الطريقة العودية.
وفي السياق ذاته، نبدأ بفحص العقدة الجذر. إذا كانت الشجرة null، إذن القيمة المراد البحث عنها لا توجد في الشجرة. وإلا، إذا كانت القيمة مساوية للجذر، ينجح البحث. إذا كانت القيمة أصغر من الجذر، نبحث في الشجرة الفرعية اليسرى. بصورة مشابهة، إذا كانت أكبر من الجذر، نبحث في الشجرة الفرعية اليمنى. نكرر هذه العملية حتى يتم إيجاد القيمة أو نصل إلا شجرة فرعية null. إذا لم يتم إيجاد القيمة المراد البحث عنها قبل أن نصل إلى شجرة فرعية null، إذن العنصر غير موجود في الشجرة.
EQ -> Just nodeValue
- 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;
- }
في هذا الإطار، على افتراض أن BinarySearchTree هي كلاس يحتوي على دالة (search(int ومؤشر إلى العقدة الجذر، الخوارزمية كذلك منفذة بالطريقة التكرارية.
علاوةً على ذلك، هذه العملية تطلب زمن (O(log n بالحالة المتوسطة، ولكن تطلب (O(n بأسوء حالة.
searchBinaryTree _ NullNode = Nothing
- searchBinaryTree key (Node nodeKey nodeValue (leftChild, rightChild))
- case compare key nodeKey of
- LT -> searchBinaryTree key leftChild
- GT -> searchBinaryTree key rightChild
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟