Binary Search Trees, Heaps, and Priority Queues Study Guide

Vocabulary practice flashcards covering binary search tree operations, tree traversals, priority queues, binary heap properties, and heap restructuring algorithms.

Binary Search Tree (BST)

A binary tree that follows the rule that values smaller than a node go to its left subtree, and values larger than a node go to its right subtree.

BST Single-Child Deletion

A binary search tree deletion rule stating that when deleting a node with one child, its parent is connected directly to that child.

BST Leaf Node Deletion

A binary search tree deletion rule stating that when deleting a leaf node (a node with no children), it is simply removed from the tree.

Preorder Traversal

A depth-first traversal method that visits nodes in the order $\text{Root} \rightarrow \text{Left} \rightarrow \text{Right}$, meaning the root comes first.

Inorder Traversal

A depth-first traversal method that visits nodes in the order $\text{Left} \rightarrow \text{Root} \rightarrow \text{Right}$, meaning the root comes in the middle; in a binary search tree, it visits values in ascending order.

Postorder Traversal

A depth-first traversal method that visits nodes in the order $\text{Left} \rightarrow \text{Right} \rightarrow \text{Root}$, meaning the root comes last.

findMin()

A binary search tree operation that finds the smallest value in the tree, which is always located at the leftmost node.

findMax()

A binary search tree operation that finds the largest value in the tree, which is always located at the rightmost node.

BST Operation Time Complexity

The typical runtime complexity for search, insertion, and deletion operations in a binary search tree, which is $O(\log(n))$ in a reasonably balanced tree, but $O(n)$ in a severely unbalanced tree.

Priority Queue

A data structure in which each element has a priority, and elements are removed according to their priority rather than simply their insertion order.

Max-Priority Queue

A priority queue implementation where the element with the highest priority is removed first.

Min-Priority Queue

A priority queue implementation where the element with the lowest priority is removed first.

Regular Queue

A standard FIFO (first in, first out) data structure where the first element inserted is always the first element removed.

Priority Queue Applications

Computer applications including operating systems (process and task scheduling), networking (prioritizing packets), graph algorithms (finding shortest paths using Dijkstra's algorithm), event simulation (processing events by scheduled time), and emergency systems.

Heap

A specialized binary tree that satisfies two conditions: the shape property and the heap-order property; it is not necessarily a binary search tree.

Shape Property

A heap requirement specifying that the binary tree must be a complete binary tree, where every level is full except possibly the last, which fills strictly from left to right.

Heap-Order Property

The structural ordering rule stating that in a max-heap every parent is greater than or equal to its children, while in a min-heap every parent is less than or equal to its children.

Full Binary Tree

A binary tree that requires every node to have either zero or two children.

Leaf

A tree node that has no children; being inserted first in a data structure does not make a node a leaf.

Reheap-Up

Also called sift-up or bubble-up; the enqueue process in a heap where a new element is inserted at the next available bottom position and swapped upward with its parent until the heap property is satisfied or it reaches the root.

Reheap-Down

Also called sift-down or bubble-down; the dequeue process in a heap where the root is removed, the last element is moved to the root position, and it is swapped downward with its larger child until the heap property is restored.

Level-Order Heap Indexing

The sequential left-to-right, level-by-level arrangement of nodes in a complete binary heap, where the first element of a new level becomes the left child of the first node on the level directly above it.