Introduction to Trees and Data Structures

A set of vocabulary flashcards based on the concepts of trees and data structures as discussed in the lecture.

Tree

A non-linear hierarchical data structure composed of nodes connected by edges.

Root

The distinguished topmost node of a tree that has no parent.

Leaf Node

A node with no children.

Internal Node

Any non-leaf node that has at least one child.

Edge

The connection between two nodes in a tree.

Path

A sequence of nodes connected by edges.

Height of a Node

The number of edges in the longest downward path from the node to a leaf.

Binary Search Tree (BST)

A binary tree where left subtree values are less than the root value and right subtree values are greater.

AVL Tree

A self-balancing binary search tree with a balance factor of -1, 0, or +1.

B-Tree

A self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.

Heap Tree

A complete binary tree that satisfies the heap property, where parent nodes are either greater than or less than their child nodes.

Traversal

The process of visiting each node in a tree exactly once in a defined order.

Depth-First Traversal

A traversal method where nodes are explored as far as possible along each branch before backtracking.

Breadth-First Traversal

A traversal method that visits nodes level by level.

General Tree

A tree with no restrictions on the number of children a node can have.

Full Binary Tree

A binary tree where each node has either 0 or 2 children.

Skewed Binary Tree

A binary tree where nodes have only one child, leading to a structure resembling a linked list.

Balance Factor

The difference in height between the left and right subtrees of a node in an AVL tree.

Dynamic Memory Allocation

Allocating memory dynamically as needed, which is an advantage of linked representation of trees.

Time Complexity

An estimate of the amount of time an algorithm takes to complete based on the size of the input.

Space Complexity

An estimate of the amount of memory space required by an algorithm as a function of the input size.