binary search tree (tsz. binary search trees)
A Binary Search Tree (röviden: BST, magyarul: bináris keresőfa) egy hierarchikus adatstruktúra, amely a bináris fa és a keresés szabályait egyesíti. Lényegében olyan bináris fa, amely lehetővé teszi a gyors keresést, beszúrást és törlést.
A bináris keresőfa egy rekurzív adatszerkezet, amelyben minden csomópont:
Bal gyermekek értékei kisebbek, Jobb gyermekek értékei nagyobbak, mint a szülőé.
BST a következő számokra: 8, 3, 10, 1, 6, 14, 4, 7, 13
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
| Művelet | Leírás | Időkomplexitás (átlag / legrosszabb) |
|---|---|---|
search(x)
|
Egy érték keresése | O(log n) / O(n) |
insert(x)
|
Új érték beszúrása | O(log n) / O(n) |
delete(x)
|
Adott érték törlése | O(log n) / O(n) |
min()
|
Minimum érték keresése (bal szél) | O(log n) / O(n) |
max()
|
Maximum érték keresése (jobb szél) | O(log n) / O(n) |
💡 Megjegyzés: A legrosszabb eset akkor fordul elő, ha a fa kiegyensúlyozatlan (pl. lánc, mint egy lista).
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
Node* insert(Node* root, int key) {
if (!root) return new Node(key);
if (key < root->data)
root->left = insert(root->left, key);
else
root->right = insert(root->right, key);
return root;
}
bool search(Node* root, int key) {
if (!root) return false;
if (key == root->data) return true;
if (key < root->data)
return search(root->left, key);
else
return search(root->right, key);
}
delete(x))3 eset lehetséges:
O(n)).
| Tulajdonság | BST |
|---|---|
| Sorrendiség | Igen (bal < gyökér < jobb) |
| Átlagos keresés | O(log n) |
| Legrosszabb eset | O(n) (kiegyensúlyozatlan) |
| Memóriahasználat | O(n) |
| Használat | Gyors keresés, rendezés |