数据结构精讲-CSDN博客

本文链接：https://blog.csdn.net/cube__4/article/details/126623158

查找篇

文章目录

查找篇

符号表

符号表顾名思义，就是一串键值组成的表，这些键值的含义有很多
在这里插入图片描述
这样的表格，已经被抽象成了一种数据类型，并为其定义了一系列的API

在这里插入图片描述

我们将这样的数据结构称为ST（search table），简而言之，专门用于查找的表。

简单表查询的算法及其复杂度
在这里插入图片描述

 Value get(Key key)
 { 
     // 查找给定的键，返回相关联的值
     for (Node x = first; x != null; x = x.next)
     	if (key.equals(x.key))
     		return x.val; // 命中
     return null; // 未名中
 }
void put(Key key, Value val)
 { 
    // 查找给定的键，找到则更新其值，否则在表中新建结点
     for (Node x = first; x != null; x = x.next)
    	 if (key.equals(x.key))
    		 { x.val = val; return; } // 命中，更新
     first = new Node(key, val, first); // 未命中，新建结点
 }

向大小为 N 的有序数组中插入一个新的元素在最坏情况下需要访问∼2N 次数组，因此向一个空符号表中插入 N 个元素在最坏情况下需要访问∼N² 次数组。

//有序数组
Value get(Key key) 
{ 
 	if (isEmpty()) return null; 
 	int i = rank(key); 
     if (i < N && keys[i].compareTo(key) == 0) return vals[i]; 
     else return null; 
}
void put(Key key, Value val) 
 { 
     // 查找旧键，找到则更新值，否则创建新的元素
     int i = rank(key); 
     if (i < N && keys[i].compareTo(key) == 0) 
     { vals[i] = val; return; } 
    // 新键，需要创建
     for (int j = N; j > i; j--) 
     { keys[j] = keys[j-1]; vals[j] = vals[j-1]; } 
     keys[i] = key; vals[i] = val; 
     N++; 
 }

二叉查找树

在这里插入图片描述

一颗树的基本组成由一系列的父节点和其子节点组成。

如果一个父节点有两个子节点，则成为二叉树，这样的树具有二分查找的特点，为此我称其为二分树。

当然，也有多叉树，但这里面存在一个问题是，空间换时间，节点越多，查询越快，但相应的空间更多，为此二叉树可能是一个不错的选择。

一棵二叉查找树（BST）是一棵二叉树，其中每个结点都含有一个 Comparable 的键（以及相关联的值）且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。

在这里插入图片描述

这里就主要记录一下比较重要的几种API

查询（get）

Value get(Key key) 
{ 
    return get(root, key); 
} 
Value get(Node x, Key key) 
{ 
     // 在以x为根结点的子树中查找并返回key所对应的值；
     // 如果找不到则返回null 
     if (x == null) return null; 
     int cmp = key.compareTo(x.key);
     if (cmp < 0) return get(x.left, key); 
     else if (cmp > 0) return get(x.right, key); 
    //上面的操作都一直在递归，从抽象上来看，就像是一直在沿着树进行向下遍历
    //找到后便立即返回
     else return x.val; 
}

插入（put）

    void put(Key key, Value val) 
    { 
        // 查找key，找到则更新它的值，否则为它创建一个新的结点
        root = put(root, key, val); 
    }
    Node put(Node x, Key key, Value val) 
    { 
         // 如果key存在于以x为根结点的子树中则更新它的值；
         // 否则将以key和val为键值对的新结点插入到该子树中
         if (x == null) return new Node(key, val, 1); 
         int cmp = key.compareTo(x.key); 
         if (cmp < 0) x.left = put(x.left, key, val); 
         else if (cmp > 0) x.right = put(x.right, key, val); 
         else x.val = val; 
         x.N = size(x.left) + size(x.right) + 1; 
         return x; 
    }

可以将递归调用前的代码想象成沿着树向下走：它会将给定的键和每个结点的键相比较并根据结果向左或者向右移动到下一个结点。然后可以将递归调用后的代码想象成沿着树向上爬。对于 get() 方法，这对应着一系列的返回指令（return），但是对于 put() 方法，这意味着重置搜索路径上每个父结点指向子结点的链接，并增加路径上每个结点中的计数器的值。

删除（delete）

在删除结点 x 后用它的后继结点填补它的位置。因为 x 有一个右子结点，因此它的后继结点就是其右子树中的最小结点。这样的替换仍然能够保证树的有序性，因为 x.key 和它的后继结点的键之间不存在其他的键。

用 4 个简单的步骤完成将 x 替换为它的后继结点的任务

⚡ 将指向即将被删除的结点的链接保存为 t；
⚡ 将 x 指向它的后继结点 min(t.right)；
⚡ 将 x 的右链接（原本指向一棵所有结点都大于 x.key 的二叉查找树）指向 deleteMin(t.
right)，也就是在删除后所有结点仍然都大于 x.key 的子二叉查找树；
⚡将 x 的左链接（本为空）设为 t.left（其下所有的键都小于被删除的结点和它的后继
结点）

Node delete(Node x, Key key){
	if(x == nullptr) return nullptr;
    auto cmp = key.compare(x.key);
    if(cmp>0) x.right = delete(x.right,key);
    else if(cmp<0) x.left = delete(x.left,key);
    else{
        if(x.left == nullptr) return x.right;
        if(x.right == nullptr) return x.left;
        Node t = x;
        x = min(t.right);
        x.right = deleteMin(t.right);
        x.left = t.left
    }
}

在这里插入图片描述

平衡查找树

针对二分查找树的不稳定性，在最坏情况，树高为N，需要进行改进。我们希望树高为lgN

为了保证查找树的平衡性，我们需要一些灵活性，因此在这里我们允许树中的一个结点保存多个键。确切地说，我们将一棵标准的二叉查找树中的结点称为 2- 结点（含有一个键和两条链接），而现在我们引入 3- 结点，它含有两个键和三条链接。2- 结点和 3- 结点中的每条链接都对应着其中保存的键所分割产生的一个区间。

2-3查找树
- 查找
  
  将二叉查找树的查找算法一般化我们就能够直接得到 2-3 树的查找算法。要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中任意一个相等，查找命中；否则我们就根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接，查找未命中。
- 插入
  - 向 2- 结点中插入新键
    
    如果未命中的查找结束于一个 2- 结点，我们只要把这个 2- 结点替换为一个 3- 结点，将要插入的键保存在其中即可
  - 向一棵只含有一个 3- 结点的树中插入新键
    
    将新键存入该结点中，使之成为一个 4- 结点。它很自然地扩展了以前的结点并含有 3 个键和 4 条链接。创建一个 4- 结点很方便，因为很容易将它转换为一棵由3个2-结点组成的2-3树，其中一个结点（根）含有中键，一个结点含有 3 个键中的最小者（和根结点的左链接相连），一个结点含有 3 个键中的最大者（和根结点的右链接相连）。
  - 向一个父结点为 2- 结点的 3- 结点中插入新键
    
    将临时生成的4-结点中的中键上移到父节点，由于此时父节点为2-结点于是可以变成3-结点，树仍然是有序的。
  - 向一个父结点为 3- 结点的 3- 结点中插入新键
    
    现在假设未命中的查找结束于一个父结点为 3- 结点的结点。我们再次和刚才一样构造一个临时的 4- 结点并分解它，然后将它的中键插入它的父结点中。但父结点也是一个 3- 结点，因此我们再用这个中键构造一个新的临时 4- 结点，然后在这个结点上进行相同的变换，即分解这个父结点并将它的中键插入到它的父结点中去。推广到一般情况，我们就这样一直向上不断分解临时的 4- 结点并将中键插入更高层的父结点，直至遇到一个2- 结点并将它替换为一个不需要继续分解的 3- 结点，或者是到达 3- 结点的根。（递归）
    
    分解根节点：如果从插入结点到根结点的路径上全都是 3- 结点，我们的根结点最终变成一个临时的 4- 结点。此时我们可以按照向一棵只有一个 3- 结点的树中插入新键的方法处理这个问题。我们将临时的 4- 结点分解为 3 个 2- 结点，使得树高加 1。
    
    局部变换：将一个 4- 结点分解为一棵 2-3 树可能有 6 种情况，这个 4- 结点可能是根结点，可能是一个 2- 结点的左子结点或者右子结点，也可能是一个 3- 结点的左子结点、中子结点或者右子结点。由于插入算法的根本就是变换，并且它是局部的，不需要全局改变或者修改，就能保证树的完整性。

在这里插入图片描述
由于实现困难，为此进行了相应的抽象，将2-3树抽象化成红黑树

红黑树
- 基本思想：标准的二叉查找树+额外信息（替换3-结点）
- 红黑树的定义：我们将红黑树中的链接分为两种类型：红链接将两个 2- 结点连接起来构成一个 3- 结点，黑链接则是 2-3 树中的普通链接。
- 等价的定义：
```
‰ 红链接均为左链接；
‰ 没有任何一个结点同时和两条红链接相连；
‰ 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。
满足这样定义的红黑树和相应的 2-3 树是一一对应的
```
- 代码实现：
  - 颜色的表示：因为每个结点都只会有一条指向自己的链接（从它的父结点指向它），我们将 链接的颜色保存在表示结点的 Node 数据类型的布尔变量 color 中。如果指向它的链接是红色的，那么该变量为 true，黑色则为 false。我们约定空链接为黑色。
```
static bool RED = true;
static bool BLACK = false;
struct RBNode
{
     Key key; // 键
     Value val; // 相关联的值
     RBNode left, right; // 左右子树
     int N; // 这棵子树中的结点总数
     boolean color; // 由其父结点指向它的链接的颜色
};
bool isRed(RBNode x)
{
 if (x == null) return false;
 return x.color == RED;
}
```
  - 修复：在我们实现的某些操作中可能会出现红色右链接或者两条连续的红链接，但在操作完成前这些情况都会被小心地旋转并修复。旋转操作会改变红链接的指向。共有左旋和右旋两者修复方法。左旋转：接受一条指向红黑树中的某个结点的链接作为参数。假设被指向的结点的右链接是红色的，这个方法会对树进行必要的调整并返回一个指向包含同一组键的子树且其左链接为红色的根结点的链接，基本思想就是两个键中较小者作为根结点变为较大者作为根结点。（右旋只需要改变左右节点顺序即可）
```
Node rotateLeft(RBNode h)
{
     RBNode x = h.right;
     h.right = x.left;
     x.left = h;
     x.color = h.color;
     h.color = RED;
     x.N = h.N;
     h.N = 1 + size(h.left)
     + size(h.right);
     return x;
}
```
- 插入操作：
  - 向单个 2- 结点中插入新键：
    
    一棵只含有一个键的红黑树只含有一个 2- 结点。插入另一个键之后，我们马上就需要将它们旋转。如果新键小于老键，我们只需要新增一个红色的结点即可，新的红黑树和单个 3- 结点完全等价。如果新键大于老键，那么新增的红色结点将会产生一条红色的右链接。我们需要使用 root = rotateLeft(root); 来将其旋转为红色左链接并修正根结点的链接，插入操作才算完成。
  - 向树底部的 2- 结点插入新键（和第一种情况一样）
  - 向一棵双键树（即一个 3- 结点）中插入新键（难）
    
    这种情况又可分为三种子情况：新键小于树中的两个键，在两者之间，或是大于树中的两个键。每种情况中都会产生一个同时连接到两条红链接的结点，而我们的目标就是修正这一点。
    1. 新键大于原树中的两个键：被连接到 3- 结点的右链接（最简单），此时树是平衡的，根结点为中间大小的键，它有两条红链接分别和较小和较大的结点相连。如果我们将两条链接的颜色都由红变黑，那么我们就得到了一棵由三个结点组成、高为 2 的平衡树。
    2. 新键小于原树中的两个键：产生了两条连续的红链接，解决办法右旋一次，再变色即可
    3. 新键介于原树中的两个键之间：会产生两条连续的红链接，一条红色左链接接一条红色右链接，先左旋再右旋，最后变色即可。
  - 颜色变换
```
void flipColors(RBNode h)
{
     h.color = RED;
     h.left.color = BLACK;
     h.right.color = BLACK;
}
```
    根结点总是黑色！！在每次插入后都会将根结点设为黑色。
  - 向树底部的 3- 结点插入新键H
  - 将红链接在树中向上传递（由下而上），使用左旋转、右旋转和颜色转换这三种简单的操作（在递归调用之后进行），我们就能够保证插入操作后红黑树和 2-3 树的一一对应关系。在沿着插入点到根结点的路径向上移动时在所经过的每个结点中顺序完成以下操作，我们就能完成插入操作。
- 插入代码
```
public Node put(Key key, Value value){
    root = put(root, key, value);
    root.color = BLACK;//根节点的颜色是黑色
}
private Node put(Node h, Key key, Value value){
	if(h == nullptr) return new Node();
    bool cmp = key.compareTo(h.key);
    if(cmp>0) h.right = put(h.right,key,value);
    else if(cmp<0) h.left = put(h.left,key,value);
    else h.val = val;
    if (isRed(h.right)&&(!isRed(h.left))) rotateLeft(h);
    if (isRed(h.left)&&(isRed(h.left.left))) rotateRight(h);
    if (isRed(h.right)&&(isRed(h.left))) flipColors(h);
    h.N = 1+size(h.left)+size(h.right);
    return h;
    //第一条 if 语句会将任意含有红色右链接的 3- 结点（或临时的 4- 结点）向左旋转；第二条 if 语句会将临时的 4- 结点中两条连续红链接中的上层链接向右旋转；第三条 if 语句会进行颜色转换并将红链接在树中向上传递
}
```
- 删除操作
  - 这个过程比插入一个结点更加复杂，因为我们不仅要在（为了删除一个结点而）构造临时 4- 结点时沿着查找路径向下进行变换，还要在分解遗留的 4- 结点时沿着查找路径向上进行变换（同插入操作）。
  - 代码：
```
// delete 
public void delete(Key key){
    if(!isRed(root.left)&&!isRed(root.right)){
        root.color = RED;
    }
    root = delete(root,key);
    if(!isEmpty()) root.color = BLACK;
}
private RBNode delete(RBNode h, Key key){
    bool cmp = key.compareTo(h.key);
    if(cmp<0){
        //---------------deleteMin(root)
        if(!isRed(h.left)&&!(isRed(h.left.left))){
            h = MoveRedLeft(h);
        }
        h.left = delete(h, key);
        
    }
    else{
        //------------deleteMax(root)
        if(isRed(h.right)){
            h = rotateRight(h);
        }
        if(key.compareTo(h.key)==0&&(h.right == nullptr)){
            return nullptr;
        }
        if(!isRed(h.right)&&!isRed(h.right.left)){
            h = MoveRedRight(h);
        }
        //-------------
        if(key.compareTo(h.key)==0){
            h.val = get(h.right, min(h.right).key);
 			h.key = min(h.right).key;
 			h.right = deleteMin(h.right);
        }
        else{
            h.right = delete(h.right,key);
        }   
    }
    return balance (h);
}
```
- 性质分析
  - 无论键的插入顺序如何，红黑树都几乎是完美平衡的
  - 一棵大小为 N 的红黑树的高度不会超过 2lgN