数据结构（查找：二叉排序树 + 平衡二叉树 + 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）删除