-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathTTTree.cpp
More file actions
50 lines (47 loc) · 1.33 KB
/
Copy pathTTTree.cpp
File metadata and controls
50 lines (47 loc) · 1.33 KB
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
//Find the record that matchs a given key value
template <typename Key, typename E>
E TTTree<Key,E>::
findhelp(TTNode<Key,E>* root, Key k) const
{
if (root == NULL) return NULL;
if (k == root->lkey) return root->lval;
if (k == root->rkey) return root->rval;
if (k < root->lkey)
return findhelp(root->left,k);
else if (root->rkey == EMPTYKEY)
return findhelp(root->center,k);
else if (k < root->rkey)
return findhelp(root->center,k);
else
return findhelp(root->right,k);
}
template <typename Key, typename E>
TTNode<Key,E>* TTTree<Key,E>::
inserthelp(TTNode<Key,E>* rt, const Key k, const E e)
{
TTNode<Key,E>* retval;
if (rt == NULL) //empty tree: create a leaf node
return new TTNode<Key,E>(k,e,EMPTYKEY,NULL,NULL,NULL,NULL);
if (rt->isLeaf()) //at leaf node: insert here
return rt->add(new TTNode<Key,E>)(k,e,EMPTYKEY,NULL,
NULL,NULL,NULL;)
//add to internal node
if (k < rt->lkey)
{
retval = inserthelp(rt->left,k,e);
if (retval == rt->left) return rt;
else return rt->add(retval);
}
else if ((rt->rkey == EMPTYKEY) || (k < rt->rkey))
{
retval = inserthelp(rt->center,k,e);
if (retval == rt->center) return rt;
else return rt->add(retval);
}
else
{
retval = inserthelp(rt->right,k,e);
if (retval == rt->right) return rt;
else return rt->add(retval);
}
}