Flashcards
DSA - Lecture 4a
Cards in this deck (10)
- 1What is a dictionary ADT like?It's a searchable collection of key-element items
- 2What are its main operations(Dictionary ADT)Searching, inserting and deleting
- 3What kind of order do the keys have?Total Order
- 4What ADTs does a lookup table consist of?it is an ordered dictionary implemented with a sorted sequence. it stores the items of the dictionary in an array based sequence, sorted by key and uses an external comparator for the keys.
- 5What is the Lookup tables performace for finding an element, inserting and removing.O(log n ) for finding if implemented with a binary tree, and O(n) for inserting and removing due to shifting elements
- 6How can you store the keys in a Lookup table?By using a BST, the keys are stored at internal nodes
- 7How can you visit the keys in increasing order in a BST?By using inorder traversal
- 8Explain the searching in a BST for a key k + Pseudocodeoke
- 9Explain and draw deletion in a BSTkk
- 10What is an AVL tree?It is a balanced BST such that the heights of internal nodes can differ with at most 1
Information
- Description
- Flashcards on DSA - Lecture 4a, created by Lucas Vanparijs on 20/03/2015.
- Created by
- Lucas Vanparijs
- Views
- 0
- Rating