首页 数据结构（C++）
  1. 集合操作的实现
    1.1 集合的并运算
    1.2 集合的交运算
  2. 顺序查找
    2.1 顺序存储结构
    2.2 基于顺序存储结构的顺序查找算法
    2.3 基于有序顺序表的顺序查找算法
    2.4 索引顺序表
  3. 并查集
    3.1 并查集类的描述
    3.2 查找算法
    3.3 合并操作
  4. 二叉排序树 (BST)
    4.1 二叉排序树结点定义
    4.2 二叉排序树类定义
    4.3 查找算法
    4.4 插入算法
    4.5 建立算法
    4.6 删除算法
  5. 二叉平衡树 (AVL)
    5.1 四种失衡情况
    5.2 插入和调整实例
  6. 2-3 树
    6.1 两种内部结点的含义
    6.2 插入操作
    6.3 删除操作
  7. B 树
    7.1 查找
    7.2 插入
    7.3 删除
  8. 哈希表
    8.1 哈希函数的构造方法
    8.2 处理冲突方法

# 一、集合操作的实现

# 1. 集合的并运算

// 集合的并运算
void Union(SeqList<int> &LA,SeqList<int> &LB)
{
    int n1=LA.Length(),n2=LB.Length();
    int i,k,x;
    for(i=0;i<n2;++i)
    {
        x=LB.getData(i);// 在 LB 中取一元素
        k=LA.Search(x);// 在 LA 中搜索它
        if(k==0)// 若在 LA 中未找到，则插入它
        {
            LA.Insert(n1,x);// 插入到第 n1 个表项位置
            n1++;
        }
    }
}

# 2. 集合的交运算

// 集合的交运算
void Intersection(SeqList<int> &LA,SeqList<int> &LB)
{
    int n1=LA.Length();
    int x,k,i=0;
    while(i<n1)
    {
        x=LA.getData(i);// 在 LA 上取一元素
        k=LB.Search(x);// 在 LB 上搜索它
        if(k==0)
        {
            LA.Remove(i,x);
            n1--;// 在 LA 中删除它
        }
        else
        {
            i++;
        }
    }
}

# 二、顺序查找

# 1. 顺序存储结构

// 顺序存储结构类型定义如下
typedef int Key; // 定义 Key 类型为 int
struct Rec
{
    Key key;
    ...;
};
Rec S[n+1];// 元素分别存放在 S [1] 至 S [n]

# 2. 基于顺序存储结构的顺序查找算法

# 普通实现算法

image-20251101154117554
int Search(Rec S[],Key x,int n)// 基于顺序存储结构的顺序查找算法
{
    int i=1;// 从头开始查看
    while(S[i].key!=x && i<=n)
    {
        i++;// 往后查找
    }
    if(i<=n)
    {
        return i;
    }
    else
    {
        return 0;
    }
}


# 改进算法 1

image-20251101154552044

改进算法 1 的核心改进是引入 “监视哨”，

通过在数组尾端放置要查找的元素，

消除了循环中的边界判断，从而简化逻辑并提高查找效率。

// 改进算法 1
int Search(Rec S[],Key x,int n)// 基于顺序存储结构的顺序查找算法
{
    // 顺序查找关键码为 x 的数据对象
    // 使用第 n+1 号位置作为控制搜索自动结束的 “监视哨” 使用
    S[n+1].key=x;// 将 x 送 n 号位置设置监视哨
    int i=1;
    while(S[i].key!=x)
    {
        i++;// 从前向后顺序搜索
    }
    if(i==n+1)
    {
        return 0;
    }
    else
    {
        return i;
    }
}

# 改进算法 2

image-20251101154857370

“改进算法 2” 是在 “改进算法 1” 的基础上进一步优化：

将哨兵移到 S [0]，不再需要额外空间；

从后向前搜索，在某些使用场景更高效；

依旧保持单条件循环，逻辑简洁无越界。

// 改进算法 2
int Search(Rec S[],Key x,int n)// 基于顺序存储结构的顺序查找算法
{
    // 顺序查找关键码为 x 的数据对象
    // 使用第 0 号位置作为控制搜索自动结束的 “监视哨” 使用
    S[0].key=x;// 将 x 送 0 号位置设置监视哨
    int i=n;
    while(S[i].key!=x)
    {
        i--;// 从后向前顺序搜索
    }
    if(i==0)
    {
        return 0;
    }
    else
    {
        return i;
    }
}

# 3. 基于有序顺序表的顺序查找算法


# 普通实现算法

image-20251101155745568
int Search(Rec S[],Key x,int n)// 有序顺序表的顺序查找算法
{
    // 顺序搜索关键码为 x 的数据对象
    for(int i=1;i<=n;++i)
    {
        if(S[i].key==x)
        {
            return i;// 成功
        }
        else
        {
            if(S[i].key>x)
            {
                break;
            }
        }
    }
    return 0;// 顺序搜索失败，返回失败信息
}

# 二分查找算法 (非递归算法)

int Search_Bin(Rec S[],Key x,int n)// 有序顺序表的顺序查找算法
{
    // 二分查找的非递归算法  S [] 为有序表
    int low=1;
    int high=n;
    int mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(x==S[mid].key)
        {
            return mid;
        }
        else if(x<S[mid].key)
        {
            high=mid-1;
        }
        else
        {
            low=mid+1;
        }
    }
    return 0;
}

# 二分查找算法 (递归算法)

int Search_Bin(Rec S[],Key x,int low,int high)// 有序顺序表的顺序查找算法
{
    // 在主函数 main 中调用该函数时实参为 Search_Bin (S,x,1,n)
    if(low>high)
    {
        return 0;// 查找不成功
    }
    else
    {
        int mid=(low+high)/2;
        if(x==S[mid].key)
        {
            return mid;
        }
        else if(x<S[mid].key)
        {
            return Search_Bin(S,x,low,mid-1);
        }
        else
        {
            return Search_Bin(S,x,mid+1,high);
        }
    }
}

image-20251101162110402

# 4. 索引顺序表

image-20251101164349251
image-20251101162847202
// 索引表的结构
struct indexItem
{
    Key maxKey;// 当前块中最大关键字
    int stadr;// 当前块在顺序表中的起始地址（索引号）
}IndexTable[MaxSize];// 索引表
struct Rec
{
    Key key;
    ...
}Table[n];// 顺序表

# 三、并查集
image-20251101163121461
image-20251101163130761
image-20251101163151211
image-20251101163953423
image-20251101164012900
image-20251101164023050
# 1. 并查集类的描述
// 并查集类的描述
#define MaxSize 100
int parent[MaxSize];// 并查集的父结点数组
int n;// 集合元素个数
// 初始化操作
for(int i=0;i<n;i++)
{
    parent[i]=-1;
}

# 2. 查找算法
// 查找算法
// 实现 find (i) 只需简单地沿着结点 i 的 parent 向上移动，直至到达 parent 值为 - 1 的结点
int SimpleFind(int i)// 找到含元素 i 的树的根
{
    while(parent[i]>=0)
    {
        i=parent[i];
    }
    return i;
}

# 3. 合并操作
image-20251101170326877
// 合并操作
// 这里假设采用令第一棵树为第二棵树的子树的策略
// 用以 i 为根和以 j (i!=j) 为根的两个不相交集合的 并 取代它们
void SimpleUnion(int i,int j)
{
    parent[i]=j;
}

# 四、二叉排序树 (BST)
(二叉搜索树 / 二叉检索树 / 二叉查找树）
image-20251101170911920
image-20251101170938094
# 1. 二叉排序树结点定义
// 二叉排序树也是二叉树，因此，通常取二叉链表作为二叉排序树的存储结构
template<class T>
struct BTreeNode// 结点结构
{
    T data;
    BTreeNode *lchild,*rchild;// 左右孩子结点
};

# 2. 二叉排序树类定义
template<class T>
class BSTree
{
    BTreeNode<T> *root;
    BTreeNode<T> *searchBST(T x,BTreeNode<T> *p);// 递归查找函数
    int insert(T x,BTreeNode<T> *&bst);// 递归插入函数
    int remove(T x,BTreeNode<T> *&p);// 删除函数
public:
    BSTree(BTreeNode<T> *p=0)// 构造函数
    {
        root=p;
    }
    BTreeNode<T> *searchBST(T x);// 查找函数，调用递归查找，供 main 函数调用
    BTreeNode<T> *searchBST1(T x);// 非递归查找函数
    T min();// 获取最小值
    T max();// 获取最大值
    int insert(T x);// 插入函数，其调用递归插入，供 main 函数调用
    int insert1(T x);// 非递归插入函数
    void CreateBST();// 建立二叉排序树
    int remove(T x);// 删除函数
};

# 3. 查找算法
image-20251101195344047
# 递归算法
// 递归算法
//x：要查找的关键字
//p：当前要搜索的子树的根结点指针
template<class T>
BTreeNode<T> *BSTree<T>::searchBST(T x,BTreeNode<T> *p)
{
    //p==nullptr（树空），说明没找到；或者 x==p->data，说明当前结点就是要找的。
    if(!p || (x==p->data))
    {
        return p;
    }
    else if(x<p->data)
    {
        return searchBST(x,p->lchild);// 在左子树中继续查找
    }
    else
    {
        return searchBST(x,p->rchild);// 在右子树中继续查找
    }
}
//public 的 searchBST 是外部调用接口
// 递归查找函数对应的公有函数
template<class T>
BTreeNode<T> *BSTree<T>::searchBST(T x)// 查找函数，调用递归查找，供 main 函数调用
{
    return searchBST(x,root);
}

# 非递归算法
// 非递归算法
template<class T>
BTreeNode<T> *BSTree<T>::searchBST1(T x)
{
    BTreeNode<T> *TT=root;
    while(TT!=0)// 当前结点不为空，就继续查
    {
        if(x==TT->data)
        {
            return TT;
        }
        else if(x<TT->data)
        {
            TT=TT->lchild;// 在左子树中找
        }
        else
        {
            TT=TT->rchild;// 在右子树中找
        }
    }
    return 0;
}

image-20251101204732207
image-20251101204741723
image-20251101204755961
# 3. 插入算法
image-20251101204821056
image-20251101204836927
image-20251101204903037
# 递归算法
// 递归算法
//*&bst 是指向结点指针的引用
template<class T>
int BSTree<T>::insert(T x,BTreeNode<T> *&bst)// 私有函数
{
    BTreeNode<T> *p;
    if(bst==0)
    {
        p=new BTreeNode<T>;
        p->data=x;
        p->lchild=p->rchild=NULL;
        bst=p;
        return 1;// 插入成功
    }
    if(x<bst->data)
    {
        return insert(x,bst->lchild);// 在左子树中插入
    }
    else if(x>bst->data)
    {
        return insert(x,bst->rchild);// 在右子树中插入
    }
    else
    {
        return -1;// 重复值，插入不成功
    }
}
// 调用插入递归函数  插入操作公有函数
template<class T>
int BSTree<T>::insert(T x)
{
    int ret;//return
    ret=insert(x,root);
    if(ret==-1)
    {
        cout <<"HAVE FOUND";
    }
    else
    {
        cout <<"insert ok";
    }
    return ret;
}

# 非递归算法
// 非递归算法
//TT：当前遍历的结点指针，从根结点开始往下找
//f：指向 TT 的父结点，用于在插入时确定新结点应插在左还是右
//p：新建结点指针，在后面创建新结点时使用
template<class T>
int BSTree<T>::insert1(T x)
{
    BTreeNode<T> *TT,*f,*p;
    TT=root;
    f=0;
    while(TT!=0)
    {
        if(x==TT->data)// 重复值，插入不成功
        {
            return -1;
        }
        else if(x<TT->data)
        {
            f=TT;
            TT=TT->lchild;// 在左子树中找
        }
        else
        {
            f=TT;
            TT=TT->rchild;// 在右子树中找
        }
    }
    // 当循环结束时，TT == 0，说明找到了插入位置
    p=new BTreeNode<T>;
    p->data=x;// 新结点生成
    p->lchild=p->rchild=0;
    if(f==0)// 树原来是空的，新结点就是根
    {
        root=p;// 根结点
    }
    else if(x>f->data)
    {
        f->rchild=p;// 作为右子树
    }
    else
    {
        f->lchild=p;// 作为左子树
    }
    return 1;// 插入成功
}

# 4. 建立算法
image-20251101213307767
// 建立算法
template<class T>
void BSTree<T>::CreateBST()
{
    root=0;
    T x;
    cin >>x;
    while(x!=-1)
    {
        insert(x);
        cin >>x;
    }    
}

# 5. 删除算法
image-20251101213457536
image-20251101213517215
image-20251101213532455
image-20251101213552774
image-20251101213848508
找 “前驱结点”
1. 前驱：p 左子树中 最大 的结点（即往左走一次，再一直往右走）
2. 用前驱的值替换 p->data
3. 再从左子树里删掉那个前驱结点

// 递归删除算法
template<class T>
int BSTree<T>::remove(T x,BTreeNode<T> *&p)
{
    if(!p)// 树空或未找到
    {
        return 0;
    }
    if(x<p->data)// 去左子树删
    {
        return remove(x,p->lchild);
    }
    else if(x>p->data)// 去右子树删
    {
        return remove(x,p->rchild);
    }
    else// 找到要删除的结点 p
    {
        BTreeNode<T> *q=p;
        //1. 没有左右子树（叶子结点）
        if(!p->lchild &&  !p->rchild)
        {
            delete p;
            p=nullptr;
        }
        //2. 只有左子树
        else if(p->lchild && !p->rchild)
        {
            p=p->lchild;
            delete q;
        }
        //3. 只有右子树
        else if(!p->lchild && p->rchild)
        {
            p=p->rchild;
            delete q;
        }
        //4. 有左右子树
        else
        {
            // 找左子树中最大的结点 (前驱)
            BTreeNode<T> *s=p->lchild;
            while(s->rchild)
            {
                s=s->rchild;// 找前驱
            }
            p->data=s->data;// 替换，注意建议复制数据
            // 因为 s 是前驱结点，所以是一个叶子结点，或者只有一个左孩子
            remove(p->data,p->lchild);// 删除前驱
        }
        return 1;
    }
}


# 五、二叉平衡树 (AVL)
image-20251102002528290
image-20251102002540963
在 AVL 树（一种自平衡二叉查找树）中，
平衡因子（Balance Factor，简称 BF） 是用于衡量结点 “平衡程度” 的一个值。
🌳 定义：
对于任意一个结点 node ：
BF(node)=左子树的高度−右子树的高度BF(node) = \text{左子树的高度} - \text{右子树的高度}
📘 取值范围：
为了让整棵树保持 “平衡”，AVL 树要求：BF(node)∈{−1,0,+1}BF(node)\in\lbrace -1, 0, +1 \rbrace
也就是说：
  • BF = 0：左右子树高度相等，完全平衡
  • BF = +1：左子树比右子树高 1，稍微左重
  • BF = -1：右子树比左子树高 1，稍微右重
  • |BF| > 1：该结点失衡，需要通过旋转（LL、RR、LR、RL）调整平衡

image-20251102003022376
image-20251102003050142
# 1. 四种失衡情况
LL 型：右旋失衡结点
RR 型：左旋失衡结点
LR 型：左旋失衡结点左孩子，右旋失衡结点
RL 型：右旋失衡结点右孩子，左旋失衡结点

# 2. 插入和调整实例
image-20251114004236530
image-20251114004254063
image-20251114004305509
# 六、2-3 树

image-20251114005035271
# 1. 两种内部结点的含义
（1）2 - 结点（Two-Node）
  • 含有 一个关键字（比如 dataL.key ）
  • 有 两个子树（左子树 LeftChild 、右子树 MiddleChild ）
规则：
LeftChild 的所有 key < dataL.key
MiddleChild 的所有 key > dataL.key
也就是说，它就像普通二叉搜索树：
2-结点
       [dataL]
       /     \
 LeftChild   MiddleChild

（2）3 - 结点（Three-Node）
  • 含有 两个关键字： dataL.key 和 dataR.key
  • 有 三个子树： LeftChild 、 MiddleChild 、 RightChild
并且：
dataL.key < dataR.key
规则：
LeftChild   中所有关键字 < dataL.key
MiddleChild 中所有关键字 > dataL.key 且 < dataR.key
RightChild  中所有关键字 > dataR.key
结构示意：
3-结点
        [ dataL  |  dataR ]
         /       |       \
 LeftChild   MiddleChild  RightChild

# 2. 插入操作
image-20251119144313580 image-20251119144326674 image-20251119144337846
手工方法
特点：
2-3 树的插入操作和二叉树既有相似的地方又有不同的地方。
相似之处在于两者都要先通过搜索，找到插入的位点；
不同之处在于这个插入的位点总是位于叶子结点，而非一个任意结点；另外，2-3 树的插入操作是将插入值 value 直接放进待插入的结点，而不是新建一个结点。
但是，2-3 树存在两种类型的结点（2 - 结点和 3 - 结点），因此我们要分为两种情况讨论：

# 2.1 插入到 2 - 结点
将一个值 value 插入到 2 - 结点的情况很简单，只需要将 value 放入正确的位置使之变为 3 - 结点即可。
例如将 4 插入到下面的树中，将会得到：
image-20251114200823868
# 2.2 插入到 3 - 结点
插入到 3 - 结点的情况会比较麻烦，因为结点已经满了，在这种情况下，2-3 树采用的策略是分裂成两个结点。

分裂：
分裂的过程可以概括为：原结点保留三个值（新来的值以及结点中原有的两个值）中的最小值，新分裂出的结点用来存放最大值，而将中间值向上传递到父结点中。
换句话说就是将中间值插入到父结点中，此时，还需要讨论父结点是 2 - 结点还是 3 - 结点，所以分情况讨论：

  • 情况 1：父结点存在，且为 2 - 结点。
这种情况下只需将中间值插入到父结点即可。
下面中的例子中，如果要在向 2-3 树中插入 1，插入后原结点分裂成两个结点，并将 2 传递到父结点，最后父结点变为 3 - 结点。
image-20251114202030972

  • 情况 2：父结点存在，且为 3 - 结点。
这时父结点也需要分裂，因此分裂后父结点再将其中间值向上传递，整个过程递归地进行直到遇到根结点。例如，我们还是在绿色的 3 - 结点中插入 9，插入后原结点分裂成两个结点，并将 8 传递到父结点中，这时发现父结点也为 3 - 结点，所以父结点的父结点也要分裂，分裂后我们把中间值 6 传递到上一层
image-20260109201843689
# 3. 删除操作
image-20251119144605039 image-20251119144631308 image-20251119144654937 image-20251119144707873 image-20251119144718766 image-20251119144728214 image-20251119144738308
当待删除的值在叶子结点上时，可以分为下面两大类：

# 3.1 叶子结点为 3 - 结点
这种情况最简单，直接删除即可，3 - 结点变为 2 - 结点
image-20251119145440564

# 3.2 叶子结点为 2 - 结点
当叶子结点为 2 - 结点时，需要分别查看兄弟结点和父结点的类型，因此，再将它们分为三种情况：
# 3.2.1 兄弟结点为 3 - 结点
兄弟结点为 3 - 结点。这种情况下，我们需要向兄弟结点借一个最近的值，来补充删除后空的叶子结点。
下面的例子中，如果删除的值为 6，我们需要向兄弟结点借一个值 8，但借来后发现不满足大小关系（7 > 8），所以我们需要再交换一下父结点和叶子结点的值。
image-20251119145705364
# 3.2.2 兄弟结点为 2 - 结点，父结点为 3 - 结点
兄弟结点为 2 - 结点，父结点为 3 - 结点。因为兄弟结点为 2 - 结点，所以就不能向兄弟结点借一个值了，我们转而向父结点借，并与兄弟结点结合，最后父结点从 3 - 结点变成了 2 - 结点。
image-20251119154717786
# 3.2.3 父结点和兄弟结点都为 2 - 结点
父结点和兄弟结点都为 2 - 结点。这种情况是最麻烦的，首先我们要让父结点和兄弟结点合并。例如下方，如要删除 1，则 2 和 3 进行合并。
image-20251119154951240
我们发现原来的父结点内值为空，为了填补这个空结点，我们要再对父结点执行一次删除操作。
注意这里我们仅仅只是调整树的结构，而非删除任何值。
接下来我们查看这个结点的兄弟结点和父结点，如果它的兄弟结点是 3 - 结点，我们就向兄弟结点借一个值来填补这个空值，最后调整结点之间的值使之满足大小关系就好了。
image-20251119155208584

如果父结点是 3 - 结点，那么我们就向其父结点中借一个值来补充这个空值。
image-20251119155335564
假如父结点和兄弟结点都不是 3 - 结点，我们就再次合并父结点和兄弟结点，并把空结点传递到上一层，然后再看前面的情况是否满足（在上一层重新检测这三个情况中属于哪一种），这就变成了一个递归的过程，当这个空结点是这棵 2-3 树的根结点时，我们就删除这个结点，并且它的孩子结点为树的根结点，此时树的高度减 1。
image-20251119155454699

时间复杂度分析
image-20251119163243194

# 七、B 树
image-20251119163729883 image-20251119163819031
image-20251119205942108
这里把外部结点作为叶子结点

image-20251119210934422
注意：根结点最少 2 个分支，1 个元素；除根结点外，最少[m2][\frac{m}{2}] 个分支，[m2]−1[\frac{m}{2}]-1 个元素

# 1. 查找
image-20251119170740597
# 2. 插入
image-20251119170825518
上溢出：中间元素[m2][\frac{m}{2}] 上移，两边分裂

image-20251119170849089 image-20251119170859163 image-20251119170911082 image-20251119170922879
# 3. 删除

image-20251120095303704
1. 删除 45：45 是非叶子结点，这里利用直接后继替换删除结点
image-20251120140122852

2. 删除 68：删除 68 后，出现下溢出现象，因此要向兄弟结点借一个元素；首先判断兄弟结点是否够借（下面例子中可向左兄弟或右兄弟借一个元素），以向右兄弟借为例，向右兄弟借一个元素，同时为了保证 B 树的有序性质，因此需要同时调整其父结点
image-20251120144148145

3. 删除 86：删除 86 后，出现下溢出现象，并且兄弟结点不满足能借出的条件；因此选择与兄弟结点进行合并（与左兄弟结点或右兄弟结点均可），这里以和右兄弟结点合并为例，此时又要考虑到父结点，因此合并操作为：父结点下移到左，然后进行右并（和左兄弟结点合并的操作也是父结点下移到左，进行右并）
image-20251120145633143

4. 删除 30：用直接后继替换 30 后，41 出现下溢出，且左右兄弟结点均不够借，因此父结点下移到左，然后右并；之后 40 出现下溢出，兄弟结点够借，因此父结点下移，兄弟结点元素 51 上移；最后调整子树分支
image-20251120155909196

5. 删除 57
image-20251120160506007

6. 删除 53：删除 53 后，60 下溢出，且兄弟结点不可借，则与兄弟结点进行合并；之后 76 出现下溢出，且兄弟结点不可借，则与兄弟结点进行合并
image-20251120163742783
# 八、哈希表
image-20251120192119371 image-20251120192150325
# 1. 哈希函数的构造方法
# 1.1 直接定址法
image-20251120192306736
# 1.2 除留余数法
image-20251120192334576 image-20251120192447021
# 1.3 数字分析法
image-20251120192551751 image-20251120192600238
# 1.4 折叠法
image-20251120192610531 image-20251120192619024
# 1.5 平方取中法
image-20251120192629466
# 1.6 随机数法
image-20251120192639342
# 2. 处理冲突方法
image-20251120192832578
# 2.1 开放定址法
image-20251120192841422 image-20251120192848481 image-20251120192906285
# 2.2 链地址法
image-20251120192916833
# 存储结构
// 哈希表最大容量
#define MaxSize 100
// 链表节点结构（用于链地址法存储冲突元素）
struct LinkNode
{
    int data;       // 存储关键字
    LinkNode *link; // 指向下一个冲突节点的指针
};

# 插入算法
// 哈希表插入算法（头插法）
bool InsertHash(int key) 
{
    // 1. 计算哈希地址
    int y = H(key);
    
    // 2. 创建新节点
    LinkNode *p = new LinkNode;
    p->data = key;
    p->link = nullptr;
    
    // 3. 头插法插入到对应哈希桶的链表头部
    p->link = HT[y]; // 新节点指向原链表头
    HT[y] = p;       // 更新链表头为新节点
    
    return true; // 插入成功
}

# 查找算法
image-20251120204905095
// 哈希表查找算法
int SearchHash(int key) 
{
    // 1. 计算哈希地址
    int y = H(key);
    
    // 2. 遍历对应哈希桶的链表
    LinkNode *p = HT[y];
    while (p != nullptr) 
    {
        if (p->data == key) 
        {
            return 1; // 查找成功，返回 1
        }
        p = p->link; // 遍历下一个节点
    }
    
    return -1; // 查找失败，返回 - 1
}