Algoritmer og Datastrukturer

Spørgsmål 1

Antag vi ønsker at understøtte operationen Pred(x) på nedenstående fire datastrukturer, som returnerer det største element i datastrukturen mindre end x. F.eks. for mængden $\{1, 2, 4, 7, 8\}$ er Pred(5) = 4. Angiv for hver af datastrukturerne hvor lang tid det vil tage at udføre Pred(x).

	$\mathcal{O}(1)$	$\mathcal{O}(\log n)$	$\mathcal{O}(n)$
Enkelt-kædet sorteret liste?
Dobbelt-kædet sorteret liste?
Binær min-heap?
Rød-sort søge-træ?

Spørgsmål 2

Consider a binary search tree that is not self-balancing. What is the worst-case time to perform the following operations?

	$\Theta(1)$	$\Theta(\log n)$	$\Theta(n)$	$\Theta(n \log n)$
Traverse the tree (visit every stored element) in order.
Build the tree from an unsorted list.
Insert an element.
Delete an element.
Rotate an edge.

Spørgsmål 3

Consider a red-black tree. Decide for each of the following statements whether it is true or false.

	True	False
The depth of the deepest leaf is at most twice the depth of the most shallow leaf.
A red node must have a red sibling.
At least half of all internal nodes must be black.
At least half of all leafs must be black.

Algoritmer og Datastrukturer

Search trees

Spørgsmål 1

Spørgsmål 2

Spørgsmål 3