#include <iostream>
#include <string>
#include <assert.h>
using namespace std;
typedef struct radix_node_s radix_node_t;
struct radix_node_s
{
radix_node_t *left;
radix_node_t *right;
radix_node_t *parent;
string key;
string value; //more general definition : void* data
radix_node_s():left(NULL),right(NULL),parent(NULL),key(""),value(""){}
};
struct radix_tree_t
{
radix_node_t *root;
radix_tree_t()
{
root = new radix_node_t;
}
};
static void radix_tree_insert(radix_tree_t* T, string key, string value)
{
int i = 0;
radix_node_t *node,*child;
node = T->root;
for (i = 0; i < (int)key.length(); i++)
{
if(key[i] == '0')//insert left
{
if(node->left == NULL)
{
child = new radix_node_t();
assert( child != NULL);
child->parent = node;
node->left = child;
node = node->left;
//cout << "new left" << endl;
}
else
{
//cout << "left" << endl;
node = node->left;
}
}
else//right
{
if(node->right == NULL)
{
child = new radix_node_t();
assert( child != NULL);
child->parent = node;
node->right = child;
//cout << "new right" << endl;
node = node->right;
}
else
{
//cout << "right" << endl;
node = node->right;
}
}
}
node->value = value;
// cout << "insert " << s << " ok!" << endl;
}
/*
preorder traversal
*/
static inline void radix_print(radix_node_t* T)
{
if(T == NULL)
{
return;
}
if(T->value != "")
{
cout << T->value << endl;
}
radix_print(T->left);
radix_print(T->right);
}
string radix_tree_find(radix_tree_t* T, string key)
{
radix_node_t *node;
string radix_value("radix_null_value");
node = T->root;
int i = 0;
while(node)
{
if(key[i] == '0')
{
node = node->left;
}
else
{
node = node->right;
}
i++;
if(i == (int)key.length())
{
break;
}
}
if(node == NULL)
{
return radix_value;
}
if(node->value != "")
{
radix_value = node->value;
}
return radix_value;
}
int radix_tree_delete(radix_tree_t* T, string key)
{
radix_node_t* node;
node = T->root;
#define RADIX_ERROR -1
#define RADIX_OK 0
string radix_value("");
int i = 0;
while(node)
{
if(key[i] == '0')
{
node = node->left;
}
else
{
node = node->right;
}
i++;
if(i == (int)key.length())
{
break;
}
}
//find no such key
if(node == NULL)
{
return RADIX_ERROR;
}
//find the key but not the last
if(node->left || node->right)
{
if(node->value != "")
{
node->value = radix_value;
return RADIX_OK;
}
return RADIX_ERROR;
}
//the last
for(;;)
{
if(node->parent->right == node)//right
{
node->parent->right = NULL;
}
else//left
{
node->parent->left = NULL;
}
node = node->parent;
if(node->left || node->right)//not the leaf node
{
break;
}
if(node->value != "")//has data
{
break;
}
if(node->parent == NULL)//reach the root
{
break;
}
}
return RADIX_OK;
}
//TEST
int main()
{
string str, key, val;
radix_tree_t* T = new radix_tree_t;
assert( T != NULL);
while(1)
{
cin >> str;
if(str == "I")
{
cin >> key >> val;
radix_tree_insert(T, key, val);
}
else if(str == "P")
{
radix_print(T->root);
cout << endl;
break;
}
}
string s_key;
cout << "insert the key you want to search : key = "; cin >> s_key;
cout << endl << "result : " << radix_tree_find(T, s_key) << endl;
cout << "delete the key : " << s_key << endl;
if(radix_tree_delete(T, s_key) == 0)
{
cout << "delete ok! " << endl;
}
else
{
cout << "null delete!" << endl;
}
//test search after delete
cout << "search after delete ,result : " << radix_tree_find(T, s_key) << endl;
return 0;
}