散列樹

我們選擇質數分辨算法來建立一棵散列樹（Hash樹）。
選擇從2開始的連續質數來建立一個十層的哈希樹。第一層結點為根結點，根結點下有2個結點；第二層的每個結點下有3個結點；依此類推，即每層結點的子節點數目為連續的質數。到第十層，每個結點下有29個結點。如下圖所示：
同一結點中的子結點，從左到右代表不同的餘數結果。
例如：第二層結點下有三個子節點。那么從左到右分別代表：除3餘0，除3餘1，除3餘2.
對質數進行取余操作得到的餘數決定了處理的路徑。結點：結點的關鍵字(在整個樹中是唯一的)，結點的數據對象，結點是否被占據的標誌位(標誌位為真時，關鍵字才被認為是有效的)，和結點的子結點數組。

特點

哈希樹的結構是動態的，也不像某些哈希算法那樣需要長時間的初始化過程，只需要初始化根結點就可以開始工作。哈希樹也沒有必要為不存在的關鍵字提前分配空間。
查找迅速，最多只需要10次取余和比較操作，就可知道這個對象是否存在。哈希樹的查找次數和元素個數沒有關係。
結構不變，哈希樹在刪除的時候並不做任何結構調整。這也是它的一個非常好的優點。常規樹結構在增加元素和刪除元素的時候都要做一定的結構調整。
非排序性，哈希樹不支持排序，沒有順序特性。需要注意的是：哈希樹是一個單向增加的結構，即隨著所需要存儲的數據量增加而增大。即使數據量減少到原來的數量，但是哈希樹的總結點樹不會減少。這樣做的目的是為了避免結構的調整帶來的額外消耗。

C++代碼

// HashTree.cpp : 定義控制台應用程式的入口點。
//選擇質數分辨算法構造一棵哈希樹
#include "stdafx.h"
#include <iostream>
using namespace std;
const int SIZE = 32;//第10個質數為29，餘數不可能大於32，所以數組的固定長度設定為32
const int Prime[10] = {2,3,5,7,11,13,17,19,23,29};
//哈希結點類型
template<class T1, class T2>
class HashNode
{
public:
HashNode();//默認構造函式
HashNode(T1 key, T2 value);//一般構造函式
~HashNode();
public:
T1 m_key; //結點的關鍵字
T2 m_value; //結點的數據對象
bool occupied; //結點是否被占據，如果是表示結點的關鍵字有效
HashNode *child[SIZE]; //結點的子結點數組
};
template<class T1, class T2>
HashNode<T1,T2>::HashNode()
{
occupied=false;
memset(child, NULL, SIZE*sizeof(HashNode<T1,T2>*));
}
template<class T1, class T2>
HashNode<T1,T2>::HashNode(T1 key, T2 value)
{
this->m_key = key;
this->m_value = value;
occupied=false;
memset(child, NULL, SIZE*sizeof(HashNode<T1,T2>*));
}
template<class T1, class T2>
HashNode<T1,T2>::~HashNode()
{
}
//哈希樹類型
template<class T1, class T2>
class HashTree
{
public:
HashTree();
~HashTree();
void InsertNode(T1 key, T2 value);
bool FindNode(T1 key, T2 &value);
void DeleteNode(T1 key);
private:
HashNode<T1,T2> *root;
void Insert(HashNode<T1,T2> *hashNode, int level, T1 key, T2 value);//插入結點
bool Find(HashNode<T1,T2> *hashNode, int level, T1 key, T2 value);//查找
void Delete(HashNode<T1,T2> *hashNode, int level,T1 key);//刪除結點
};
template<class T1, class T2>
HashTree<T1,T2>::HashTree()
{
root = new HashNode<T1,T2>;
}
template<class T1, class T2>
HashTree<T1,T2>::~HashTree()
{
}
template<class T1, class T2>
void HashTree<T1,T2>::InsertNode(T1 key, T2 value)
{
Insert(root,0,key,value);
}
template<class T1, class T2>
void HashTree<T1,T2>::Insert(HashNode<T1, T2> *hashNode, int level, T1 key, T2 value)//插入結點
{
if(hashNode->occupied == false)
{
hashNode->m_key = key;
hashNode->m_value = value;
hashNode->occupied = true;
return;
}
int index = key%Prime[level];
if (hashNode->child[index] == NULL)
{
hashNode->child[index] = new HashNode<T1,T2>;
}
level += 1;
Insert(hashNode->child[index], level, key, value);
}
template<class T1, class T2>
bool HashTree<T1,T2>::FindNode(T1 key, T2 &value)
{
return Find(root, 0, key, value);
}
template<class T1, class T2>
bool HashTree<T1,T2>::Find(HashNode<T1,T2> *hashNode, int level, T1 key, T2 value)//查找
{
if (hashNode->occupied == true)
{
if (hashNode->m_key == key)
{
value = hashNode->m_value;
return true;
}
}
int index = key%Prime[level];
if (hashNode->child[index] == NULL)
{
return false;
}
level += 1;
return Find(hashNode->child[index], level, key, value);
}
template<class T1, class T2>
void HashTree<T1,T2>::DeleteNode(T1 key)
{
Delete(root, 0, key);
}
template<class T1, class T2>
void HashTree<T1,T2>::Delete(HashNode<T1,T2> *hashNode, int level, T1 key)//刪除結點
{
if (hashNode->occupied == true)
{
if (hashNode->m_key == key)
{
hashNode->occupied = false;
cout << "關鍵字為" << key << "結點已被刪除！" << endl;
return;
}
}
int index = key%Prime[level];
if (hashNode->child[index] == NULL)
{
cout << "該關鍵字不存在！" << endl;
return;
}
level += 1;
Delete(hashNode->child[index], level, key);
}
int _tmain(int argc, _TCHAR* argv[])
{
HashTree<int, int> ht;
ht.InsertNode(1, 8);
ht.InsertNode(2, 0);
ht.InsertNode(3, 4);
ht.InsertNode(4, 7);
ht.InsertNode(5, 4);
ht.InsertNode(6, 3);
ht.InsertNode(7, 8);
int nvalue = 0;
cout << ht.FindNode(5,nvalue) << endl;
cout << ht.FindNode(9,nvalue) << endl;
ht.DeleteNode(4);
ht.DeleteNode(10);
cout<<"baasdfas"<<endl;
system("pause");
return 0;
}

散列樹

基本介紹

散列樹

特點

C++代碼

相關詞條

熱門詞條