Data Structures: Tree Fundamentals and Binary Trees

This set of vocabulary flashcards covers fundamental tree concepts, terminalogy, binary tree variations (strictly, complete, extended), traversals, and specialized structures like BST, B-trees, B+ trees, and AVL trees based on the lecture notes.

Tree

A non-linear data structure in which items are arranged in a sorted sequence to represent hierarchical relationships existing amongst several data items.

Root

The specially designed first data item in the hierarchical arrangement of a tree. In a tree, every node except this one has exactly one parent.

Node

The basic structure in a tree that specifies the data information and links (branches) to other data items.

Degree of a node

The number of subtrees belonging to a specific node in a given tree.

Degree of a tree

The maximum degree of any node within a given tree.

Terminal node(s)

Also called a leaf, this is a node with a degree of zero.

Non-terminal node(s)

Any node, except the root node, whose degree is not zero; these serve as intermediate nodes when traversing from the root to the leaves.

Siblings

The children nodes of a given parent node, also referred to as brothers.

Level

A measurement of tree hierarchy where the root is at level $0$, and if a node is at level $n$, its children are at level $n + 1$.

Edge

A connecting line drawn from one node to another node in a tree.

Path

A sequence of consecutive edges from a source node to a destination node.

Depth

Also known as height, it is the maximum level of any node in a given tree.

Forest

A set of disjoint trees; removing the root node from a tree results in this structure.

Binary tree

A finite set of elements partitioned into three distinct sub-sets: the root, the left sub-tree, and the right sub-tree.

Ancestor

A node A is considered this for node B if A is either the father of B or the father of some other ancestor of B.

Climbing

The operation of traversing a tree from a leaf node up to the root node.

Descending

The operation of traversing a tree from the root node down to the leaves.

Strictly binary tree

A binary tree in which every non-leaf node has non-empty left and right sub-trees.

Complete binary tree

A strictly binary tree in which all leaf nodes are located at the same level.

Extended Binary tree

Also known as a 2-tree, it is formed by adding nodes to a binary tree such that every node in the resultant structure has either $0$ or $2$ children.

Internal nodes

The nodes of the original tree when it is converted into an extended binary tree.

External nodes

The new nodes added to a binary tree to make it an extended binary tree.

Pre-order Traversal

A traversal method using the sequence: (1) Visit the root R, (2) Traverse the left sub-tree in pre-order, (3) Traverse the right sub-tree in pre-order.

In-order Traversal

A traversal method using the sequence: (1) Traverse the left sub-tree in in-order, (2) Visit the root R, (3) Traverse the right sub-tree in in-order.

Post-order Traversal

A traversal method using the sequence: (1) Traverse the left sub-tree in post-order, (2) Traverse the right sub-tree in post-order, (3) Visit the root R.

Binary search tree

A binary tree where all elements in the left sub-tree of a node are less than the node's contents, and all elements in the right sub-tree are greater than or equal to it.

B-tree

A balanced N-way search tree where all leaf nodes appear on the same level and non-leaf nodes (except root) have at least $n/2$ children; used in external sorting.

B+ tree

A variation of the B-tree used for indexed sequential organization where all leaves are connected to form a linked list of keys in sequential order.

AVL tree

A balanced binary search tree invented in 1962 by Adelson-Velskii and Landis where the difference between left and right sub-tree heights is at most one.

Balance factor

In an AVL tree node, this is calculated by subtracting the height of the right sub-tree from the height of the left sub-tree.

Threaded Binary Tree

A tree structure where NULL pointers are replaced with pointers to in-order predecessors or successors to facilitate traversal without using a stack.

Right threads

Pointers in a threaded binary tree that point to the in-order successor of a node, replacing normal NULL right pointers.