|
Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
|
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>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 |
Ranked BST demo using BinNodeXt subtree sizes (select/order-statistics + visualization output).
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.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.
Node = BinNodeXt<int>intNode::getCount() stores subtree size.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.insert_by_key_xt(root, new Node(key)) updates subtree counts.select(root, k) uses left-subtree sizes to descend.This example generates one file:
rank-tree-aux.TreeThe file contains:
START-AUX section with inorder traversal of subtree counts.btreepic-style visualization.Let h be the tree height.
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.
rank-tree-aux.Tree is opened for writing each run.tpl_binNodeXt.H (ranked node)tpl_binNodeUtils.H (order-statistics utilities)writeSplit.C (split operation uses ranks)btreepic.C (visualization)Definition in file writeRankTree.C.
Definition at line 128 of file writeRankTree.C.
| int main | ( | int | argc, |
| char * | argv[] | ||
| ) |
Definition at line 147 of file writeRankTree.C.
References Aleph::check_bst(), Aleph::check_rank_tree(), Aleph::computeHeightRec(), Aleph::destroyRec(), Aleph::inOrderRec(), Aleph::insert_by_key_xt(), KEY, Aleph::maps(), min(), Aleph::BinNodeXt< Key >::NullPtr, output, Aleph::preOrderRec(), print_count(), print_key(), print_tag(), root(), Aleph::searchInBinTree(), and Aleph::select().
| void print_count | ( | Node * | p, |
| int | , | ||
| int | |||
| ) |
| 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().
| void print_tag | ( | Node * | , |
| int | , | ||
| int | pos | ||
| ) |
Definition at line 142 of file writeRankTree.C.
References Aleph::maps(), and output.
Referenced by main().
| ofstream output |
Definition at line 130 of file writeRankTree.C.
Referenced by main(), print_count(), print_key(), and print_tag().