Hoofdstuk 3 Flashcards
Verschil dictionary en container
Dictionary supports add, find, delete when given a key to locate the value
Container simply stores information.
Some datastructures can be used as both dictionary and container. e.g. array.
Eigenschappen array?
Continu datastructuur. Het hele geheugen kan gezien worden als een grote array met de geheugen adressen als index.
Elementen opvragen in O(1) als de index geweten is.
Grootte is fixed en vooraf bepaald.
Eigenschappen Dynamic Array (ArrayList) ?
Array die zichzelf vergroot als hij vol is. elementen toevoegen duurt O(1) maar als hij volloopt moet hij zichzelf volledig kopiëren in O(n).
als je amortized efficiency berekent voor deze operatie komen we nog steeds uit op O(1).
De grootte wordt altijd verdubbeld.
Wat is amortized analysis
Consider the cost of a sequence of operations, not indiviual cost of a particular operation
e.g stating that the arraylist has a time complexity of O(n) is true but very pessimistic.
Amortized efficiency calculates an average cost over a series of operations.
Aggregrate method, bankers method
Eigenschappen Linked list
Retrieving first elem is fast O(1), but for other elements you have to follow the chain, O(n)
Easy to insert or delete nodes, O(1) after they are found,
Overhead for pointers in each node.
Eigenschappen stack
Last in first out structuur (LIFO)
Push (add to top of stack): O(1)
Pop (retrieve and remove top of stack): O(1)
Easy to implement with array or linked list
Eigenschappen tree
Recursively defined. Every node is the root of a subtree
Degree (graad): Amount of children
Depth (diepte): Amount of edges(takken) from the root of the node
Height (hoogte): Maximum distance (edges) from root of the node to the leaf(bladeren).
Leaf (blad) is een node without children.
Eigenschappen Queue
First in first out (FIFO) structuur
Enqueue: (Add) O(1)
Dequeue: (Remove) O(1)
easy to implement with array or linked list
Array implementation needs two pointers and a circular array is used
Eigenschappen Dequeue
Double ended queue.Can be used as a stack and a queue.
Add/remove supported on front and back. Both O(1)
Multiway (m-way) tree
Elke node kan 0 tot k kinderen hebben.
Stores a list of pointers to children
Wordt vaak gebruikt om efficient te zoeken door databases
How are trees stored
Trees with a variable amount of children has to use pointers (linked)
Missing children -> null pointer
Threaded trees store pointers to predecessors to speed up traversal
Tree’s with a fixed structure (e.g. heap) can be stored in a continuous way (in an array). Children of nodes are found in a specific offset from the parent node.
If average number of children is low, using a tree might be a waste of space. A simple linked list might be a better data structure.
What is tree traversal?
Iterate over a tree in a certain way.
Possible methods:
- Depth first (Helemaal naar beneden eerst)
- Breadth first (Eerst alle siblings dan naar beneden)
- Best first (Some nodes have priority over others)
How does depth first search work?
Explore the search as deep as possible.
4 ways:
- pre-order: root,left,right
- in-order: left, root, right
- reverse-in-order: right,root,left
- post-order: left,right,root
easy to implement in a recursive way
How does breadth first search work
Process each level from left to right before moving down
Does not use the recursive definition of the tree -> adds all children of a level to a queue.
Used for crawlers in search engines.
Eigenschappen graph
Collection of n nodes (=vertices) with m connections
Nodes are numbered, defined by end nodes.
The degree (graad) of a node is the amount of edges it has, in a undirected graph
In a directed graph, indegree and outdegree can be distinguished
An edge can have properties, ( like a name, cost, time, etc..) if the properties are numbers which can be compared they are called weights. We would call this a weighted graph.
