CICS 210 Trees

Tree definition

"A non-sequential data structure made up of nodes connected by arcs and organized hierarchically without cycles."

Root

"The single distinct node from which all other nodes descend."

Parent

"Any node that has one or more child nodes."

Child

"A node that descends directly from another node (its parent)."

Sister

"Two nodes that share the same parent."

Ancestor

"A node that appears on the path from the root to another node."

Grandchild

"A node that is the child of another node’s child."

Internal node

"A node with at least one child."

External node (Leaf)

"A node with no children."

Path

"A sequence of nodes connected by arcs."

Branch

"A path connecting the root to a leaf."

Importance of trees

"Trees are widely used in computer science for file systems

Binary tree definition

"A tree in which each node has at most two children (left and right)."

Formal definition of binary tree

"B = ∅ (empty tree) or B = <O

Left child

"The root of the left subtree."

Right child

"The root of the right subtree."

Left arc / Right arc

"An arc connecting a node to its left or right child."

Degree of binary tree

"The maximum number of children a node can have (2)."

Volume of binary tree

"The total number of nodes in the tree: Vol(EmptyTree)=0; Vol(<O

Height of node

"The number of arcs from the node to the root (root has height 0)."

Height of tree (H(B))

"The maximum height among all nodes."

Width of tree (W(B))

"The maximum number of nodes at any level."

Traversal distances

"LC(B) = total traversal distance; LCI(B) = internal traversal distance; LCE(B) = external traversal distance."

Linear binary tree

"A binary tree where each node has at most one child."

Complete binary tree

"A binary tree where all levels are fully filled with 2^k nodes at level k; total nodes = 2^(h+1)-1."

Perfect binary tree

"A binary tree where all levels are filled except possibly the last

Full binary tree

"A binary tree where each internal node has either two or no children; left and right subtree heights differ by at most 1."

Skewed binary tree

"A binary tree dominated entirely by either left or right children (left-skewed or right-skewed)."

Theorem 1 relation between height and nodes

"For any BT of volume n and height H: ⌊log₂ n⌋ ≤ H ≤ n − 1."

Corollary on leaves and height

"For a BT with f leaves: H ≥ ⌈log₂ f⌉."

Traversal distance theorem

"The traversal distance satisfies n·log₂ n ≤ LC(B) ≤ n²."

Mean height of leaves

"The average height of leaves ≤ log₂(f)."

Pointer representation of a binary tree

"Each node stores its value and two pointers (left and right subtrees)."

Table/array representation of a binary tree

"Each row stores: node value

Tree traversal purpose

"To visit all nodes of the tree in a specific order for processing."

General traversal rule

"Go deep and turn left whenever possible."

Preorder traversal

"Order: Node → Left → Right."

Inorder traversal

"Order: Left → Node → Right."

Postorder traversal

"Order: Left → Right → Node."

Generalized tree definition

"A tree where each node can have multiple children."

Representation using pointer tables

"Each node has a table of pointers to its children; maximum number = degree of the GT."

Representation using linked lists

"Each node has two pointers: first child and next sibling. Efficient and flexible structure."

Modified linked list representation

"Last child points to parent; includes a field to indicate whether pointer leads to sibling or parent."

Binary search tree definition

"A binary tree where for every node V: all elements in the left subtree ≤ V’s element

Inorder property of BST

"Traversing a BST in inorder gives the elements in ascending order."

Multiple BSTs

"Multiple BSTs can represent the same dataset depending on insertion order."

BST search process

"Compare target x with current node value s. If x = s

Search algorithm complexity

"Depends on height of the tree; tail-recursive and can be implemented iteratively."

Insertion at leaves

"The new element is added as a leaf after searching for the correct position."

Insertion at root

"The tree is split into L (≤ x) and R (> x)

Split algorithm

"Recursively divides the BST into two subtrees L and R based on whether node values are ≤ or > x."

Add_root algorithm

"Creates a new node as root

Deletion case 1

"Node is a leaf → delete directly."

Deletion case 2

"Node has one child → replace node with its child."

Deletion case 3

"Node has two children → replace node with its predecessor (max in left subtree)."

Delete_max procedure

"Finds and deletes the largest node in a BST and returns its value."

Delete_node procedure

"Recursively searches for the node to delete and reorganizes the BST using delete_max if needed."

BST search complexity

"If element found at node v: ≈ 2·H(v) comparisons; if not found: ≈ 2·(H(v)+1) comparisons."

BST insertion complexity

"Same as search; proportional to tree height."

BST deletion complexity

"Also proportional to height."

BST time complexities

"Best case (balanced tree): O(log n); worst case (skewed tree): O(n)."

Applications of trees

"Trees are used in databases

Importance of tree structures

"Provide efficient hierarchical data organization and enable fast searching