一种高效查找树-radix的实现

1.引言

我们知道，unoredered_map是一种查找时间复杂度o(1)的数据结构，经常用在数据查找相关的地方，但是在使用unordered_map进行数据查找时，hash冲突是一件令人很头疼的事情，因为hash冲突导致unordered_map的查找效率降低。radix就是一种适用于基于二进制表示的键值的查找树，在数据量增大的时候不会影响其查找效率。由于我在一个项目中发现使用unordered_map在处理大量数据的时候效率并不高，因此来学习radix,本文将介绍radix的原理，并将我所实现并用于项目的代码分享出来。

2.介绍

radix是一种基于前缀树的思想的适用于基于二进制表示的键值的查找树。用图来解释直观明了。

3.实现

在使用radix这种数据结构的时候，会涉及到多次申请空间的过程，unordered_map使用的时STL自己的allocator。我使用的是boost中pool的一个对象池，因为每次申请的对象都是一样大的。

如何插入数据

radix是一种很巧妙的数据结构(感觉想出来的人是个天才)，并且很简单，难的地方可能就是这个插入数据部分。难点在于每次如何获取Key值的二进制位上的一位、两位或多位。这个视具体情况，为了不让整个树层数过深，我采用每次获取两二进制的方法来实现的。
话不多说，上代码

#define CHECK_BITS(key,pos) ((((unsigned int)(key))<<sizeof(int)*8-((pos)+1)*BITS)>>(sizeof(int)*8-BITS))

这行代码负责每次获取两位二进制的值。

#pragma once
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<boost\pool\pool.hpp>
#include<stddef.h>
using namespace std;

#define RADIX_INSERT_VALUE_OCCUPY -1	//该节点已被占用
#define RADIX_INSERT_VALUE_SAME -2		//插入了相同的值
#define RADIX_DELETE_ERROR -3			//删除错误

typedef int k_type;
typedef char* v_type;

#define BITS 2
const int radix_tree_height = sizeof(k_type) * 8 / BITS;//树的高度
//返回key中由pos指定的位的值，位数由BITS指定，每次获取两位二进制的值
#define CHECK_BITS(key,pos) ((((unsigned int)(key))<<sizeof(int)*8-((pos)+1)*BITS)>>(sizeof(int)*8-BITS))
//基数树节点
struct radix_node_t {
	radix_node_t* child[4];//四个指向下层节点的指针数组，分别指向节点储存值为00 01 10 11的节点。
	radix_node_t* parent;//记录夫结点
	v_type value;//节点储存的值
};
//基数树头节点
struct radix_head {
	//根节点
	radix_node_t* root;
	//储存已分配但不在树中的节点（双向链表，这里储存其中的一个节点）
	size_t number;//存储目前有多少个存进来的节点。
};

class radix
{
public:
	radix()
		:_pool(sizeof(radix_node_t))
	{
		t = (radix_head*)malloc(sizeof(radix_head));
		t->number = 0;
		t->root = (radix_node_t*)_pool.malloc();
		for (int i = 0; i < 4; i++)
			t->root->child[i] = nullptr;
		t->root->value = nullptr;
	}
	int insert(k_type key, v_type value)
	{
		int i, temp;
		radix_node_t* node, *child;
		node=t->root;
		for (i = 0; i < radix_tree_height; i++) {
			//从低位开始获取每两位的值
			temp = CHECK_BITS(key, i);

			if (node->child[temp] == nullptr) {
				child = (radix_node_t*)_pool.malloc();
				if (!child)return NULL;

				//显示构造
				for (int i = 0; i < 4; i++)
					child->child[i] = nullptr;
				child->value = nullptr;

				child->parent = node;
				node->child[temp] = child;
				node = node->child[temp];
			}
			else {
				node = node->child[temp];
			}
		}
		//已经插入返回-2
		if (node->value == value)return RADIX_INSERT_VALUE_SAME;
		//插入节点有其他值返回-3
		if (node->value != nullptr)return RADIX_INSERT_VALUE_OCCUPY;
		node->value = value;
		//计数加1
		++t->number;
		return 0;
	}
	int Delete(k_type key)
	{
		radix_node_t* tar = find(key);
		if (tar == nullptr)
		{
			cout << "删除失败" << endl;
			return RADIX_DELETE_ERROR;//返回-3，删除失败，没有该数据
		}
		else
		{
			radix_node_t* par = tar->parent;
			//printf("真正删除%d\n", tar->value->_pageid);
			tar->value = nullptr;
			_pool.free(tar);
			--t->number;
			for (int i = 0; i < 4; i++)
			{
				if (par->child[i] == tar)
				{
					par->child[i] = nullptr;
					break;
				}
			}
			//printf("减少到%d个\n", t->number);
		}
		return 0;
	}
	void print()
	{
		radix_node_t* node = t->root;
		_radix_print(node);
	}
	radix_node_t* find(k_type key)
	{
		int i = 0, temp;
		radix_node_t* node;
		node = t->root;
		while (node && i < radix_tree_height) {
			temp = CHECK_BITS(key, i++);
			node = node->child[temp];
		}
		if (node == nullptr||node->value==nullptr)
			return nullptr;
		return node;
	}
private:
	void _radix_print(radix_node_t* node)
	{
		if (node == nullptr)return;
		if (node->value != nullptr)
			printf("%s\n", node->value);
		_radix_print(node->child[0]);
		_radix_print(node->child[1]);
		_radix_print(node->child[2]);
		_radix_print(node->child[3]);
	}
private:
	boost::pool<> _pool;
	radix_head* t;
};