Demonstrates BST balancing operation (recursive median selection with rotations) More...

#include <iostream>
#include <fstream>
#include <tclap/CmdLine.h>
#include <aleph.H>
#include <tpl_dynArray.H>
#include <tpl_balanceXt.H>

Include dependency graph for writeBalance.C:

Typedefs
typedef BinNodeXt< int >	Node

Functions
void	print_keyb (Node *p, int, int)

void	print_keya (Node *p, int, int)

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

Variables
ofstream	outputb

ofstream	outputa

Detailed Description

Demonstrates BST balancing operation (recursive median selection with rotations)

This program demonstrates balance_tree() from tpl_balanceXt.H, which rebalances a BST by repeatedly selecting the median (by inorder position) and rotating it up to become the root, then recursing on the left and right subtrees.

It generates visualization files showing the transformation from an unbalanced BST to a size-balanced tree.

Why Balance Trees?

The Problem with Unbalanced Trees

Unbalanced trees degrade to linked lists in worst case:

Worst case: O(n) search time instead of O(log n)
Performance: Degrades significantly
Cache: Poor cache locality

Benefits of Balancing

Balancing ensures:

Optimal performance: O(log n) search, insert, delete operations
Predictable: Consistent performance characteristics
Cache friendly: Better memory access patterns
Height: Minimum possible height

Algorithm Overview

The algorithm used in this example is:

Select the node at inorder position n/2.
Rotate it up until it becomes the root.
Recurse on left and right subtrees.

In Aleph-w this is implemented by select_gotoup_root() + balance_tree().

Total Complexity

Time: O(n log n)
Space: O(1) - constant extra space (in-place)
Rotations: O(n log n) in the worst case

Perfect Balance

Definition

The routine used here produces a size-balanced tree:

For each node, the difference between the cardinalities of its left and right subtrees is at most 1.
This yields a height that is O(log n) (so searches become logarithmic), but it does not require building a complete/perfect tree level-by-level.

Example

Unbalanced (height 4):    Balanced (height 3):
      1                         4
       \                       / \
        2                     2   6
         \                   / \ / \
          3                 1 3 5 7
           \
            4

Comparison with Other Balancing Methods

Method	Time	Space	Result	Notes
Median-rotations (`balance_tree`)	O(n log n)	O(1)	Size-balanced	Implemented by `tpl_balanceXt.H`
AVL	O(n log n)	O(log n)	Height-balanced	Maintains during ops
Red-Black	O(n log n)	O(log n)	Relaxed balance	Maintains during ops
Rebuild	O(n)	O(n)	Perfect	Requires extra memory

Applications

Tree Optimization

Improve performance: Optimize existing BSTs
One-time operation: Balance tree before heavy queries
Legacy code: Improve performance without rewriting

Educational

Visualize balancing: See tree transformation
Learn algorithms: Understand balancing techniques
Algorithm study: Compare balancing methods

Data Structure Conversion

Prepare trees: Optimize trees for operations
Format conversion: Convert between tree formats
Preprocessing: Prepare data for algorithms

Performance Tuning

Query optimization: Optimize trees before queries
Batch processing: Balance after bulk insertions
Maintenance: Periodic tree optimization

Output Files

**balance-before-aux.Tree**: Original unbalanced tree (preorder)
- Shows tree before balancing
- May have high height
**balance-after-aux.Tree**: Perfectly balanced tree (preorder)
- Shows tree after DSW algorithm
- Minimum height achieved

Both files can be visualized with btreepic tool to see the transformation.

Usage

# Generate balanced tree with 50 nodes
writeBalance -n 50
 
# Use specific seed for reproducibility
writeBalance -n 100 -s 12345
 
# Generate larger tree
writeBalance -n 200

Algorithm Properties

Advantages

Efficient: O(n) time complexity
In-place: O(1) extra space
Simple: Easy to understand and implement
Perfect balance: Achieves optimal height

Limitations

One-time: Doesn't maintain balance during operations
Rotations: Many rotations may be performed
Not incremental: Must rebuild entire tree

See also: tpl_balanceXt.H DSW balancing implementation; btreepic.C Visualization tool; timeAllTree.C Tree performance comparison (includes balanced trees)

Author: Leandro Rabindranath León

Definition in file writeBalance.C.

Typedef Documentation

◆ Node

typedef BinNodeXt<int> Node

Definition at line 187 of file writeBalance.C.

Function Documentation

◆ main()

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

Definition at line 203 of file writeBalance.C.

References Aleph::balance_tree(), Aleph::check_rank_tree(), Aleph::computeHeightRec(), Aleph::destroyRec(), Aleph::insert_by_key_xt(), log2(), Aleph::maps(), Aleph::BinNodeXt< Key >::NullPtr, outputa, outputb, Aleph::preOrderRec(), print_keya(), print_keyb(), root(), and Aleph::searchInBinTree().

◆ print_keya()

void print_keya	(	Node *	p,
		int	,
		int
	)

Definition at line 198 of file writeBalance.C.

References outputa.

Referenced by main().

◆ print_keyb()

void print_keyb	(	Node *	p,
		int	,
		int
	)

Definition at line 193 of file writeBalance.C.

References Aleph::BinNodeXt< Key >::get_key(), and outputb.