median of a list of n numbers
can be found by sorting the listand picking the middle value if nis odd or calculating the mean of the two middle values if nis even
Hashing
- Data items are placed in a series of indexed slots in a linear structure called a hash table.
- The ratio of the number of occupied slots to the size of the table is known as the load factor.
- The mapping of an item to a slot index is performed by means of a hash function.
The folding method
Divide the digits of the item into equal size pieces (except possibly the last). Then, add the pieces together and take the remainder when the total is divided by the number of slots.
The mid-square method
Square the item. Then, extract the middle digit or middle two digits, depending on whether the number of digits of the squared item is odd or even.Finally, take the remainder when this number is dividedby the number of slots.
open addressing
if a collision occurs, the item is placed in another slot
Linear probing
searches sequentially for the next open slot
Quadratic probing
avoids clustering by adding successive square numbers to the index
chaining
each slot may contain a collection of items, all having the same hash value
Binary search trees
A binary tree (not necessarily complete), such that for every node p, all the keys within p’s left subtree are less than the key of p; and all the keys withinp’s right subtree are greater than the key of p.
Insert to BST
- If the tree is empty, replace it with a tree consisting of a single node with the new key.
- Otherwise, if the new key is less than the key of the root, then insert into the left subtree of the root, else insert into the right subtree of the root.
Delete from BST
- Find the node N to be deleted.
- If N has no children, remove it.
- If N has one child, replace N with the child.
- If N has two children, find N’s successor, M, in N’s right subtree. M is a leaf. Replace N’s content with M’s content and delete M.
AVL trees
A self-balancing binary search tree.
height of a tree
number of edges on the longest path from the tree’s root to a leaf, if the tree is non-empty, and −1 otherwise.
A balanced BST
a BST for which the difference in height between any node’s left and right subtree doesn’t exceed 1.
balance factor
calculated by subtracting the height of the node’s right subtree from the height of its left subtree
