What are the features of an inorder traversal?
Outputs the data in ascending order
Describe an inorder traversal
Pointers below the nodes
- Traverses the left sub-tree
- Visits the root
- Traverses the right sub-tree
What are the features of a postorder traversal?
A 'bottom up' method
Used if data needs to be deleted from the tree
Describe a postorder traversal
Pointers to the right of the node
- Traverses left sub-tree
- Traverses right sub-tree
- Visits the root
What is a hash table?
An array structure with an associated hash function
What is the process of hashing?
When the data being stored (the key) is inserted into the hashing function and a hash value is output
The hash value relates to a specific location in the hash table
What are two applications of hashing?
Speeding up data retrieval
Checking validity of data
How would you search for a particular record in a hash table?
The record would be inserted into the hashing function, and then the output is the location in which you need to search
How is hashing used to check the validity of data?
If data is sent to a new location, the hash value is sent too
Once the data arrives, the hash function is carried out again, and if the new and old hash values don't match, then the data is invalid
What is the advantage of a hash table when locating a record in a file?
Using the hash function means there will be only one location outputted that needs to be searched
What are 3 features of a good hash algorithm?
- Generates a uniform spread of unique indexes to avoid collisions
- Produces hash values quickly, thus being fast
- Is complex, thus reducing the chance of collisions, with unique hash values
What is a collision in the context of hashing?
A collision occurs when the hash function produces the same hash value for different keys, thus giving the same memory location in the hash table to both keys
What are two methods of dealing with collisions in the context of hashing?
Open addressing (closed hashing): inserts a colliding key into the next available memory location, known as rehashing
Closed addressing (open hashing): apply a linked list to a memory location where a collision occurs. This is an overflow list, which holds all subsequent keys which collide with the data already stored in this location
What are some uses of hashing?
Searching a database: can quickly find data in a database
Sending files: used to validate the data sent
Storing passwords safely: hashes the user's password before storing it
Describe the structure of a graph
A graph is composed of multiple vertices, each connected to others by edges
Describe the difference between a directed and undirected graph
Directed graph: the edges have a direction, the way of travel
Undirected graph: no specific direction on an edge
Describe the difference between a weighted and unweighted graph
Weighted: has weights/costs marked on each edge
Unweighted: has no additional edge values
How can an adjacency matrix be used to store a graph?
How can a list be used to store a graph?
How can a dictionary be used to store a graph?
How can ordered pairs be used to store a graph?