Metraipolis › archive › dc_602e83f7232f

Binärer Suchbaum — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/Bin%C3%A4rer_Suchbaum
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-01T12:56:39.738Z
SHA-256 of the archived text
2eaf4e208e73d7f5a44b5e026605188f22dd18c668c07b0b4c3aaa7073f6a441
Stable URL of this page
https://metraipolis.com/documento/dc_602e83f7232f

How to cite

Binärer Suchbaum — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Bin%C3%A4rer_Suchbaum (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_602e83f7232f (Metraipolis archive dc_602e83f7232f, sha256 2eaf4e208e73d7f5a44b5e026605188f22dd18c668c07b0b4c3aaa7073f6a441)
BibTeX
@misc{dc602e83f7232f,
  title = {Binärer Suchbaum — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Bin%C3%A4rer_Suchbaum},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_602e83f7232f; sha256 2eaf4e208e73d7f5a44b5e026605188f22dd18c668c07b0b4c3aaa7073f6a441},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Bin%C3%A4rer_Suchbaum. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In der Informatik ist ein binärer Suchbaum eine Kombination der abstrakten Datenstrukturen Suchbaum und Binärbaum. Ein binärer Suchbaum, häufig abgekürzt als BST (von englisch Binary Search Tree), ist ein binärer Baum, bei dem die Knoten „Schlüssel“ tragen, und die Schlüssel des linken Teilbaums eines Knotens nur kleiner (oder gleich) und die des rechten Teilbaums nur größer (oder gleich) als der Schlüssel des Knotens selbst sind. Was die Begriffe „kleiner gleich“ und „größer gleich“ bedeuten, ist völlig dem Anwender überlassen; sie müssen nur eine Totalordnung (genauer: eine totale Quasiordnung siehe unten) etablieren. Am flexibelsten wird die Ordnungsrelation durch eine vom Anwender zur Verfügung zu stellende 3-Wege-Vergleichsfunktion realisiert. Auch ob es sich um ein einziges Schlüsselfeld oder eine Kombination von Feldern handelt, ist Sache des Anwenders; ferner ob Duplikate (unterschiedliche Elemente, die beim Vergleich aber nicht als „ungleich“ herauskommen) zulässig sein sollen oder nicht. Über Suchfunktionen für diesen Fall siehe unten. Ein in-order-Durchlauf durch einen binären Suchbaum ist äquivalent zum Wandern durch eine sortierte Liste (bei im Wesentlichen gleichem Laufzeitverhalten). Mit anderen Worten: ein binärer Suchbaum bietet ggf. wesentlich mehr Funktionalität (zum Beispiel Durchlauf in der Gegenrichtung und/oder einen „direkten Zugriff“ mit potentiell logarithmischem Laufzeitverhalten – erzielt durch das Prinzip „Teile und herrsche“, das auf der Fernwirkung des Transitivitätsgesetzes beruht) bei einem gleichen oder nur unwesentlich höheren Speicherbedarf.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in tedesco, in ordine alfabetico).
Fonte: Wikipedia in tedesco, voce «Binärer Suchbaum» — https://de.wikipedia.org/wiki/Bin%C3%A4rer_Suchbaum
Wikidata Q623818: «tipo di struttura dati» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q623818
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Bin%C3%A4rer_Suchbaum?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 269830971, consultata il 2026-11-01T12:49:26.694Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 612fac52f2826fbc9d2d57434b685d1ab9d9152d3af8896d6674f5ce78aadadb