EMZETT.Glossar
736 Begriffe aus IT, Netzwerk, Sicherheit und Programmierung: erst kurz erklärt, dann ausführlicher. Suche nach einem Wort oder wähle einen Buchstaben.
2 Treffer
Binäre Suche Die binäre Suche findet ein Element in einer sortierten Liste, indem sie den Suchbereich immer wieder halbiert – statt alle Elemente einzeln zu prüfen.
Sie vergleicht den gesuchten Wert mit dem mittleren Element: Ist er kleiner, geht es links weiter, ist er größer, rechts. Dadurch braucht sie bei n Elementen nur etwa log₂(n) Schritte – bei einer Million Elementen höchstens 20 (Laufzeit O(log n), siehe Big-O-Notation). Voraussetzung ist eine sortierte Datenmenge mit Indexzugriff.
Verwandt: Algorithms (Algorithmen) · Index · Baum (Datenstruktur) · Big-O-Notation · Mergesort · Sorting (Sortieren)
Ganzer Artikel im Wiki →Baum (Datenstruktur) Ein Baum ist eine hierarchische Datenstruktur aus Knoten, die über Kanten verbunden sind: Ein Wurzelknoten hat Kinder, diese wieder Kinder – ohne Kreise.
Bäume bilden Hierarchien ab: Dateisysteme, HTML-Dokumente (DOM), Organigramme und Entscheidungen. Der binäre Suchbaum speichert Werte so, dass links nur kleinere und rechts nur größere Werte hängen – dadurch lässt sich in O(log n) suchen, solange er ausgeglichen ist.
Verwandt: Graph (Datenstruktur) · Queue (Warteschlange) · Stack (Stapel) · Big-O-Notation · Binäre Suche · Compiler
Ganzer Artikel im Wiki →