3013-Algorithms Test 2 - Avl, Tree Traversals, Hashing Solution

Avl Trees
Here is a pdf on rotations: Tree Rotations
Be able to insert a list of values into an AVL tree applying single and double rotations when appropriate so that you resulting tree is correct. Ensure you label the balance factors for each tree node.
Try to show work when you can.
Be able to describe the differences between a BST and AVL tree. Know the differences in implementation and performance (costs for insertion, searching, and deletion). Do we implement one or both using arrays or pointers?
Tree Traversals
Perform the following traversals on a binary tree:
PreOrder traversal
InOrder traversal
PostOrder traversal LevelOrder traversal.
Hashing
When to choose which type of collision resolution:
Read this: https://stackoverflow.com/questions/2556142/chained-hash-tables-vs-open-addressed-hash-tables
Read this: https://www.geeksforgeeks.org/hashing-set-3-openaddressing/#:~:text=Open%20addressing%20requires%20extra%20care,number%20of%20keys%20is%20known. General Hashing Questions
Does the data being hashed have an impact on the hash function being chosen?
What is the load factor, and give a general overview of how certain load factors are chosen.
Table size is important when implementing a hash table. Explain how we should choose a certain table size and why.
Explain what Collision resolution is, the two major categories, and the three major open addressing types we discussed in class. What does the term avalanche mean when discussing hash functions?
https://simple.wikipedia.org/wiki/Avalanche_effect How does a hash table allow for O(1) searching?
What is the worst case efficiency of a look up in a hash table using: chaining and open addressing?
The bigger the ratio between the size of the hash table and the number of data elements, the less chance there is for collision. What is a drawback to making the hash table big enough so the chances of a collision are extremely small? How long would a deletion operation take from hash table implemented using separate chaining?
Given the input {4371, 1323, 6173, 4199, 4344, 9679, 1989}, a fixed table size of 10, and a hash function H(X) = X mod 10, show the resulting

Ascii Values:
Here are some quick lookup tables to help with your hashing application question:

Application Hashing
Epd, DcS, Fcf, Gco, Qzj, Wvc, RUC, ejJ, iwR, zyz

Binary Search Tree Deletion
(NOT THIS TEST BUT WANTED TO LEAVE IT ON THE STUDY GUIDE)
Delete the root from the following binary search tree:


Think about this: There is a general property in a BST where the in-order successor of a node whose right child is always null. Where might this be?

Algorithm to find in-order successor and predecessor
```txt Input: root node, key output: predecessor node, successor node
1. If root is NULL then return
2. if key is found then a. If its left subtree is not null Then predecessor will be the right most child of left subtree or left child itself. b. If its right subtree is not null The successor will be the left most child of right subtree or right child itself. return
3. If key is smaller then root node set the successor as root search recursively into left subtree else set the predecessor as root search recursively into right subtree ```

Suppose deleteMe is the root node in a BST with both a left child and a right child. Will the in-order successor of deleteMe, always have a null left child?
1. Yes, always
2. No, only sometimes
3. No, never
Could you please create a test question that tests a students knowledge on binary search tree deletion. There are three major cases when deleting a node: 0 children, 1 child, and 2 children. Please show a student three separate binary search trees, prompting the student to delete a node from each tree, where each of the above major cases are covered.