Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
20 Cards in this Set
- Front
- Back
|
A node's value is less than or equal to that of its children
|
Heap order property
|
|
|
Average time of add() for a SortedArray
|
O(n)
|
|
|
Worst-case search time for a binary search tree
|
O(n)
|
|
|
This tree is efficiently stored in an array.
|
Heap
|
|
|
Traversal that produces elements of an AVL tree in sorted order.
|
In-order traversal.
|
|
|
Average case to add for an unsorted dynArray
|
O(1)
|
|
|
Average case to remove from an AVL tree
|
O(log n)
|
|
|
Pre-order traversal
|
Node, left children, right children
|
|
|
In-order traversal
|
Left children, node, right children
|
|
|
Post-order traversal
|
Left children, right children, node
|
|
|
AVL Tree Balance Factor =
|
height(left subtree) - height(right subtree)
|
|
|
Sub-trees of each node in an AVL tree can differ by at most __ in their height.
|
1
|
|
|
The maximum path length from a node to a leaf node.
|
Node height
|
|
|
Data structure used to implement a knowledgebase as in the "guess the animal game"
|
Binary tree (not a binary search tree, order doesn't matter).
|
|
|
A tree traversal that produces a reverse Polish notation expression for an expression tree.
|
Post-order
|
|
|
Term that describes the path length from the root to a given node.
|
Node depth
|
|
|
ADT used when implementing an in-order tree traversal iterator.
|
Stack
|
|
|
What is a heap?
|
A binary tree organized as a priority queue.
|
|
|
Which node fills the spot in a heap when you removeMin()?
|
The last node fills the spot and percolates down.
|
|
|
An adjacency matrix of a graph with V vertices requires ____ space.
|
O(V^2)
|
