/ Informatik

Datenstrukturen

Adressierung und Speicherbedarf klassischer Datenstrukturen (Array, Linked List, Stack, Queue), Hash-Tabellen-Lastfaktor und Kollisionswahrscheinlichkeit, Binär- und B-Baum-Relationen sowie Heap-Index-Arithmetik.

12 Rechner in dieser Kategorie, jeweils mit automatischer Variablen-Umstellung.

I01

Array Zugriffszeit

Speicheradresse eines Array-Elements aus Basisadresse, Index und Elementgröße: Adresse = Basis + Index · Elementgroesse. Konstante Zeit O(1).

I02

Linked List Zugriffszeit

Anzahl Schritte zum Erreichen eines Elements in einer einfach verketteten Liste: Schritte = Index. Lineare Zeit O(n).

I03

Stack Kapazität

Speicherbedarf eines Stacks bei fester Kapazität: Speicher = Kapazitaet · Elementgroesse. Pre-allokierter Block, kein Overhead pro Element.

I04

Queue Kapazität

Speicherbedarf einer Queue (Ringpuffer) bei fester Kapazität: Speicher = Kapazitaet · Elementgroesse. FIFO-Datenstruktur mit konstantem Pro-Element-Aufwand.

I05

Hash-Tabelle Lastfaktor

Füllgrad einer Hash-Tabelle: alpha = Elemente / Tabellengroesse. Werte α ≈ 0,7 gelten als guter Kompromiss zwischen Speicher und Kollisionsrate.

I06

Hash-Tabelle Kollisionswahrscheinlichkeit

Wahrscheinlichkeit mindestens einer Kollision nach n Einfügungen in m Slots (Geburtstagsparadoxon-Näherung): P = 1 − e^(−n²/(2·m)).

I07

Binärbaum max. Knoten

Maximale Knotenanzahl eines vollständigen Binärbaums bei Tiefe h (Wurzel auf Ebene 0): MaxKnoten = 2^(h+1) − 1. Geometrische Reihe über alle Ebenen.

I08

Binärbaum min. Tiefe

Minimal benötigte Tiefe eines Binärbaums mit n Knoten (vollständig gefüllte Ebenen): MinTiefe = ⌊log₂(n)⌋. Untere Schranke für Suchoperationen.

I09

B-Baum max. Schlüssel

Maximale Schlüsselanzahl in einem B-Baum der Ordnung m und Tiefe h: MaxKeys = m^(h+1) − 1. Grundlage für Indexdimensionierung in Datenbanken.

I10

Heap Eltern-Index

Eltern-Index in einem Array-basierten Heap (0-basiert): Eltern = ⌊(i − 1) / 2⌋. Grundlage von Heapify und Priority-Queues.

I11

Heap Kind-links Index

Index des linken Kindes in einem Array-basierten Heap (0-basiert): Links = 2 · i + 1. Gegenstück zur Eltern-Formel.

I12

Heap Kind-rechts Index

Index des rechten Kindes in einem Array-basierten Heap (0-basiert): Rechts = 2 · i + 2. Gegenstück zu linkem Kind und Eltern-Index.