Wat is een gebalanceerde boom?

Een gebalanceerde boom is een variant van een binaire zoekboom waarin de balans van de hoogte van de subbomen wordt gehandhaafd om efficiënte zoek-, invoeg- en verwijderbewerkingen te garanderen. Het doel van de balans is om de hoogte van de boom te minimaliseren zodat de operaties in een tijdsbestek dicht bij O(log n) worden uitgevoerd.

Voorbeelden van gebalanceerde bomen:

• AVL-boom: houdt de hoogtebalans van de subbomen, waarvan het verschil niet meer dan 1 is.
• Rode-zwart boom: gebruikt kleurmarkeringen in de knooppunten om een geschatte balans te behouden.

De balans wordt bereikt door middel van speciale operaties (bijvoorbeeld rotaties), die de knooppunten herverdelen bij veranderingen in de structuur van de boom.

Dit is belangrijk voor algoritmen en datastructuren waar snelle toegang, invoeging en verwijdering van elementen vereist is.