Trees, Hierarchical Structures, Heaps, and Priority Queues

Vocabulary flashcards covering key terms and definitions for Binary Trees, Tree Traversals, Binary Search Trees, AVL Trees, Heaps, Heapify Operations, and Priority Queues.

Binary Tree

A hierarchical data structure where every node can have up to two (2) child nodes (commonly called the left child and right child) per parent.

Root Node

The topmost node of a tree structure.

Leaf Nodes

The end nodes in a tree structure that have no children, containing NULL pointers pointing to their left and right children.

Tree Traversal

The systematic process of visiting every node in a tree structure exactly once in a particular order to access or process data.

Breadth-First Traversal (BFT)

Also known as Level Order Traversal, a traversal method that visits nodes level by level from the root downwards, moving horizontally across each level before descending to the next using a queue.

Depth-First Traversal (DFT)

A tree traversal approach that proceeds by exploring as deeply as possible along each branch before backtracking.

Inorder Traversal

A depth-first traversal method where nodes are visited in the order: left subtree first, then the root node, and finally the right subtree ($\text{L-Root-R}$).

Preorder Traversal

A depth-first traversal method where nodes are visited in the order: root node first, followed by the left subtree, and then the right subtree ($\text{Root-L-R}$).

Postorder Traversal

A depth-first traversal method where nodes are visited in the order: left subtree first, then the right subtree, and finally the root node ($\text{L-R-Root}$).

Binary Search Tree (BST)

Also called an Ordered Binary Tree, a node-based structure where a node's left subtree contains only keys less than the node's key, the right subtree contains only keys greater, and duplicate nodes are not allowed.

AVL Tree

An Adelson-Velskii Landis tree; a self-balancing binary search tree (BST) in which each node maintains an extra balance factor value of $-1$, $0$, or $+1$.

Balance Factor

In an AVL tree, the value calculated as the difference between the height of the left subtree and the height of the right subtree: $\text{Balance Factor} = \text{Height(Left Subtree)} - \text{Height(Right Subtree)}$.

Left-Left (LL) Rotation

A single right rotation performed on an AVL tree when insertion occurs in the left subtree of a left child, resolving a left-heavy balance factor of $+2$.

Right-Right (RR) Rotation

A single left rotation performed on an AVL tree when insertion occurs in the right subtree of a right child, resolving a right-heavy balance factor of $-2$.

Left-Right (LR) Rotation

A double rotation (left rotation on the left child, followed by right rotation on the root) applied in an AVL tree when insertion occurs in the right subtree of a left child.

Right-Left (RL) Rotation

A double rotation (right rotation on the right child, followed by left rotation on the root) applied in an AVL tree when insertion occurs in the left subtree of a right child.

Abstract Syntax Trees (ASTs)

Tree structures relied upon by compilers to represent the syntactic structure of programming languages to parse and analyze code efficiently.

Merkle Trees

Tree structures used in cryptography and blockchain technologies, such as Bitcoin and Ethereum, to facilitate fast and secure verification of transactions.

Heap

A binary tree data structure in which every node is larger (or smaller) than the values associated with either child, placing the largest or smallest value at the root.

Complete Binary Tree (Shape Property)

A structural property of a heap where all levels are completely filled except possibly the last, which is filled from left to right without skipping nodes.

Max-Heap

A heap structure where the parent node is always greater than or equal to its children, ensuring that the largest value is stored at the root.

Min-Heap

A heap structure where the parent node is always less than or equal to its children, ensuring that the smallest value is stored at the root.

Heapsort

A comparison-based sorting algorithm that uses a binary max-heap to sort an array in ascending order by repeatedly extracting the maximum element and placing it at the end.

Top-K Tracking

The process of efficiently maintaining the $K$ largest or $K$ smallest elements from a continuous stream or large dataset without sorting the entire input.

Dijkstra's Algorithm

An algorithm used in GPS routing, network protocols, and game AI pathfinding that utilizes a min-heap to extract the next closest vertex with the smallest tentative distance.

Heapify

The process of converting an arbitrary array with no specific structure into a valid heap that maintains the heap order property from a given node down to its descendants.

Up-Heapify (Bubble-Up)

A heap operation used after inserting a new element at the bottom to restore the heap property by moving the element up the tree toward the root.

Down-Heapify (Bubble-Down)

A heap operation used after removing or deleting the root element to restore the heap property by moving the replacement root element down the tree.

Priority Queue

An abstract data type operating like a queue where each element has an associated priority level, and elements are dequeued based on priority rather than arrival order.