writeInsertRoot.C File Reference

Demonstrates root insertion in BST. More...

#include <ctime>
#include <iostream>
#include <fstream>
#include <tclap/CmdLine.h>
#include <aleph.H>
#include <tpl_binNode.H>
#include <tpl_binNodeUtils.H>

Include dependency graph for writeInsertRoot.C:

Go to the source code of this file.

Functions
static void	printNode (BinNode< int > *node, int, int)
int	main (int argc, char *argv[])

Variables
ofstream	output

Detailed Description

Demonstrates root insertion in BST.

This program demonstrates root insertion, an alternative insertion strategy for binary search trees. Unlike standard insertion (which places new elements at leaves), root insertion always places new elements at the root using rotations. This creates a self-adjusting tree structure that adapts to insertion patterns.

Standard vs Root Insertion

Standard Insertion

• Traversal: From root to leaf
• Insertion: New node becomes leaf
• Time: O(log n) average, O(n) worst case
• Result: New element at bottom of tree
• Structure: Tree grows downward

Root Insertion

• Traversal: From root to insertion point
• Insertion: New node inserted at correct position
• Rotation: Rotate path to bring new element to root
• Time: O(log n) average, O(n) worst case
• Result: New element always at root
• Structure: Tree adjusts upward

Algorithm

Root Insertion Process

Root insertion works by:

root_insert(tree, value):
  1. Search: Find insertion point (as in standard insertion)
  2. Insert: Create new node at that position
  3. Rotate up: Perform rotations along path to move new node to root
     - While new node is not root:
       - If new node is left child: rotate right
       - If new node is right child: rotate left

Rotations

The rotations maintain the BST property while moving the node upward:

• Right rotation: Moves left child up
• Left rotation: Moves right child up
• BST property: Maintained throughout

Properties

Advantages

✅ Temporal locality: Recently inserted elements near root ✅ Cache friendly: Frequently accessed elements at top ✅ Self-adjusting: Tree adapts to insertion patterns ✅ Fast access: Recent elements accessed quickly ✅ Splay-like: Similar to splay tree behavior

Disadvantages

❌ No balance guarantee: Tree may become unbalanced ❌ More rotations: Extra overhead compared to standard insertion ❌ Worst case: Still O(n) height possible ❌ Overhead: Rotations add computational cost

Applications

Caching

• LRU cache: Keep recently used items accessible
• Temporal locality: Exploit access patterns
• Performance: Fast access to recent items

Self-Adjusting Structures

• Adapt to patterns: Tree adapts to insertion order
• Dynamic optimization: Optimize based on usage
• Learning: Tree "learns" from insertions

Educational

• Tree rotations: Demonstrate rotation operations
• BST variants: Show alternative insertion strategies
• Algorithm design: Understand self-adjusting structures

Foundation for Splay Trees

• Similar concept: Splay trees extend root insertion
• Access patterns: Both optimize for temporal locality
• Implementation: Root insertion is simpler version

Comparison with Splay Trees

Aspect	Root Insertion	Splay Trees
When rotates	On insertion	On access
Rotates	New nodes only	Any accessed node
Complexity	O(log n) avg	O(log n) amortized
Balance	No guarantee	No guarantee
Use case	Insert-heavy	Access-heavy

Key Difference

• Splay trees: Rotate accessed nodes to root (not just inserted)
• Root insertion: Only rotates newly inserted nodes
• Both: Provide temporal locality benefits

Tree Structure Comparison

Standard Insertion

Insert sequence: 5, 3, 7, 1, 9
Result:
      5
     / \
    3   7
   /     \
  1       9

Root Insertion

Insert sequence: 5, 3, 7, 1, 9
Result (after each insertion):
  5 → 3 → 3 → 1 → 1
      5   7   3   3
          5   7   7
              5   5
                  9

Recent insertions cluster near root!

Output Files

• **insert_root-aux.Tree**: Tree structure in preorder format
  • Shows tree after root insertion
  • Can be visualized with btreepic

The visualization shows how recently inserted elements cluster near the root, creating a different structure than standard BST insertion.

Usage

# Generate tree with root insertion (20 nodes)
writeInsertRoot -n 20
 
# Use specific seed for reproducibility
writeInsertRoot -n 30 -s 42
 
# Compare with standard insertion
write_tree -n 20  # Standard insertion
writeInsertRoot -n 20  # Root insertion

Performance Characteristics

Operation	Standard Insertion	Root Insertion
Insert	O(log n)	O(log n) + rotations
Search (recent)	O(log n)	O(1) to O(log n)
Search (old)	O(log n)	O(log n) to O(n)
Balance	No	No

See also

tpl_binNodeUtils.H BST utility functions including root insertion

tpl_splay_tree.H Splay tree (related self-adjusting structure)

write_tree.C Standard insertion (for comparison)

btreepic.C Visualization tool

Author

Leandro Rabindranath León

Definition in file writeInsertRoot.C.

Function Documentation

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 222 of file writeInsertRoot.C.

References Aleph::check_bst(), Aleph::computeHeightRec(), Aleph::destroyRec(), Aleph::insert_root(), KEY, Aleph::maps(), output, Aleph::preOrderRec(), printNode(), and root().

printNode()

static void printNode ( BinNode< int > *  node, int  , int    )

static

Definition at line 217 of file writeInsertRoot.C.

References Aleph::BinNode< Key >::get_key(), and output.

Referenced by main().

Variable Documentation

output

ofstream output

Definition at line 215 of file writeInsertRoot.C.

Referenced by main(), and printNode().