Föreläsning 6

Question 1

Vilket är en bra anledning att implementera en symboltabell som ett binärt sökträd istället för en sorterad array?

Answer 1

Man behöver kunna lägga till nya nycklar efter hand

Question 2

Hur lång tid tar det att sätta in ett nytt element i ett binärt sökträd där det tidigare fanns N element?

Answer 2

Proportionellt mot höjden på trädet

Question 3

En symboltabell kan implementeras med hjälp av olika underliggande datastrukturer. Para ihop varje implementation med rätt egenskap.

Binärt sökträd
Hashtabell
Stack
Oordnad länkad lista

Answer 3

Binärt sökträd: Tiden för put och get är förväntad logaritmisk i antal element, för slumpmässiga instättningar.

Hashtabell: Tiden för put och get är förväntad konstant i antal element, för slumpmässiga insättningar

Stack: Inte lämplig datastruktir för att implementera symboltabell .

Oordnad länkad lista: Tiden för put och get är förväntad linjär, för slumpmässiga insättningar.