u4 Flashcards Preview

m269 > u4 > Flashcards

Flashcards in u4 Deck (15)
Loading flashcards...

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



•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



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