|
Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
|
Demonstrates BST split by position operation. 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_key1 (Node *p, int, int) |
| void | print_key2 (Node *p, int, int) |
| int | main (int argc, char *argv[]) |
Variables | |
| ofstream | output |
| ofstream | output_1 |
| ofstream | output_2 |
Demonstrates BST split by position operation.
This program demonstrates the split operation for binary search trees with rank information. It divides a BST at a given position, producing two separate BSTs and generating visualization files. Split is a fundamental operation that enables efficient tree manipulation.
The split operation divides a BST at position k, creating:
Key properties:
Standard BSTs don't support efficient position-based operations:
This example uses BinNodeXt which maintains:
select(root, k) and inorder_position(...)/find_position(...)select(root, k)**: Find k-th smallest element in O(h)inorder_position(root, key, ...)**: Find inorder position of a key in O(h)find_position(root, key, ...)**: Find exact/insertion position of a key in O(h)Split by position works by:
| Tree Type | Complexity | Notes |
|---|---|---|
| Balanced with rank | O(log n) | Height is O(log n) |
| Balanced without rank | O(n) | Must traverse to find position |
| Unbalanced | O(n) | Worst case (height can be linear) |
writeJoin.C)split-before-aux.Tree**: Original tree with SPLIT marker (preorder)split-1-aux.Tree**: Left subtree - positions 0 to pos-1 (preorder)split-2-aux.Tree**: Right subtree - positions pos to n-1 (preorder)All files can be visualized with btreepic to see the split operation.
Definition in file writeSplit.C.
Definition at line 228 of file writeSplit.C.
| int main | ( | int | argc, |
| char * | argv[] | ||
| ) |
Definition at line 250 of file writeSplit.C.
References Aleph::check_bst(), Aleph::check_rank_tree(), Aleph::computeHeightRec(), Aleph::destroyRec(), Aleph::insert_by_key_xt(), l, Aleph::maps(), Aleph::BinNodeXt< Key >::NullPtr, num_nodes, output, output_1, output_2, Aleph::preOrderRec(), print_key(), print_key1(), print_key2(), root(), Aleph::searchInBinTree(), Aleph::split_pos(), and Aleph::split_pos_rec().
| void print_key | ( | Node * | p, |
| int | , | ||
| int | |||
| ) |
Definition at line 235 of file writeSplit.C.
References Aleph::BinNodeXt< Key >::get_key(), and output.
Referenced by main().
| void print_key1 | ( | Node * | p, |
| int | , | ||
| int | |||
| ) |
| void print_key2 | ( | Node * | p, |
| int | , | ||
| int | |||
| ) |
| ofstream output |
Definition at line 231 of file writeSplit.C.
Referenced by main(), and print_key().
| ofstream output_1 |
Definition at line 232 of file writeSplit.C.
Referenced by main(), and print_key1().
| ofstream output_2 |
Definition at line 233 of file writeSplit.C.
Referenced by main(), and print_key2().