bináris keresőfa
Kiejtés
- IPA: [ ˈbinaːriʃkɛrɛʃøːfɒ]
Főnév
- (matematika, algoritmusok, gráfelmélet) A bináris keresőfa egy bináris fa adatszerkezet, amelyben minden csomópont betartja a keresőfa tulajdonságot: - A bal részfa minden csomópontjának értéke kisebb, mint az adott csomópont értéke. - A jobb részfa minden csomópontjának értéke nagyobb, mint az adott csomópont értéke.
Tulajdonságok
- Struktúra:
- Minden csomópont legfeljebb két gyerekkel rendelkezik (bal és jobb gyerek).
- Az adatok a fa bal és jobb részében rendezetten helyezkednek el.
- Alapműveletek:
- Beszúrás: Új elem hozzáadása a fa megfelelő helyére.
- Keresés: Egy adott érték megkeresése a fában.
- Törlés: Egy csomópont eltávolítása, a fa tulajdonságainak megőrzésével.
- Időkomplexitás:
- Legjobb eset (kiegyensúlyozott fa): (O(n)).
- Legrosszabb eset (egyenetlen fa, láncolt lista): (O(n)).
Pszeudokód
Beszúrás
Insert(node, key):
ha node üres:
hozz létre egy új csomópontot a key értékkel
ha key < node.value:
node.left = Insert(node.left, key)
különben:
node.right = Insert(node.right, key)
térj vissza node
Keresés
Search(node, key):
ha node üres vagy node.value == key:
térj vissza node
ha key < node.value:
térj vissza Search(node.left, key)
különben:
térj vissza Search(node.right, key)
Törlés
Delete(node, key):
ha node üres:
térj vissza node
ha key < node.value:
node.left = Delete(node.left, key)
ha key > node.value:
node.right = Delete(node.right, key)
különben:
ha node.left üres:
térj vissza node.right
ha node.right üres:
térj vissza node.left
successor = Minimum(node.right)
node.value = successor.value
node.right = Delete(node.right, successor.value)
térj vissza node
Python implementáció
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, node, key):
if node is None:
return TreeNode(key)
if key < node.value:
node.left = self.insert(node.left, key)
else:
node.right = self.insert(node.right, key)
return node
def search(self, node, key):
if node is None or node.value == key:
return node
if key < node.value:
return self.search(node.left, key)
return self.search(node.right, key)
def delete(self, node, key):
if node is None:
return node
if key < node.value:
node.left = self.delete(node.left, key)
elif key > node.value:
node.right = self.delete(node.right, key)
else:
if node.left is None:
return node.right
if node.right is None:
return node.left
successor = self.get_min(node.right)
node.value = successor.value
node.right = self.delete(node.right, successor.value)
return node
def get_min(self, node):
while node.left:
node = node.left
return node
def inorder(self, node):
if node:
self.inorder(node.left)
print(node.value, end=" ")
self.inorder(node.right)
# Példa használat
bst = BinarySearchTree()
root = None
keys = [50, 30, 20, 40, 70, 60, 80]
for key in keys:
root = bst.insert(root, key)
print("Inorder bejárás a beszúrás után:")
bst.inorder(root)
print()
# Keresés
result = bst.search(root, 40)
print("Keresés eredménye:", result.value if result else "Nincs ilyen elem")
# Törlés
root = bst.delete(root, 20)
print("Inorder bejárás törlés után:")
bst.inorder(root)
print()
Kimenet:
Inorder bejárás a beszúrás után: 20 30 40 50 60 70 80 Keresés eredménye: 40 Inorder bejárás törlés után: 30 40 50 60 70 80
C++ implementáció
#include <iostream>
using namespace std;
struct TreeNode {
int value;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};
class BinarySearchTree {
public:
TreeNode* insert(TreeNode* node, int key) {
if (!node) return new TreeNode(key);
if (key < node->value)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
TreeNode* search(TreeNode* node, int key) {
if (!node || node->value == key)
return node;
if (key < node->value)
return search(node->left, key);
return search(node->right, key);
}
TreeNode* deleteNode(TreeNode* node, int key) {
if (!node) return node;
if (key < node->value) {
node->left = deleteNode(node->left, key);
} else if (key > node->value) {
node->right = deleteNode(node->right, key);
} else {
if (!node->left) return node->right;
if (!node->right) return node->left;
TreeNode* successor = getMin(node->right);
node->value = successor->value;
node->right = deleteNode(node->right, successor->value);
}
return node;
}
TreeNode* getMin(TreeNode* node) {
while (node->left) node = node->left;
return node;
}
void inorder(TreeNode* node) {
if (!node) return;
inorder(node->left);
cout << node->value << " ";
inorder(node->right);
}
};
int main() {
BinarySearchTree bst;
TreeNode* root = nullptr;
int keys[] = {50, 30, 20, 40, 70, 60, 80};
for (int key : keys) {
root = bst.insert(root, key);
}
cout << "Inorder bejárás a beszúrás után:" << endl;
bst.inorder(root);
cout << endl;
// Keresés
TreeNode* result = bst.search(root, 40);
cout << "Keresés eredménye: " << (result ? result->value : -1) << endl;
// Törlés
root = bst.deleteNode(root, 20);
cout << "Inorder bejárás törlés után:" << endl;
bst.inorder(root);
cout << endl;
return 0;
}
Kimenet:
Inorder bejárás a beszúrás után: 20 30 40 50 60 70 80 Keresés eredménye: 40 Inorder bejárás törlés után: 30 40 50 60 70 80
Összegzés
Előnyök:
- Könnyen érthető és implementálható.
- Hatékony beszúrás, törlés és keresés kiegyensúlyozott esetekben ((O(n))).
Hátrányok:
- Kiegyensúlyozatlanság: Szélsőséges esetekben a fa magassága (O(n))-re nőhet.
- Az AVL- vagy Red-Black-fákhoz képest kevésbé hatékony kiegyensúlyozatlan adathalmazok esetén.
A bináris keresőfa alapvető adatszerkezet, amely a rendezés és a keresés alapjául szolgál, de összetettebb problémák esetén kiegyensúlyozott változatai előnyösebbek.
Fordítások
- angol: binary search tree (en)
- orosz: двоичное дерево поиска (ru) (dvoičnoje derevo poiska)
- bináris keresőfa - Értelmező szótár (MEK)
- bináris keresőfa - Etimológiai szótár (UMIL)
- bináris keresőfa - Szótár.net (hu-hu)
- bináris keresőfa - DeepL (hu-de)
- bináris keresőfa - Яндекс (hu-ru)
- bináris keresőfa - Google (hu-en)
- bináris keresőfa - Helyesírási szótár (MTA)
- bináris keresőfa - Wikidata
- bináris keresőfa - Wikipédia (magyar)