1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
////////////////////////////////////////////////////////////
//
// File name: splaytree.hxx
//
// Title: Splay Tree class
//
// Desciption:
//
// Author: Scott Holden (t-scotth)
//
// Date: August 16, 1994
//
////////////////////////////////////////////////////////////
#ifndef _SPLAY_TREE_HXX_
#define _SPLAY_TREE_HXX_
typedef int BOOLEAN;
#define TRUE 1
#define FALSE 0
#define NULL 0
template<class T> class SplayTree;
template<class T>
class SplayNode {
friend class SplayTree<T>;
private:
SplayNode<T> *_Parent;
SplayNode<T> *_RightChild;
SplayNode<T> *_LeftChild;
T *_Data;
SplayNode( ) : _Data( NULL ),
_Parent( NULL ),
_RightChild( NULL ),
_LeftChild( NULL ) { }
SplayNode( T *a ) : _Data( a ),
_Parent( NULL ),
_RightChild( NULL ),
_LeftChild( NULL ) { }
~SplayNode() { }
};
template<class T>
class SplayTree {
friend class SplayNode<T>;
private:
SplayNode<T> *_Root;
unsigned int _Size;
void Splay ( SplayNode<T> * );
// returns pointer to the root of the tree
void Delete( SplayNode<T> * );
SplayNode<T>* InsertAsRightChild( SplayNode<T> *, SplayNode<T> * );
SplayNode<T>* InsertAsLeftChild ( SplayNode<T> *, SplayNode<T> * );
BOOLEAN IsRoot ( SplayNode<T> *a )
{ return ( a == _Root ? TRUE : FALSE ); }
BOOLEAN IsRightChild( SplayNode<T> *a )
{
if ( a->_Parent != NULL) {
return ( a == a->_Parent->_RightChild ? TRUE : FALSE );
}
return FALSE;
}
BOOLEAN IsLeftChild( SplayNode<T> *a )
{
if ( a->_Parent != NULL ) {
return ( a == a->_Parent->_LeftChild ? TRUE : FALSE );
}
return FALSE;
}
SplayNode<T>* Successor ( SplayNode<T> * );
SplayNode<T>* Predecessor ( SplayNode<T> * );
SplayNode<T>* SubtreeSuccessor ( SplayNode<T> * );
SplayNode<T>* SubtreePredecessor( SplayNode<T> * );
SplayNode<T>* Find( SplayNode<T> *, T * );
SplayNode<T>* MaximumNode( );
SplayNode<T>* MinimumNode( );
public:
//SplayTree() : _Root( NULL ), _Size( 0 ) { }
SplayTree( T *a = NULL ) : _Root( NULL ), _Size( 0 ) { if ( a != NULL ) { Insert( a ); } }
~SplayTree();
void Insert( T * );
T* Find ( T * );
T* Delete( T * );
T* Minimum( )
{
SplayNode<T> *Temp = MinimumNode( );
return Temp->_Data;
}
T* Maximum( )
{
SplayNode<T> *Temp = MaximumNode( );
return Temp->_Data;
}
T* Successor ( T * );
T* Predecessor( T * );
unsigned int Size() { return _Size; }
#ifdef DEBUGRPC
void Print( );
unsigned int Depth( ) { return Depth( _Root, 0 ); }
private:
void Print( SplayNode<T> * );
unsigned int Depth( SplayNode<T> *, unsigned int );
#endif // DEBUGRPC
};
#include "splaytre.inl"
#endif // _SPLAY_TREE_HXX_
|
