Flashcards
DSA - Lecture 4a
Flashcards do conjunto (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
Informações
- Descrição
- FlashCards sobre DSA - Lecture 4a, criado por Lucas Vanparijs em 20-03-2015.
- Criado por
- Lucas Vanparijs
- Visualizações
- 0
- Avaliação