Binární Vyhledávací Strom (BST) je jako strom, ve kterém všechny uzly postupujte podle níže uvedených vlastností −
-
hodnota klíče levého podstromu jsou menší než hodnota jeho rodič (kořenový) uzel je klíč.
-
hodnota klíče pravého pod stromem je větší nebo rovna hodnotě klíče jeho nadřazeného (kořenového) uzlu.,
Tak, BST rozděluje všechny jeho sub-stromy do dvou částí; v levém podstromu a pravém podstromu a mohou být definovány jako −
left_subtree (keys) < node (key) ≤ right_subtree (keys)
Zobrazení
BST je kolekce uzly uspořádány tak, kde se udržují BST vlastnosti. Každý uzel má klíč a přidruženou hodnotu. Při vyhledávání se požadovaný klíč porovnává s klíči v BST a pokud je nalezen, vyvolá se přidružená hodnota.,
Následující vyobrazení BST −
pozorujeme, že kořenový uzel klíč (27) má všechny menší hodnotou klíče v levém podstromu a vyšší hodnotě klíče na pravé sub-tree.
základní operace
následující jsou základní operace stromu-
-
vyhledávání-vyhledá prvek ve stromu.
-
Insert-vloží prvek do stromu.
-
pre-order Traversal-Traverses strom v pre-order způsobem.
-
in-order Traversal-Traverses strom v pořadí způsobem.,
-
Post-order Traversal-Traverses strom post-order způsobem.
Node
Definujte uzel s některými daty, odkazy na jeho levé a pravé podřízené uzly.
struct node { int data; struct node *leftChild; struct node *rightChild;};
operace vyhledávání
kdykoli má být prvek prohledán, začněte hledat z kořenového uzlu. Pokud jsou data menší než hodnota klíče, vyhledejte prvek v levém podstromu. V opačném případě vyhledejte prvek v pravém podstromu. Postupujte podle stejného algoritmu pro každý uzel.,
algoritmus
vložit operaci
vždy, když má být prvek vložen, nejprve vyhledejte jeho správné umístění. Začněte hledat z kořenového uzlu, pak pokud jsou data menší než hodnota klíče, vyhledejte prázdné místo v levém podstromu a vložte data. V opačném případě vyhledejte prázdné místo v pravém podstromu a vložte data.