数据结构(查找:二叉排序树 + 平衡二叉树 + B-树 + 哈希表)
一、查找表
查找表是由同一类型的数据(或记录)构成的集合
对查找表进行的操作有:
(1)查找某个“特定的”数据元素是否在表中
(2)查找某个“特定的”数据元素的各种属性
(3)在查找表中插入一个数据元素
(4)从查找表中删除一个数据元素
(1)(2)是静态查找,(3)(4)动态查找
二、二叉排序树(BST)(二叉查找树)
1.性质:
(1)若它的左子树不空,则左子树上所有结点的值均小于根节点
(2)若它的右子树不空,则右子树上所有结点的值均大于根节点
2.二叉排序树的插入和删除
(1)插入
首先找到要插入的位置,然后该元素与当前位置的元素比较大小,再插入到相应的左子树OR右子树。
/*
* 将结点插入到二叉树中
*
* 参数说明:
* root 二叉树的根结点
* node 要插入的结点
*/
void BSTree::insert(BSTNode*& root, BSTNode* node)
{
BSTNode* y = NULL;
BSTNode* x = root;
/*找到要插入的位置*/
while (x != NULL)
{
y = x;
if (node->key > x->key)
x = x->right;
else x = x->left;
}
/*插入结点*/
node->parent = y;
if (y == NULL)
root = node;
else if(y->key > node->key)
y->left = node;
else y->right = node;
}
void BSTree::insert(int key)
{
BSTNode* node = new BSTNode(key, NULL, NULL, NULL);
insert(root, node);
}
(2)删除
- 若删除的是叶子结点,只需把父节点的相应孩子结点置为空即可。
- 若删除的结点只有一个孩子,则将它的父节点指向它的子节点
- 若删除的结点有两个孩子,可以选左子树最大元素替代该结点,或者选右子树最小元素替代该结点。
三、平衡二叉树
定义:左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值<=1。所有结点的平衡因子可能是-1,0,1.
插入:先插入到相应的位置,然后再调整
删除:跟BST的操作一样。
四、B-树
一棵m阶的B-树,满足以下条件:
- 树中每个结点至多有m棵子树
- 根结点至少有两棵子树
- 除根之外的结点至少有m/2向上取整棵子树
四、哈希表
哈希冲突:对于不同的关键字得到相同的哈希地址
处理冲突的办法:
(1)开放地址法
- 线性探测再散列:di = 1, 2, 3,4 …
- 二次线性探测再散列: di = 1方,-1方,2方,-2方…
- 随机探测再散列:di = 随机数序列
(2)再哈希法
给不同的哈希函数,产生地址冲突时计算另一个哈希函数地址,直到不再发生冲突。
(3)链地址法
(4)建立一个公共溢出区
一旦发生冲突,就填入溢出表中。