Data Structures, unit: Trees and Binary Search Trees. Core concepts, terminology, and worked-example cues a college student meets for this unit, building on prior units without repeating them. Front: a term, concept, or short problem cue. Back: the definition, explanation, or answer.
38 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a tree, as a data structure?
Show answer
A hierarchical structure of nodes connected by edges, with one root and no cycles- What is the root of a tree?
Show answer
The topmost node, with no parent- What is a leaf node?
Show answer
A node with no children- What is the height of a tree?
Show answer
The length of the longest path from the root to a leaf- What is a binary tree?
Show answer
A tree where each node has at most two children- What is a binary search tree (BST)?
Show answer
A binary tree where each node's left subtree contains smaller values and right subtree contains larger values- What is the time complexity of searching a balanced binary search tree?
Show answer
O(log n)- What is the time complexity of searching an unbalanced (degenerate) binary search tree?
Show answer
O(n) in the worst case- What is tree traversal?
Show answer
Visiting all nodes of a tree in a systematic order- What is inorder traversal?
Show answer
Visiting left subtree, then the node, then right subtree- What is preorder traversal?
Show answer
Visiting the node first, then left subtree, then right subtree- What is postorder traversal?
Show answer
Visiting left subtree, then right subtree, then the node last- What does an inorder traversal of a binary search tree produce?
Show answer
The values in sorted order- What is a balanced binary tree?
Show answer
A tree where the height difference between left and right subtrees is minimized at every node- What is an AVL tree?
Show answer
A self-balancing binary search tree that maintains balance after every insertion or deletion
FlashKeepers