Algoritmer? hjælp

på dansk_:

Antag du har et træ, (fx et binært træ, som kan ses på billedet, (men løsningen skal virke for alle mulige træer)), du skal nu beskrive en simple datastruktur (en måde at gemme data på), så spørgsmålet: Er knude x forfader til knude y (altså ligger knude x over knude y i træet, OG i samme undertræ, på eksemplet vil den øverste knude være forfader til alle, 5 til alle i højre undertræ osv..) kan besvares.

(in a nutshell: "Du har et træ som på billedet, du bliver givet 2 knuder, nu skal du sige om den ene knude ligger over den anden... Givet fx 5 og 11 er svaret nej, givet 5 og 9 er svaret ja.")

Jeg synes ikke du oversætter korrekt. Du har slet ikke "space-efficient" og "in constant time" med.

Med "constant time" kunne man forestille sig et dobbeltarray, begge indexer er knuder. Der står "1" hvis den ene er en forfader til den anden, og "0" ellers. Men den er nok ikke "space-efficient".

Hvad har du lært om det?