Searching and Tables Flashcards
What are common names for data structures that allow for efficient searching?
- Associative array
- Map
- Dictionary
What are data structures in the table ADT?
- Associative array
- Dictionary
- Map
What are basic operations of table ADTs?
- construct (initialize) a table
- search and retrieve for an entry
- update record (doesn’t change key)
- insert and delete (dynamic operations)
- enumerate all (usually unsorted)
Binary search example
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/825/384/a_image_thumb.png?1466283643)
Basic table ADT operations and worst case running times on a table of n elements are:
- Construct (initialize) a table; requires sorting Θ(n lg n)
- Search and retrieve an entry; binary search Θ(lg n)
- Update record (doesn’t change key); binary search Θ(lg n)
- Insert and delete (dynamic operations); shift array Θ(n)
- Enumerate all (here it will be sorted); scan array Θ(n)
we can improve running of number 4 to O(lg n) by using a different data structure i.e. binary tree or hash table
What is a BST?
A binary search tree (BST) is a binary tree that satisfies the following ordering relation: for every node ν in the tree, the values of all the keys in the left subtree are smaller than (or equal, if duplicates allowed) to the key in ν and the values of all the keys in the right subtree are greater than the key in ν.
Left subtree has smaller valued nodes then right subtree
Searching and Inserting example
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/825/456/a_image_thumb.png?1466284033)
Illustrating Removal of Nodes in a BST
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/825/724/a_image_thumb.jpg?1466284431)
The search, retrieval, update, insert and remove operations in a BST all take what time?
O(h) in the worst case, where h is the height of the tree
The search, retrieval, update, insert and remove operations in a well-balanced BST
Θ(lg n)
dynamic operations of insertion and deletions may destroy balance, degrading performance to Ω(n)
What technique is used to make sure worst case does not occur in BST?
balancing
Left and right rotation of BST
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/825/963/a_image_thumb.png?1466284696)
What is an AVL tree?
An AVL tree is a binary search tree with the additional balance property that the tree is balanced
What is the height of an AVL tree with n nodes?
Θ(log n)
(AVL trees are more rigidly balanced than red-black trees so good for applications with more prominent search-only operations)
What is a red-black tree?
A red-black tree is a binary search tree such that every node is colored either red or black and every non-leaf node has two children. In addition, it satisfies the following properties:
- the root is black;
- all children of a red node must be black;
- every path from the root node to a leaf must contain the same number of black nodes.