1/28
Vocabulary flashcards covering core terminology about binary search trees, their operations, tree traversal, and Huffman coding with related greedy algorithms.
Name | Mastery | Learn | Test | Matching | Spaced |
---|
No study sessions yet.
Binary Tree
Hierarchical data structure that is either empty or contains a root and up to two subtrees (left and right).
Binary Search Tree (BST)
A binary tree in which left child < parent and right child > parent, with no duplicate values, enabling O(log n) search, insert, and delete operations in average cases.
Root
The top‐most node of a tree; the ancestor of all other nodes.
Subtree
A tree formed by a node and all of its descendants; can be left or right in a binary tree.
Path Length
The number of edges along a path between two nodes.
Node Depth
Length of the path from the root to the node (root depth = 0).
Level
All nodes that share the same depth in a tree.
Sibling Nodes
Nodes that share the same parent.
Left Child
The root of the left subtree of a node; holds a smaller value than its parent in a BST.
Right Child
The root of the right subtree of a node; holds a larger value than its parent in a BST.
Leaf (External Node)
A node with no children.
Tree Height
Length of the longest path from the root to any leaf; 0 for a single‐node tree, –1 for an empty tree.
Traversal
Systematic process of visiting every node in a tree exactly once.
Inorder Traversal
Visits nodes in the sequence left → root → right; yields ascending order in a BST.
Preorder Traversal
Visits nodes in the sequence root → left → right; useful for copying a tree.
Postorder Traversal
Visits nodes in the sequence left → right → root; useful for deleting/freeing nodes.
Depth-First Traversal
Traversal that explores as far along each branch as possible (preorder, inorder, postorder variations).
Breadth-First Traversal
Traversal that visits nodes level by level from the root downward (also called level-order).
BST Insertion
Operation that places a new key by traversing from the root to a leaf, linking it as a left child if smaller, right child if larger.
BST Deletion
Operation that removes a node while preserving BST properties; handled by cases based on the node’s children.
Deletion Case 1 (No Left Child)
If the node has no left child, link its parent directly to its right child.
Deletion Case 2 (Has Left Child)
If the node has a left child, replace its value with the rightmost node in its left subtree, then delete that rightmost node.
Rightmost Node
The node with the greatest key in a subtree (furthest right along right children).
MVC Architecture (for BST Visualization)
Software pattern where the Model stores tree data, the View renders the tree, and the Controller handles user interaction.
Huffman Coding
Compression technique that assigns shorter binary codes to more frequent characters by building a frequency-based binary (Huffman) tree.
Huffman Tree
Binary tree where characters are leaves and edge directions (left = 0, right = 1) define prefix-free codes used for compression.
Decoding (Huffman)
Process of reading bits from the root, moving left on 0 and right on 1 until a leaf is reached to retrieve each character.
ASCII Limitation
Standard fixed-length coding where every character uses 8 bits, regardless of frequency, leading to larger file sizes than Huffman coding.
Greedy Algorithm
Algorithmic approach that makes the locally optimal choice at each step, e.g., Huffman coding or U.S. coin change; may not always yield global optimum.