المحاضرة السادسة عشر - خوارزميات وبنى معطيات 1
شجرة البحث الثنائية (BST) هي شجرة ثنائية تحقق الشروط التالية:
In-order: 5, 15, 22, 30, 35, 60, 70, 80
In-order: 12, 15, 10, 22, 25, 30
(10 < 12 لكنها في اليمين)
البحث عن قيمة محددة في الشجرة
إضافة عقدة جديدة مع الحفاظ على خصائص BST
حذف عقدة مع الحفاظ على خصائص BST
إيجاد أصغر أو أكبر قيمة في الشجرة
struct
Node {
int
data;
struct
Node* left;
struct
Node* right;
};
typedef struct
Node* BST;
خوارزمية البحث في شجرة BST:
struct
Node* search(BST root,
int
x) {
if
(root ==
NULL
|| root->data == x)
return
root;
if
(x < root->data)
return
search(root->left, x);
return
search(root->right, x);
}
struct
Node* iter_search(BST root,
int
x) {
BST ptr = root;
while
(ptr !=
NULL
) {
if
(ptr->data == x)
return
ptr;
if
(x < ptr->data)
ptr = ptr->left;
else
ptr = ptr->right;
}
return
NULL
;
}
خوارزمية الإضافة إلى شجرة BST:
void
insertNode(BST &root,
int
x) {
if
(root ==
NULL
) {
root =
new
Node();
root->data = x;
root->left = root->right =
NULL
;
}
else
if
(x == root->data)
return
;
else
if
(x < root->data)
insertNode(root->left, x);
else
insertNode(root->right, x);
}
Node
* minNode(BST root) {
while
(root->left !=
NULL
)
root = root->left;
return
root;
}
Node
* maxNode(BST root) {
while
(root->right !=
NULL
)
root = root->right;
return
root;
}
عند حذف عقدة من شجرة BST، هناك ثلاث حالات:
قم بحذف العقدة مباشرة
استبدل العقدة بابنها
استبدل العقدة بأكبر قيمة في اليسار أو أصغر قيمة في اليمين
BST
deleteNode(BST root,
int
x) {
if
(root ==
NULL
)
return
root;
if
(x < root->data)
root->left = deleteNode(root->left, x);
else
if
(x > root->data)
root->right = deleteNode(root->right, x);
else
{
// الحالة 1: عقدة بدون أبناء أو بعمر واحد
if
(root->left ==
NULL
) {
BST temp = root->right;
delete
root;
return
temp;
}
else
if
(root->right ==
NULL
) {
BST temp = root->left;
delete
root;
return
temp;
}
// الحالة 2: عقدة لها ابنان
BST temp = minNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return
root;
}