Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
writeRankTree.C File Reference

Ranked BST demo using BinNodeXt subtree sizes (select/order-statistics + visualization output). More...

#include <iostream>
#include <fstream>
#include <tclap/CmdLine.h>
#include <aleph.H>
#include <tpl_dynArray.H>
#include <tpl_binNodeXt.H>
#include <tpl_binNodeUtils.H>
#include <tpl_binTree.H>
Include dependency graph for writeRankTree.C:

Go to the source code of this file.

Typedefs

typedef BinNodeXt< int > Node
 

Functions

void print_key (Node *p, int, int)
 
void print_count (Node *p, int, int)
 
void print_tag (Node *, int, int pos)
 
int main (int argc, char *argv[])
 

Variables

ofstream output
 

Detailed Description

Ranked BST demo using BinNodeXt subtree sizes (select/order-statistics + visualization output).

Overview

This example demonstrates a ranked binary search tree: each node stores the size of its subtree, enabling order statistics operations such as:

  • select(root, k) — return the node at inorder position k.
  • rank/position queries via helpers in tpl_binNodeUtils.H.

This file builds a plain BST (not self-balancing) using insert_by_key_xt(). Therefore, asymptotic costs are expressed in terms of the tree height h.

Data model used by this example

  • Node type: Node = BinNodeXt<int>
  • Key type: int
  • Rank field: Node::getCount() stores subtree size.

Usage / CLI

This example uses TCLAP:

  • --count / -n <int>: number of inserted elements (default: 10).
  • --seed / -s <unsigned>: RNG seed (0 means use time(); default: 0).
  • --help: show help.
# Generate ranked BST with 25 nodes
./writeRankTree --count 25
# Use a specific seed
./writeRankTree --count 50 --seed 42
# Show help
./writeRankTree --help

Algorithm / operations

  • Insertion: insert_by_key_xt(root, new Node(key)) updates subtree counts.
  • Select: select(root, k) uses left-subtree sizes to descend.

Output

This example generates one file:

  • rank-tree-aux.Tree

The file contains:

  • A preorder traversal of keys.
  • A START-AUX section with inorder traversal of subtree counts.
  • Position tags (inorder) intended for btreepic-style visualization.

Complexity

Let h be the tree height.

  • insert/search/remove: O(h)
  • select(k) / rank queries: O(h)

If the tree were balanced, then h = O(log n). In this example (plain BST) h can be O(n) in the worst case.

Pitfalls and edge cases

  • For sorted/near-sorted insert sequences, the BST can become degenerate.
  • Output is overwritten: rank-tree-aux.Tree is opened for writing each run.

References / see also

Author
Leandro Rabindranath León

Definition in file writeRankTree.C.

Typedef Documentation

◆ Node

typedef BinNodeXt<int> Node

Definition at line 128 of file writeRankTree.C.

Function Documentation

◆ main()

◆ print_count()

void print_count ( Node p,
int  ,
int   
)

Definition at line 137 of file writeRankTree.C.

References output.

Referenced by main().

◆ print_key()

void print_key ( Node p,
int  ,
int   
)

Definition at line 132 of file writeRankTree.C.

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

Referenced by main().

◆ print_tag()

void print_tag ( Node ,
int  ,
int  pos 
)

Definition at line 142 of file writeRankTree.C.

References Aleph::maps(), and output.

Referenced by main().

Variable Documentation

◆ output

ofstream output

Definition at line 130 of file writeRankTree.C.

Referenced by main(), print_count(), print_key(), and print_tag().