(6) Hash Tables and Trees Flashcards
Definition Hash Table
A hash table is composed of a key and a bucket of unfixed size for elements:
- realised as list with the key and lists
- every element in a bucket is associated with the respective key
- the hash function determines the mapping key
What are advantages of hash tables?
- Adding elements is efficient O(1): Compute hash value and add element to the corresponding bucket
- Retrieving elements is easy (O(n) worst case): Compute has value, find corresponding key and look into the bucket
Why is it important to choose a good hash function and how does it look like?
- a good hash function should distribute the data evenly among the buckets
- clusters increase the worst case search time
What is the basic concept of trees?
- order data in a hierarchical manner
- elements can be easily inserted at the end (leafs) (more effort to insert anywhere)
- Elements can be removed
- Searching is efficient
Definition Node
Any element of the tree
Definition Root
Topmost node of the tree
Definition Parent
Node that has one or more children
Definition Child
Node that has a connected node above it
Definition Leaf
Node that does not have any children
Definition Subtree
Parent and all the node below it
What is a binary search tree?
- Tree in which every parent node has at most two children
- Every node holds a value and a total order is defined
- The left child value (and all values in the left subtree) are always smaller than the right child value
What is a balanced tree?
One part of the tree has a height that is at most 1 larger than the height of the other part of the tree.
What is the advantage of a binary search tree?
Allows to look up elements efficiently
What is the height of a tree?
The length of the longest path starting from the root and ending at a leaf (count edges)
How fast is searching a binary tree?
Balanced Tree: O(log n) given height h
Unbalanced Tree: O(n)
