第九章 检索

平均查找长度

检索式确定数据元素集合中是否存在数据元素等于特定元素或存在满足某种给定的特征的过程。

衡量检索算法效率的标准是评价查找长度（Average Search Length，ASL），也就是为了确定密钥一个节点在数据集合中的位置，给定值与集合中的元素进行比较的次数。

设共n个元素，平均查找长度为：

$$ ASL = \sum^n_{i=1}p_i \cdot C_i $$

$$C_i$$为查找第i个元素所需要进行的比较次数

$$p_i$$为查找第i个元素的概率

$$ \sum^n_{i=1}p_i=1 $$

9.2.1 顺序检索

从表的一段开始，顺序扫描每个元素。

查找成功时的平均查找长度 $$ ASL = \sum^n_{i=1}i*\frac{1}{n} = (n+1)/2 $$

查找失败时的平均查找长度

$$ ASL = \sum^n_{i=1}n*\frac{1}{n} = n $$

9.2.2二分检索

要求序列是有序的。

二分检索成功的平均查找长度为：

一次成功的元素有一个 二次成功的元素有2个,...

所以一共n个元素，设 $$2^{k-1} < n$$, $$2^{k}>=n$$

那么

$$ ASL = \frac{1}{n}\sum^{k}_{i=1}i*2^{i-1} = 2^k(k-1)+1 $$

失败时的平均查找长度为lgn

代码：

#include<iostream> 
#include <stdio.h>
#include <string.h> 
#include <vector>
#include <queue>
#include <map>
#include <Windows.h>
using namespace std;


int n = 20;

int binary_search(vector<int> &v, int number, int left, int right)
{
    int index = -1, mid = (left + right) / 2;
    if (left <= right)
    {
        if (v[mid] == number)
            index = mid;
        else
        {
            if (number < v[mid])
                index = binary_search(v, number, left, mid - 1);
            else
                index = binary_search(v, number, mid + 1, right);
        }
    }
    return index;
}

int binary_search2(vector<int>& v, int number)
{
    int index = -1, left=0, right=v.size()-1, mid=0;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (v[mid] == number)
        {
            index = mid;
            break;
        }
        else
        {
            if (number < v[mid])
                right = mid - 1;
            else
                left = mid + 1;
        }
    }
    return index;
}

int main() 
{
    vector<int> v;
    for (int i = 0; i != n; i++)
    {
        v.push_back(i);
    }

    int index = -1, number = 10;
    index = binary_search(v, number, 0, v.size()-1);
    cout << index << endl;
    index = binary_search2(v, number);
    cout << index << endl;

    return 0;
}

9.2.3 分块检索

就是块间有序，单块内无序，就是二分查找块，然后顺序搜索块内元素。

9.3 二叉排序树

二分搜索需要的顺序排列数组，不方便插入新元素，所以就需要构建二叉排序树。

规则：

1 左孩子小于根

2 右孩子大于根

3 是个二叉树

但如果一直插右孩子，让树长成一列，那么查找速度就和顺序查找一样了，这样的树不好，我们希望树左右平衡一点，不要有深度太深的节点，所以需要构建平衡二叉树。

9.4 平衡二叉树

经典的平衡树一般指AVL平衡树，这个树一直保持平衡树的状态。还有一些其他的利用访问概率，访问频率等来懒惰的构造平衡树，他们并不保证树一直是平衡树。例如Splay，Treap等。

左子树和右子树都是平衡二叉树，并且左右子树的高度只差不超过1。

维护平衡二叉树有两个场景

1 插入新节点

2 删除节点

在找到位置插入后可能会导致树变得不平衡，要调整树。

一共有四种调整场景

参考链接：https://www.bilibili.com/read/cv15595779/

由于我们设计的节点存储数据种不含有父节点，所以，所有代码在调整树的结构的时候都需要返回调整过后的树的根节点，由上一层函数设置正确的子节点指针。这一点是本算法的核心。

代码（由于急着先复习一边，并没有用oj验证正确性，小心！）：

#include<iostream> 
#include <stdio.h>
#include <string.h> 
#include <vector>
#include <queue>
#include <map>
#include <Windows.h>
using namespace std;


int n = 20;

class Node
{
public:
    int number;
    int height;
    Node* left, * right;

    Node();
    Node(int number);
    int GetBalance();
    void UpdateHeight();
};

Node::Node()
{
    this->number = 0;
    this->height = 0;
    this->left = nullptr;
    this->right = nullptr;
}

Node::Node(int number)
{
    this->number = number;
    this->height = 0;
    this->left = nullptr;
    this->right = nullptr;
}

int Node::GetBalance()
{
    int left_child_height = -1, right_child_height = -1;
    if (this->left != nullptr)left_child_height = this->left->height;
    if (this->right != nullptr)right_child_height = this->right->height;
    return left_child_height - right_child_height;
}

void Node::UpdateHeight()
{
    int left_child_height = -1, right_child_height = -1;
    if (this->left != nullptr)left_child_height = this->left->height;
    if (this->right != nullptr)right_child_height = this->right->height;
    this->height = max(left_child_height, right_child_height) + 1;
}

class AVLTree
{
public:
    Node* root;

    AVLTree();
    AVLTree(vector<int> v);
    ~AVLTree();
    void DeleteTree(Node* root);

    Node* LL(Node* root);
    Node* RR(Node* root);
    Node* LR(Node* root);
    Node* RL(Node* root);
    Node* BalanceNode(Node* root);
    Node* InsertNode(int number);
    void DeleteNode(int number);
    Node* QueryNode(int number);

    void MidPrintf(Node* root);
    void ShowTree();
private:
    Node* InsertNode(Node* root, int number);
    Node* GetNearstNodeFromRightToReplaceDeleteNode(Node** NearstNode, Node* root);
    Node* DeleteNode(Node* root, int number);
    Node* QueryNode(Node* root, int number);
};

AVLTree::AVLTree()
{
    this->root = nullptr;
}

AVLTree::AVLTree(vector<int> v)
{
    this->root = nullptr;
    for (int i = 0; i != v.size(); i++)
        this->InsertNode(v[i]);
}

AVLTree::~AVLTree()
{
    this->DeleteTree(this->root);
}

void AVLTree::DeleteTree(Node* root)
{
    if (root != nullptr)
    {
        this->DeleteTree(root->left);
        this->DeleteTree(root->right);
        delete(root);
    }
}

Node* AVLTree::LL(Node* root)
{
    if (root == nullptr)return root;
    Node* left = nullptr, * left_right = nullptr;
    left = root->left;
    if (left == nullptr)return root;
    left_right = left->right;
    left->right = root;
    root->left = left_right;

    root->UpdateHeight();
    left->UpdateHeight();
    return left;
}

Node* AVLTree::RR(Node* root)
{
    if (root == nullptr)return root;
    Node* right = nullptr, * right_left = nullptr;
    right = root->right;
    if (right == nullptr)return root;
    right_left = right->left;
    right->left = root;
    root->right = right_left;

    root->UpdateHeight();
    right->UpdateHeight();
    return right;
}

Node* AVLTree::LR(Node* root)
{
    if (root == nullptr)return root;
    root->left = RR(root->left);
    return LL(root);
}

Node* AVLTree::RL(Node* root)
{
    if (root == nullptr)return root;
    root->right = LL(root->right);
    return RR(root);
}

Node* AVLTree::BalanceNode(Node* root)
{
    int balance = root->GetBalance();
    if (balance >= 2)
    {
        // 判断是LL还是LR
        if (root->left->GetBalance() >= 1)
        {
            // LL
            return this->LL(root);
        }
        else
        {
            // LR
            root->left = RR(root->left);
            return LL(root);
        }
    }
    if (balance <= -2)
    {
        // 判断是RR还是RL
        if (root->right->GetBalance() >= 1)
        {
            // RL
            root->right = LL(root->right);
            return RR(root);
        }
        else
        {
            // RR
            return RR(root);
        }
    }
    return root;
}

Node* AVLTree::InsertNode(int number)
{
    return this->root = this->InsertNode(this->root, number);
}

Node* AVLTree::InsertNode(Node* root, int number)
{
    if (root == nullptr)return new Node(number);
    if (number < root->number) root->left = InsertNode(root->left, number);
    else root->right = InsertNode(root->right, number);
    root->UpdateHeight();
    return BalanceNode(root);
}

Node* AVLTree::GetNearstNodeFromRightToReplaceDeleteNode(Node **nearstNode, Node* root)
{
    // 此函数的返回值是该子树调整过后的根节点，nearstNode由参数记录，因为拿到这个节点需要调整树，调整树就需要返回修正好的根节点，因为没有父指针，所以只能这样搞
    // 用t记录一会儿要返回的根节点
    Node* t = root;
    if (root->left != nullptr)t = GetNearstNodeFromRightToReplaceDeleteNode(nearstNode, root->left);

    // 如果本节点没有了右孩子节点，那么当前节点就是值最小的节点，即nearstNode，记录结果
    // 如果本节点有右孩子节点，那么更新root->left
    if (t == root)*nearstNode = t;
    else root->left = t;

    // 如果当前节点是结果的父节点，易知结果是没有左孩子的，那么需要看看结果有没有右孩子，当前结果的父节点需要接管结果的右孩子
    if (t == root->left)
    {
        // 如果结果的右孩子不为空，那么我们需要让结果的父节点接管结果的右孩子，因为我们仅仅需要结果这个节点
        // 如果结果的右孩子为空，那么可知这个结果拿走后，结果的父节点的左孩子为空
        if (t->right != nullptr)
            root->left = t->right;
        else
            root->left = nullptr;
    }

    // 拿走结果节点后树的高度有可能会变化，所以要更新高度
    root->UpdateHeight();

    // 拿走结果节点后树有可能不平衡需要调整平衡，并且我们需要返回调平后的新的根节点
    t = BalanceNode(root);
    return t;
}

void AVLTree::DeleteNode(int number)
{
    this->root = this->DeleteNode(this->root, number);
}

Node* AVLTree::DeleteNode(Node* root, int number)
{
    if (root == nullptr)return root;
    if (root->number == number)
    {
        // 找到了需要删除的节点
        // 该节点有4种状态，
        // 1，没有子节点，那么只需要delete这个节点，并返回nullptr
        // 2，有左右孩子节点，那么需要 (在右孩子的树上，找到左边值最小的孩子，来替换当前root节点) 或 (在左孩子的树上，找到右边值最大的孩子，来替换当前root节点)
        // 3，仅有左孩子，直接把左孩子拿来替换当前root节点即可
        // 4，仅有右孩子，直接把右孩子拿来替换当前root节点即可
        if (root->left == nullptr && root->right == nullptr)
        {
            delete(root);
            root = nullptr;
            return root;
        }
        else
        {
            if (root->left != nullptr && root->right != nullptr)
            {
                Node* nearstNode = nullptr;
                root->right = GetNearstNodeFromRightToReplaceDeleteNode(&nearstNode, root->right);
                nearstNode->left = root->left;
                nearstNode->right = root->right;
                delete(root);
                root = nullptr;
                return nearstNode;
            }
            else
            {
                Node* t = nullptr;
                if (root->left == nullptr)
                    t = root->right;
                else
                    t = root->left;
                delete(root);
                root = nullptr;
                return t;
            }
        }
    }
    if (number < root->number)root->left = DeleteNode(root->left, number);
    if (number > root->number)root->right = DeleteNode(root->right, number);
    return root;
}

Node* AVLTree::QueryNode(int number)
{
    return QueryNode(this->root, number);
}

Node* AVLTree::QueryNode(Node* root, int number)
{
    if (root == nullptr || root->number == number)return root;
    if (number < root->number)return QueryNode(root->left, number);
    return QueryNode(root->right, number);
}

void AVLTree::MidPrintf(Node* root)
{
    if (root == nullptr)return;
    MidPrintf(root->left);
    printf("%d ", root->number);
    MidPrintf(root->right);
}

void AVLTree::ShowTree()
{
    queue<Node*> q;
    q.push(this->root);
    int flag = 1;
    while (q.size() && flag)
    {
        int layer_node_size = q.size();
        flag = 0;
        for (int i = 0; i != layer_node_size; i++)
        {
            Node* t = q.front();
            q.pop();
            if (t != nullptr)
            {
                printf("%d ", t->number);
                q.push(t->left);
                q.push(t->right);
                flag = flag || (t->left != nullptr || t->right != nullptr);
            }
            else
            {
                printf("- ");
                q.push(nullptr);
                q.push(nullptr);
            }
        }
        printf("\n");
    }
}

int main()
{
    vector<int> v;
    int a[] = { 0,1,2,3,4,5,6,7 };
    for (int i = 0; i != 8; i++)
    {
        v.push_back(a[i]);
    }

    AVLTree avl_tree(v);
    avl_tree.MidPrintf(avl_tree.root);
    printf("\n");
    avl_tree.ShowTree();
    avl_tree.DeleteNode(3);
    avl_tree.MidPrintf(avl_tree.root);
    printf("\n");
    avl_tree.ShowTree();
    return 0;
}

9.5 最佳二叉排序树和Huffman树

对于n个节点的二叉排序树，如果考虑每个节点分查找概率，使得ASL最小的树是最佳二叉排序树。

设n个元素分别为k_i,对应的查询概率是P(k_i),对应的深度为d_i

$$ ASL = \sum^n_{i=1}P(k_i)*d_i $$

构建方法好像是动规

9.5.3 haffman树

所有叶子节点的带权路径长度之和最小的树就是haffman树，有可能不止一棵。

这个用来给东西编码，比如说a用0表示，b用10，c用11，这样就是编码了三个字母。

对应的树是

易知,要想平均通过编码读取一个字符的速度最快，那么读取频率高的字母应该更靠近根节点。

如果直接把频率高的字符安排的离根节点最近，那么也不是合适的，因为可能导致其他节点过深，比如：

如果考虑从频率低的字符先结合到一起，变成一颗有整体权重的树，那么这样再和权重较大的字符比较的时候，就更加公平。

比如先拿出权重最小的两个字符c和d，结合成一个子树。

以上就是huffman树的构造方法。

代码：

// HaffmanTree.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>
#include <queue>

using namespace std;

class Node
{
    friend bool operator < (const Node a, const Node b);
public:
    char c;
    float weight;
    Node* left, * right;

    Node();
    Node(char c, float weight);
};

bool operator < (const Node a, const Node b)
{
    return a.weight > b.weight;
}

struct NodePointerCmp
{
    bool operator ()(Node *a, Node *b)
    {
        return a->weight > b->weight;
    }
};

Node::Node()
{
    c = ' ';
    weight = 0;
    this->left = nullptr;
    this->right = nullptr;
}

Node::Node(char c, float weight)
{
    this->c = c;
    this->weight = weight;
    this->left = nullptr;
    this->right = nullptr;
}

class HaffmanTree
{
public:
    Node* root;

    HaffmanTree();
    HaffmanTree(const vector<Node> v);
    void DeleteTree(Node* root);
    ~HaffmanTree();
    void PrintCode(Node* root, string preCode);
    void PrintTree();
    float GetTreeASL(Node *root, int height);
    float CalcASL();
};

HaffmanTree::HaffmanTree()
{
    this->root = nullptr;
}

HaffmanTree::HaffmanTree(const vector<Node> v)
{
    this->root = nullptr;
    priority_queue<Node*, vector<Node *>, NodePointerCmp> q;
    for (int i = 0; i != v.size(); i++)q.push(new Node(v[i].c, v[i].weight));
    while (q.size()>1)
    {
        Node *node1 = q.top();
        q.pop();
        Node *node2 = q.top();
        q.pop();
        Node *t = new Node();
        t->weight = node1->weight + node2->weight;
        t->left = node2;
        t->right = node1;
        q.push(t);
    }
    this->root = q.top();
    q.pop();
}

void HaffmanTree::DeleteTree(Node* root)
{
    if (root == nullptr)return;
    DeleteTree(root->left);
    DeleteTree(root->right);
    delete(root);
}

HaffmanTree::~HaffmanTree()
{
    this->DeleteTree(this->root);
}

void HaffmanTree::PrintCode(Node *root, string preCode)
{
    if (root == nullptr)return;
    PrintCode(root->left, preCode+"0");
    if(root->c!=' ')
        printf("%c: %s\n", root->c, preCode.c_str());
    PrintCode(root->right, preCode+"1");
}

void HaffmanTree::PrintTree()
{
    queue<Node*> q;
    q.push(this->root);
    int flag = 1;
    while (q.size() && flag)
    {
        int layer_node_size = q.size();
        flag = 0;
        for (int i = 0; i != layer_node_size; i++)
        {
            Node* t = q.front();
            q.pop();
            if (t != nullptr)
            {
                if (t->c == ' ')
                    printf("- ");
                else
                    printf("%c ", t->c);
                q.push(t->left);
                q.push(t->right);
                flag = flag || (t->left != nullptr || t->right != nullptr);
            }
            else
            {
                printf("- ");
                q.push(nullptr);
                q.push(nullptr);
            }
        }
        printf("\n");
    }
}

float HaffmanTree::GetTreeASL(Node* root, int height)
{
    if (root == nullptr)return 0;
    float left_asl = GetTreeASL(root->left, height+1);
    float right_asl = GetTreeASL(root->right, height+1);
    float asl = left_asl + right_asl;
    if (root->c != ' ')asl+= root->weight*height;
    return asl;
}

float HaffmanTree::CalcASL()
{
    return GetTreeASL(this->root, 0);
}

int main()
{
    vector<Node> v;
    v.push_back(Node('a', 0.3));
    v.push_back(Node('b', 0.3));
    v.push_back(Node('c', 0.2));
    v.push_back(Node('d', 0.2));

    HaffmanTree haffmantree(v);
    haffmantree.PrintCode(haffmantree.root, "");
    printf("\n");
    haffmantree.PrintTree();
    printf("\n");
    float asl = haffmantree.CalcASL();
    printf("%.2f\n", asl);
    return 0;
}

9.6 B树

B树 多路平衡查找树（Balanced Tree），它适合在磁盘等直接存取设备上组织动态的索引表，动态索引结构在文件创建，初始装入记录时生成，在系统运行过程中插入或删除记录时，索引结构本身也可能发生改变，以保持较好的检索性能。

一颗m阶（m>=3）B树，或为空树，或满足以下特性的m叉树

1 树种每个节点置多有m棵子树

2 若根节点不是叶子节点，则至少有两棵子树

3 所有的非终点节点种包含下列信息： （n, p_0, k_1, p_1, k_2, k_n, p_n）

4 除根节点之外的所有非终端节点至少有m/2棵子树，即每个非根节点至少有m/2-1个关键字

5 所有的叶子节点都出现在同一层上

其中k_i为关键字($$i\in[1,n]$$)，且$$k_i < k_{i+1}$$

p_j为指向子树根节点的指针且p_j($$j\in[0,n)$$)所指子树中所有节点的关键字均小于k_{j+1},均大于k_j.

n 为关键字的个数 $$n\in[m/2-1, m-1]$$

就是说是个有序的m叉树，每段内用二分查找

9.7 散列表检索

散列存储的基本思想时以关键码的值为自变量，通过Hash函数，计算出对应的hash值，以这个值最为存储地址。

检索时也是先算Hash值，再去对应的地址取值。

对于不同的关键字算出的Hash值相同的情况，叫做冲突或碰撞。

负载因子 \alpha 反应了散列表的装填程度，其定义为：

$$ \alpha = \frac{散列表种节点的数目}{基本区域能容纳的节点数} $$

当 \alpha >1时，冲突是不可避免的。所以要有对应的解决碰撞的方法。

散列函数

1 除余法

$$ Hash(key) = key%p $$

2 平方取中法

Hash(key) = key^2 中间的几位

3 折叠法

把key拆成几部分，求和，舍去进位

4 数组分析法

只保留关键码能用于区分的几位

5 直接地址法

$$ Hash(key) = key $$

$$ Hash(key) = a*key+b $$

冲突处理

1 开放定址法

当找到的位置已经被占用了，那么就向后偏移d看看，直到找到一个空位置

Hash(key) = (Hash(key)+d) % m

2 再hash法

第一个Hash函数不行，就再换一个Hash函数

3 拉链法

把Hash值相同的元素存储成链表