BTREE Template for class STL

Recently I wrote a BTree similar to STL, and I will share it with you. This BTree's usage is very similar to MAP in STL. I compiled successfully in VC7.1 and Redhat (GCC 3.2). BTREE has not been strictly tested, you are welcome to test the improvement of him.

If you have any questions, or any suggestions, you can contact me. Contact: larrin2002@msn.com.

1.BTREE source #ifndef _larrin_workshop_btree_h # define _larrin_workshop_btree_h

#include

#define begin_namespace namespace larrindsl {#define end_namespace}

#ifndef null # ifdef __cplusplus # Define Null 0 # Else # Define Null ((void *) 0) # Endif # ENDIF

Begin_namespace

Template struct btree_less {bool operator () (const type & _left, const type & _right) const {return _LEFT <_Right;}};

Template struct btree_pair {/ * typename * / _first_first; / * typename * / _second_ second;

Btree_pair () {}

BTree_pair (/ * typeename * / _first_ v1, / * typeename * / _second_ v2) {first = v1; second = v2;

~ btree_pair () {}};

Template > class btree {public:

Typedef key key_type; typef type data_type; typef traits key_compare; typedef unsigned long size_type

Typedef btree_pair value_type;

Private:

typedef btree _btree_; static const unsigned int mid_pos = (int) (order / 2); static const unsigned int max_val_size = order - 1; static const unsigned int min_vals = ((order 1) / twenty one ;

Struct Tree_iterator;

class BTNode {friend class _btree_; friend class _btree _ :: tree_iterator; int keynum; BTNode * parent; int sub_id; // i am my parent's sub_id'th sun value_type * vals [order]; // value node BTNode * subTree [order 1];

PUBLIC:

BtNode () {MEMSET (this, 0, sizeof (btnode));} ~ btnode () {}

Btnode * left_sibling () {if (this-> Parent && this-> Sub_id> 0) {Return this-> Parent-> Subtree [sub_id - 1];

Return NULL;

Btnode * right_sibling () {if (this-> parent && this-> sub_id parent-> keynum) {return this-> parent-> subtree [sub_id 1];}

Return NULL;

Void set_parent (btnode * p, const int sub_id) {this-> parent = p; this-> sub_id = SUB_ID; this-> parent-> subtree [sub_id] = this;}

Key & _Key_ (const Int IDX) {Return Vals [IDX] -> first;

BOOL FIND_IN_NODE (const key & key, int & pos) {if (keynum == 0) {POS = 0; Return False;}

POS = -1;

// binary search ... int top, bottom, mid; TOP = 0; bottom = keynum == 0? 0: keynum -1;

Typename _btree _ :: key_compare less; for (;;) {mid = (TOP BOTTOM) / 2; if (Less (Key, _key_ (mid))) // Key <_key_ (mid) {ix (TOP> = bottom -1) {POS = MID; RETURN FALSE;}

Bottom = MID - 1;} else if (_key_ (mid), key) // key> _key_ (mid) {if (top == bottom) {POS = MID 1; Return False;}

TOP = MID 1;} else // Find it {POS = MID; return true;}}}}

void move_up (int new_key_pos, BTNode * & node, int & where) {BTNode * new_node = new BTNode; int k = 0; for (int i = mid_pos 1; i <= max_val_size; i , k ) {new_node-> vals [ K] = this-> vals [i]; if (this-> subtree [i]) this-> Subtree [i] -> set_parent (new_node, k); this-> keynum--; new_node-> keynum ;} IF (this-> subtree [max_val_size 1]) this-> subtree [max_val_size 1] -> set_parent (new_node, k); if (new_key_pos! = -1) {if (new_key_pos mid_pos) // new key will be move {node = new_node; where = where - MID_POS - 1; new_key_pos = -1; //// Keep new key's position} // else {} // new key will be moveup} if (this-> parent) // Have Parent's {if (new_key_pos! = -1) // new key is moved inTo Parent {node = THIS -> Parent; where = this-> sub_id;

For (int i = this-> parent-> keynum; i> this-> sub_id; i--) {this-> parent-> vals [i] = this-> parent-> value [i-1]; this -> Parent-> Subtree [i] -> set_parent (this-> parent, i 1);}

This-> Parent-> Vals [this-> Sub_ID] = this-> value [mid_pos]; --this-> keynum;

New_node-> set_parent (this-> parent, this-> SUB_ID 1);

IF ( this-> parent-> keynum> max_val_size) {this-> parent-> move_up (new_key_pos, node, where);}} else // i am the current root {btnode; new_root = new btnode; new_root > VALS [0] = this-> vals [mid_pos]; --this-> keynum; new_root-> keynum; if (new_key_pos! = -1) {node = new_root; where = 0;}

this-> set_parent (new_root, 0);

NEW_NODE-> set_parent (new_root, 1);}}

Bool INSERT (const key_type& "{INT POS; IF (Find_in_Node (Key, POS)) // Key Exist in this node already {returnaf false;}

IF (this-> Subtree [POS]! = null) {Return this-> Subtree [POS] -> INSERT (key, data, node, where);} else {for (int i = this-> keynum; i> POS; I -> vals [i] = this-> vals [i-1];

{// where the new key is inserted node = this; where = pos;} vals [pOS] = new value_type; vals [pOS] -> first = key; vals [pOS] -> second = data;

IF ( this-> keynum> max_val_size) // slipt this node, new key will be moved up {move_up (pos, node, where);

Return true;}}} Bool Find (const key, btnode * & node, int & pos) {{node = this; return true;} else {if (this-> Subtree [POS]) {Return this-> Subtree [POS] -> Find (Key, Node, POS);} else {return false;}}}

Btnode * Erase (btnode * node, int idx) {// step1: delete the key delete node-> vals [idx];

// Step2: FORMER BTNODE * LEAF; {INT RIDX; if (null == node-> subtree [id = 1]) // node is a leaf {leaf = node; ridx = idx;} Else {RIDX = 0; Leaf = Node-> Subtree [IDX 1]; While (null! = leaf-> subtree [0]) {leaf = leaf-> subtree [0];} node-> vals [idx] = Leaf-> Vals [0]; // Copy Successor to ...}

//move for (int i = ridx; i keynum - 1; i ) {leaf-> vals [i] = leaf-> vals [i 1];

Leaf-> Keynum--;

// Now the key is remoded, We need Makes Sure of Balance of this Tree

// case 1 if (Leaf-> Keynum> = min_vals) Return NULL;

Return Merge (Leaf);

Btnode * merge (btnode * node) {// case 2 if (! Node-> parent) // this is root too return null; // case 3 {btnode * sibling = node-> left_sibling (); if (Sibling && Sibling-> keynum> min_vals) {for (int i = node-> keynum; i> 0; I -) {node-> vals [i] = node-> vals [i-1]; if (node-> Subtree [i]) Node-> Subtree [i] -> set_parent (Node, i 1);} node-> value [0] = node-> parent-> vals [node-> sub_id-1]; if ( Sibling-> subtree [Sibling-> Keynum]) SIBLING-> Subtree [Sibling-> Keynum] -> set_parent (node, 0); Node-> Keynum ;

Node-> Parent-> Vals [Node-> Sub_ID-1] = Sibling-> Vals [Sibling-> Keynum-1]; SIBLING-> Keynum--; Return Null;}

SIBLING = node-> right_sibling (); if (Sibling && Sibling-> Keynum> min_vals) {node-> vals [node-> keynum] = node-> parent-> vals [node-> sub_id]; if (SIBLING- > Subtree [0]) Sibling-> Subtree [0] -> set_parent (node, node-> keynum 1); node-> keynum ; node-> parent-> vals [node-> sub_id] = Sibling-> VALS [0]

For (int i = 0; i keynum - 1; i ) {sibling-> vals [i] = sibling-> Vals [i 1]; // move ... if (Sibling-> Subtree [ i 1]) SIBLING-> Subtree [i 1] -> set_parent (Sibling, i);} if (Sibling-> Subtree [Sibling-> Keynum]) SIBLING-> Subtree [Sibling-> Keynum] -> set_parent (Sibling, Sibling-> Keynum - 1);

Sibling-> Keynum--; return null;}}

// case 4: do merge count {btnode * left, * right; left = node-> left_sibling (); if (left) {right = node;} else {left = node; Right = node-> right_sibling (); }

// now merge left / right / parent // step1: {left-> vals [left-> keynum] = left-> parent-> value; if (Right-> Subtree [0]) RIGHT -> Subtree [0] -> set_parent (left, left-> keynum 1); left-> keynum ;}

// Step2: remove parent's value {for (int i = left-> sub_id; i parent-> keynum - 1; i ) {left-> parent-> vals [i] = left-> parent-> VALS [i 1]; if (left-> parent-> subtree [i 2]) left-> parent-> subtree [i 2] -> set_parent (left-> parent, i 1);}

LEFT-> Parent-> Keynum--;

// Step3: Merge Left And Right - Move Right Into Left {for (INT I = 0; I Keynum; i ) {Left-> Vals [Left-> Keynum] = Right-> VALS [i]; Left-> keynum ; if (Right-> Subtree [i 1]) Right-> Subtree [i 1] -> set_parent (left, left-> keynum);} delete right;}

IF (Left-> Parent-> Keynum parent-> keynum == 0 &&! left-> parent-> parent) // this is root, left become new root {delete left-> Parent; Left-> parent = null; return left;} else {return merge (left-> parent);}}}}

Void destroy () {for (int i = 0; i keynum; i ) {delete valS [i];}

IF (this-> Subtree [0] == null) // this is a leaf {delete this; return;} else {for (int i = 0; i keynum 1; i ) {this-> Subtree [i] -> destroy ();}}

DELETE THIS;

Btnode * m_root; // btree size_type m_size;

PUBLIC:

Struct Tree_iterator {btnode * curnode; int curkey;

Tree_iterator (): curkey (0) {} Tree_iterator (btnode * node, int key): Curnode (Node), Curkey (KEY) {}

Value_type & operator -> () const {return * (curnode-> vals [curkey]);

Value_type & operator * () const {return * (curnode-> vals [curkey]);

Bool operator == (const tree_iterator & it) const {return (this-> curnode == it.curnode && this-> curkey == it.curbey);}

Bool Operator! = (const tree_iterator & it) const {return (this-> curnode! = it.curnode || this-> curkey! = it.curkey);}

Tree_iterator & operator () {if (Curnode-> Subtree [Curkey 1] == NULL) {if ( Curkey Keynum) {} else {// Check if this is end () btnode * Node = curnode-> parent; if (node ​​== null) {return * this; // end} int TMP = CURNODE-> SUB_ID; while (node ​​&& tmp> = node-> keynum) {tmp = node-> Sub_ID ; Node = node-> parent;}

IF (node ​​== null) {return * this; // end} curkey = tmp; curnode = node;}} else {curnode = CURNODE-> Subtree [Curkey 1]; While (Curnode-> Subtree [0]) {Curnode = CURNODE-> Subtree [0];

Curkey = 0;}

Return * this;}};

Struct const_tree_iterator {const btnode * curnode; int curkey;

Const_tree_iterator (): Curnode (NULL), Curkey (0) {} const_tree_iterator (const key): curkey (node), Curkey (key) {}};

PUBLIC:

TYPEDEF TREE_ITERATOR ITERATOR; TYPEDEF const_tree_iterator const_iterator;

Btree (): m_root (null), m_size (0) {}

~ btree () {clear ();

Iterator begin () {if (! m_root) Return Iterator (NULL, -1);

Btnode * node = m_root; while (node-> subtree [0]) {node = node-> subtree [0];

Return Tree_iterator (node, 0);}

const_iterator begin () const {if (! m_root) Return Iterator (NULL, -1);

Const btnode * node = m_root; while (node-> subtree [0]) {node = node-> subtree [0];

Return const_tree_iterator (node, 0);}

Iterator end () {if (! m_root) Return Iterator (NULL, -1);

Btnode * node = m_root; while (node-> subtree [node-> keynum-1]) {node = node-> subtree [node-> keynum];

Return Tree_Iterator (node, node-> keynum);

BTree_pair Insert (const key & key, const type & data) {typedef btree_pair RET_TYPE;

Btnode * node; int POS;

IF (null == m_root) {m_root = new btnode ();

IF (M_Root-> INSERT (Key, Data, Node, POS) {while (m_root-> parent) {m_root = m_root-> parent;}

M_SIZE ; Return Ret_Type (Iterator (Node, POS), TRUE;}

Return RET_TYPE (this-> end (), false);

TYPE & OPERATOR [] (const key & key) {if (! This-> m_root) {this-> m_root = new btnode;

Iterator it = this-> Find (key); if (it! = this-> end ()) {return (* it). Second;} else {btree_pair res = this-> insert (key, DATA_TYPE ()); return (* res.first). Second;}}

Iterator Find (const key & key) {if (! m_root) Return Iterator (null, -1); btnode * node; int POS;

IF (M_Root-> Find (Key, Node, POS)) {Return Iterator (Node, POS);} else {return end ();}}

SIZE_TYPE ERASE (const key "{iterator it = this-> Find (key); ERASE (IT); Return M_SIZE;}

Void Erase {if (where! = this-> end ()) {btnode * root = m_root-> era (where.curnode, where.curkey); if (root) m_root = root; // weve NEW root; m_size--;}}

Size_type size () {return m_size;}

Void Clear () {if (m_root) {m_root-> destroy ();} m_root = null; m_size = 0;

BOOL EMPTY () {RETURN M_SIZE == 0;}};

END_NAMESPACE

#endif //

2. Test program #include "btree.h" #include

Using Namespace Larrindsl; int main () {typef btree Testtree; testtree a;

Char keys [] = "agfbkdhmjesirxclntup"; for (char * p = keys; * p; p ) {// btree_pair k = a.insert (* p, * p); a [* p] = * p;} a.rase ('h'); a.rase ('r'); a.rase ('p'); a.rase ('d');

Return 0;}