Hoofdstuk 4

Question 1

Wat is een complete binaire boom?

Answer 1

Een binarie boom (2 kinderen) die volledig gevuld is behalve eventueel de leaf nodes. Als die niet volledig gevuld is, dan liggen alle nodes zo ver mogelijk naar links.

Met gevolg kan er slechts 1 node zijn met 1 kind.

Question 2

Wat is een heap

Answer 2

Een heap is een compromis tussen een gesorteerde en een ongesorteerde tabel. Het maakt het makkelijk om een maximum of een minimum te vinden in een tabel.

Een heap is een complete binaire boom die voldoet aan de heap voorwaarde. (De waarde van een kind kan nooit groter zijn dan zijn ouder)

Max heap: grootste waarden zit in de wortel
Min heap: kleinste waarde zit in de wortel

Question 3

What is the relation between the number of elements and the height of the heap?

Answer 3

floor(log2(n))

Question 4

Wat is de time complexity van volgende operaties op een heap:

• Search
• Insert
• Delete max/min
• Change value

Answer 4

Search = O(n)
Insert = O(lg n)
Delete max/min = O(lg n)
Change value = O(lg n)