Vkládání prvků do uspořádaných množin implementovaných polem nebo seznamem je, jak jsme viděli, časově náročné, protože musíme udržet jejich uspořádání. Na druhé straně, pokud vkládáme to těchto implementací dynamických množin prvky bez ohledu na jejich uspořádání, operace vložení jsou rychlé, ale hledání prvků se stane časově náročné. Pro BVS, jak uvidíme, jsou v průměrném případu obě tyto operace efektivní.
Prvky jsou ve vrcholech BVS uspořádány tak, že splňují následující BVS vlastnost:
Nechť x je vrchol stromu.
Je-li y vrchol v levém podstromu, potom y.klíč < x.klíč.
Je-li y vrchol v pravém podstromu, potom y.klíč > x.klíč.
Pro BVS budeme uvažovat, že klíče všech prvků jsou různé. Příklad BVS je na obr.
.
Vlastnost BVS umožňuje vytisknout seřazené klíče ve vrcholech stromu jednoduše inorder průchodem. Inorder průchod vytiskne klíče stromu na obr. v pořadí 1, 2, 3, 4, 5, 6, 7, 8, 9.
Základní operací nad BVS, je hledání hodnoty uložené ve vrcholu podle klíče. Třída DVrchol tedy bude obsahovat navíc člen data, například typu String (obr. 
).
BVS strom je reprezentován svým kořenem
private DVrchol koren;
Pro prázdný strom je
koren == null
Signatura metody hledej( ) podle klíče v našem případě je
String hledej(int)
Z definice BVS přímo plyne její rekurzivní implementace na obr.
. Pokud hledaný prvek není kořenem, rozdělíme množinu prvků vyjádřenou BVS, na dvě podmnožiny, totiž na levý a pravý podstrom a podle toho, je-li klíč hledaného prvku menší nebo větší než kořen určíme, ve kterém podstromu budeme pokračovat. Hledání v BVS je tedy z hlediska časové složitosti stejně efektivní jako binární hledání v uspořádané množině vyjádřené pomocí pole, kde jsme další hledání určovali podle prostředního prvku.
Program na obr. obsahuje koncovou rekurzi, můžeme ho tedy známým způsobem přepsat použitím příkazu cyklu (obr.
). Tento program bude na většině počítačů rychlejší.
Kromě hledání prvku podle klíče, jsme například v článku 4.2 uvedli řešení hledání nejmenšího prvku v poli. Obdobná úloha je nalézt prvek s nejmenším klíčem v BVS. Pro neprázdný strom to znamená sledovat ukazatel na levý podstrom, ve kterém jsou všechny prvky stromu menší než jeho kořen. Dále postupujeme stejně, až levý strom je prázdný. Odpovídající metoda minKlic( ) je na obr.
. Metoda pro nalezení maximálního prvku maxKlic( ) je symetrická a je uvedena také na obr..
Pro BVS je významné, že stejně efektivně jako hledání prvků můžeme implementovat i jejich vkládání. Obdobně jako u hledání prvku, projdeme strom od kořene k místu, kde má být prvek vložen. Pro vybírání prvku je opět vhodné uvědomit si analogii práce se seznamem, kde jsem si řekli, že je užitečné aby prvek obsahoval ukazatel na předchůdce. Rozšíříme tedy i prvek BVS o ukazatel na předchůdce. Modifikovaná třída DVrchol je na obr.
.
Signatura metody vloz je v našem případě
void vloz(int, String)
Její implementace je na obr.
. Pro vložení prvku s klíčem klic ukazatel x prochází strom levým nebo pravým podstromem podle porovnání hodnot klic a x.klic až dosáhne hodnotu null, kam patří vkládaný prvek. Proměnná predch obdobně jako u seznamu udržuje jeho předchůdce, který je uložen do položky predch vkládaného prvku. Nakonec je nastavena hodnota predch.levy nebo predch.pravy na vkládaný prvek.
Pro vybrání prvku ze stromu musíme rozlišovat tři případy. Po prvé, odebíraný prvek je listem, kdy odpovídající ukazatel v jeho přímém předchůdci nastavíme na null, čímž je odpojen od stromu. Příkladem je vrchol s klíčem 1 na obr.
. Po druhé, odebíraný prvek má právě jednoho náslendíka a je vybrán stejně jako tomu bylo u seznamu jeho odpojením změnou odpovídajících ukazatelů. Příkladem je vrchol s klíčem 6 na obr.
. Jedním z těchto ukazatelů může být ukazatel na kořen stromu, je-li vybíraným prvkem kořen s právě jedním potomkem. Třetí případ je, má-li vybíraný prvek dva následníky, kdy pozici tohoto vrcholu musíme zachovat obsazenou, abychom udrželi strukturu BVS. Jeho odebrání provedeme tak, že jeho klíč a data přepíšeme hodnotami jiného prvku a tento odpojíme. Přitom musíme zachovat vlastnost BVS. Uvědomíme-li si, že pravý podstrom odebíraného prvku obsahuje prvky s klíči většími než je klíč tohoto prvku, můžeme ho nahradit minimem pravého stromu, čímž bude zachována vlastnost BVS a tento prvek odpojit. Příklad je na obr.
, kde je ze stromu vybrán prvek s klíčem 2 tak, že se do něj zkopírují hodnoty prvku s klíčem 3 a tento se odpojí. Zde si třeba uvědomit, že minimum uvedeného podstromu může být i jeho kořen.
Signatura metody vyber( ) je v našem případě
void vyber(int)
Její implementace je na obr.
a 
. Na obr. nejprve nalezneme vrchol se zadanou hodnotou klíče. Postup je stejný jako v iterační metodě hledej( ), přičemž po jeho nalezení na něj ukazuje proměnná z. Dále určíme, zda při jeho výběru bude odpojen tento vrchol nebo vrchol s nejmenší hodnotou klíče jeho pravého podstromu. Ukazatel na odpojovaný uzel je uložen v proměnné y. Pro jeho odpojení uložíme na x ukazatel na jeho následníka anebo null pokud ho nemá. Na obr. potom následuje odpojení určeného prvku, přičemž jsou zohledněny situace, na které jsme upozornili při opisu algoritmu, co možná činí kód trochu složitější. Pokud odpojený vrchol nebyl prvkem, který máme ze stromu vybrat, zkopírujeme jeho hodnoty do odebíraného vrcholu (třetí případ). Nakonec uvolníme referenci na odpojený vrchol pro garbage collector.
Uvedený způsob výběru prvku ze stromu s modifikací stromu není jediný. Jiným přístupem, nevyžadujícím modifikaci stromu, je označit vybraný prvek jako neplatný, například použitím logické členské proměnné v třídě DVrchol. Často totiž v aplikaci nemáme mnoho prvků, které jsou ze stromu vybírány, a dokonce můžou být užitečné pokud by jich bylo později opět potřeba.
Další technikou je vytvoření nového stromu pro platné prvky, dosáhl-li počet neplatných vrcholů nějakou mez, což je také častý obecný způsob práce s datovými strukturami.
Všechny operace nad BVS uvedené v tomto článku procházeli stromem od kořene nejvíce k jeho listům. Z toho plyne, že čas jejich výpočtu je O(h), kde h je hloubka stromu. Jaká je tedy výška stromu vytvořeného z náhodné permutace n různých prvků?
Nejhorší případ je zřejmě h = n - 1, kdy strom degeneruje na seznam, protože prvky v permutaci byly uspořádané. Časová složitost uvedených operací tedy je O(n).
Nejlepší případ, nastane když prvky budou vloženy tak, že kromě poslední úrovně, jsou zaplněny všechny vyšší úrovně. Pro h potom platí
2h ≤ N < 2h+1
a h ≈ log2 n. Čas výpočtu uvedených operací tedy je O(log2 n).
Jaký je čas výpočtu těchto operací pro obecný BVS s n vrcholy? Čas uvedených operací je dán hloubkou pozice vkládání a hledání. Zavedeme-li celkovou délku cest P(S) binárního stromu S jakou součet hloubek všech vrcholů, průměrná hloubka vrcholu ve stromu S je P(S)/n. Pro n vrcholů máme n! permutací, z kterých můžeme vytvořit stromy. Obecně v nich bude průměrná hloubka vrcholu různá, můžeme ovšem určit jaká bude pro průměrný případ.
Je-li kořenem BVS i-tý největší prvek, potom v levém podstromě je i-1 vrcholů a v pravém podstromě n-i vrcholů. Označme Pn průměrnou celkovou délku cest BVS s n vrcholy. Vznikl-li vkládáním posloupnosti n prvků, přičemž všechny jejich permutace jsou stejně pravděpodobné, kořenem může být každý z n prvků se stejnou pravděpodobností. Potom platí
kde členy i - 1 a n - i jsou příspěvky kořene k délce cest v levém a pravém podstromu. Její úpravou je
Řešením dostaneme
Pn ≈ 2n ln n = 1,39n log2 n
V průměrném případu je tak průměrná hloubka vrcholu 1,39 log2 n. Čas výpočtu základních operací nad BVS v průměrném případu je tedy O(log2 n).
Poznamenejme, že vybrat prvek ze stromu lze několika způsoby. Obecně vedou k tomu, že strom po odstranění vrcholu nezůstává náhodným, Někdy se průměrná hloubka změní na √n .
V předcházejících úvahách jsme předpokládali, že všechny permutace mají stejnou pravděpodobnost a každé odpovídá nějaký BVS. Odpovídají však každé permutaci různé BVS?
Uložme prvky posloupnosti do mřížky tak, že řádek odpovídá hodnotě a sloupec poloze
Pro posloupnost 3,5,2,4,1 má tato mřížka tvar
x x x x 1
x x 2 x x
3 x x x x
x x x 4 x
x 5 x x x
Získali jsme mřížkovou reprezentaci BVS. V prvním sloupci je jeho kořen, kořen levého podstromu je nejbližší sloupec s prvkem v řádku nad ním a kořen pravého podstromu je nejbližší sloupec s prvkem v řádku pod ním, atd.
Výměnou sloupců odpovídajících vrcholům nad a pod libovolným vrcholem se vyhledávací strom nezmění, zatímco posloupnost, která ho tvoří ano.
Vyměníme-li poslední dva sloupce, získáme mřížku
x x x 1 x
x x 2 x x
3 x x x x
x x x x 4
x 5 x x x
a odpovídající posloupnost je 3,5,2,1,4. Konkrétní BVS je tedy tvořen více posloupnostmi.
Počet všech posloupností z n prvků je n!. Lze ukázat, že počet různých binárních stromů s n vrcholy je
~ 4n/√(πn), obecně tedy veliký počet posloupností odpovídá každému BVS.