Data-Structure

Chapter2 线性表

线性结构简介

• 线性表：操作不限表
• 栈：时间有序表，先进后出表
• 队列：时间有序表，先进先出表

线性表定义

线性表是N个具有相同特征的节点$A_0,A_1,\cdots,A_{N-1}$构成的有穷有序序列

线性表的基本操作

• 创建 create()
• 清除 clear()
• 求线性表的长度 length()
• 删除 remove(i)
• 搜索 search(x)
• 访问 visit(i)
• 遍历 traverse()

线性表的抽象类

抽象类：如果一个类中至少有一个纯虚函数，则该类为抽象类
Tips. 一些好习惯：

• 不需修改的形参尽量使用const &（尽量使用引用传参）
• 不会进行修改的引用，请加const
• 类的成员函数如果不对类本身的成员变量进行修改，请将声明为类的const成员函数（原因：常对象不能调用非const成员函数，可以调用const成员函数）

template <class elemType>
class list
{ public:
     virtual void clear() = 0;
     virtual int length() const = 0;
     virtual void insert(int i, const elemType &x) = 0;
     virtual void remove(int i) = 0; 
     virtual int search(const elemType &x) const = 0 ;
     virtual elemType visit(int i) const = 0;
     virtual void traverse() const = 0
     virtual ~list() {};
};//抽象类无构造函数

线性表顺序实现

顺序表的存储实现

• 利用数组，进行顺序存放，数据连续分布
• 需要预先申请一块比存储的数据稍大的内存空间（new一个数组）
• 使用一个指针（elemType * data）存储数据的起始位置，因为数组的大小需要动态修改
• 需要两个额外的量存储目前申请的内存空间数组项数int maxSize和当前存储的数据项数int currentLength

顺序表类的定义

template <class elemType>
class seqList: public list<elemType>
{ private:
    elemType *data;
    int currentLength;
    int maxSize;
    void doubleSpace();
    
  public:
    seqList(int initSize = 10);
    ~seqList()  {delete [] data;}
    void clear()  {currentLength = 0;}
    int length() const  {return currentLength;}
    void insert(int i, const elemType &x);
    void remove(int i); 
    int search(const elemType &x) const ;
    elemType visit(int i) const;
    void traverse() const ;

};

构造函数

template <class elemType>
seqList<elemType>::seqList(int initSize)
{
	data = new elemType[initSize];
	maxSize = initSize;
	currentLength = 0;
}

时间复杂度为$O(1)$

析构函数

顺序表的运算实现

length()

只需要返回currentlength的值

int length() const  {return currentLength;}

visit(i)

返回data[i]的值

elemType visit(int i) const 
{
	return data[i];
	if (i < 0 || i >= currentLength) throw OutOfBound();
}

注意：为增强程序健壮性，加入越界的判断，若越界则抛出错误

如果要抛出错误，可以借助C++的异常处理功能，建一个OutOfBound类来提供越界异常处理的功能，具体实现如下：

class OutOfBound : public std::exception {
public:
    const char* what() const noexcept override {
        return "Index out of bound";
    }
};

clear()

只要将currentlength置为0即可

void clear()  {currentLength = 0;}

上述三个算法，时间复杂度均为$O(1)$

traverse()

template<class elemType>
void seqList<elemType>::traverse() const {
    std::cout << std::endl;
    for (int i = 0; i < currentLength; ++i) {
        std::cout << data[i] << ' ';
    }
}

遍历的时间复杂度为$O(n)$

search()

template <class elemType>
int seqList<elemType>::search(const elemType &x) const
{
   int i;
   for (i = 0; i < currentLength && data[i] != x; ++i);
   if (i == currentLength) return -1;
   else return i;
}

搜索最优时间复杂度$O(1)$，最坏时间复杂度$O(n)$，平均时间复杂度$O(n)$

insert(i,elem)

template<class elemType>
void seqList<elemType>::insert(int i, const elemType& x) {
    if (i < 0 || i > currentLength)
        throw OutOfBound();
    if (currentLength == maxSize)
        doubleSpace();
    for (int j = currentLength; j > i; --j) {
        data[j] = data[j - 1];
    }
    data[i] = x;
    ++currentLength;
}

• 思路：从后向前遍历，直到要插入元素的位置$i$，从而要插入的元素在越靠后的位置，所需时间越少

• 要检查是否超限，超限就得分配新空间

• 此处也加入了对于越界的判断，详情见前面，不再重复叙述

• 插入操作最优时间复杂度$O(1)$，最坏时间复杂度$O(n)$，平均时间复杂度$O(n)$

• 别忘了改currentLength！（虽然这是个常识）

remove(i)

template<class elemType>
void seqList<elemType>::remove(int i) {
    for (int j = i; j < currentLength - 1; ++j) {
        data[j] = data[j + 1];
    }
    --currentLength;
}

• 思路：先找到要插入元素的位置$i$，然后从前向后遍历，直到最后
• 搜索最优时间复杂度$O(1)$，最坏时间复杂度$O(n)$，平均时间复杂度$O(n)$

空间分配：doubleSpace()

• 当数组空间不够时，调用doubleSpace扩容
• doubleSpace操作按一定的比例扩大数组的空间，常用的比例是扩大一倍（当然也可以设置成其他的）。
• 数组空间在内存中必须是连续的，因此，扩大数组空间的操作如下：
  • 重新申请一个更大规模的动态数组
  • 将新数组作为存储线性表的存储区
  • 将原有数组的内容拷贝到新数组中
  • 释放原有数组空间
• 时间复杂度$O(n)$

template<class elemType>
void seqList<elemType>::doubleSpace() {
    elemType* tmp = data;
    maxSize *= 2;
    data = new elemType[maxSize];
    for (int i = 0; i < currentLength; ++i) {
        data[i] = tmp[i];
    }
    delete[] tmp;
}

顺序表总结

• 需要连续的存储空间。直观来讲，就是手搓一个动态数组

• 由于逻辑次序和物理次序的一致性使得定位访问的性能很好

• 由于要保持逻辑次序和物理次序的一致性，顺序表在插入删除时需要移动大量的数据，性能不太理想；

• 顺序表比较适合静态的、经常做定位访问的线性表。

线性表链接实现

单链表

单链表的存储实现

• 定义：每个结点附加了一个指针字段，如next，该指针指向它的直接后继结点，最后一个结点的next字段为空。

• 头结点：为了消除特殊情况（边界效应），通常在表头额外增加一个相同类型的特殊结点，称之为头结点。

  • 头结点不是线性表的组成部分
  • 添加头结点是为了使在表头位置上进行插入和删除和在其它结点位置上进行这些操作完全一致，从而简化插入和删除算法。简言之，头结点保证了操作的一致性。
  

• 链表中的节点包含两部分：数据字段和指针字段。数据字段是单链表中要存储的数据，指针字段存放后继结点的地址值。

• 链表的操作是通过对节点进行操作实现的，因此应该把节点定义成一个结构体（struct）。

• 一般情况下，结点类型是链表专用的，建议设置为内嵌类/结构体。

单链表类的定义

template<class elemType>
class sLinkList: public list<elemType> {
private:
    struct node {
        elemType data;
        node* next;

        node(const elemType& x, node* n = NULL) {
            data = x;
            next = n;
        }
        node(): next(NULL) {}
        ~node() {}
    };
    node* head; //头指针
    int currentLength; //表长 
    node* move(int i) const; //返回第i个结点的地址

public:
    sLinkList();
    ~sLinkList() {
        clear();
        delete head;
    }
    void clear();
    int length() const {
        return currentLength;
    }
    void insert(int i, const elemType& x);
    void remove(int i);
    int search(const elemType& x) const;
    elemType visit(int i) const;
    void traverse() const;
};

构造函数

template <class elemType>
sLinkList<elemType>::sLinkList() 
{ 
    head = new node;
    currentLength = 0;
}

析构函数：清除单链表clear()

• 把单链表变成一个空表
• 回收所有结点的空间
• 时间复杂度为$O(n)$

template<class elemType>
void sLinkList<elemType>::clear() {
    node *p = head->next, *q;
    head->next = NULL;
    while (p != NULL) { //删除链表中的所有结点
        q = p->next;
        delete p;
        p = q;
    }
    currentLength = 0;
}

单链表的运算实现

返回第i个元素的指针：move(i)

• 应该定义为private函数
• 时间复杂度$O(n)$

template<class elemType>
struct sLinkList<elemType>::node* sLinkList<elemType>::move(int i) const {
    node* p = head;
    while (i-- >= 0 && p)
        p = p->next;
    return p;
}

插入元素：insert(i,x)

• 让指针p指向第i-1个元素

• 执行插入操作：

  1. new一个节点

  2. 将新数据和下一节点的指针填入新节点

  3. 将新节点链入队伍

template<class elemType>
void sLinkList<elemType>::insert(int i, const elemType& x) {
    node* pos;
    if (i < 0)
        return;
    pos = move(i - 1);
    if (pos) {
        pos->next = new node(x, pos->next);
        ++currentLength;
    }
}

删除第i个元素：remove(i)

• 找到被删节点前一节点pos
• 让delp指向被删节点
• 将delp的后继节点指针赋值给pos的后继节点指针
• 释放被删节点空间（别忘！）

template<class elemType>
void sLinkList<elemType>::remove(int i) {
    node *pos, *delp;
    if (i < 0)
        return;
    pos = move(i - 1);
    if (!pos || !pos->next)
        return;
    delp = pos->next;
    pos->next = delp->next;
    delete delp;
    --currentLength;
}

搜索某个元素：search(x)

思路：从头指针的后继结点开始往后检查链表的结点直到找到x或查找到表尾

千万注意：while条件判断括号里的两个式子不能对调！！！！

template<class elemType>
int sLinkList<elemType>::search(const elemType& x) const {
    node* p = head->next;
    int i = 0;
    while (p != NULL && p->data != x) {
        p = p->next;
        ++i;
    }
    if (p == NULL)
        return -1;
    else
        return i;
}

访问第i个元素：visit(i)

• 找到第i个节点
• 返回节点的数据部分
• 最好处理一下越界访问的异常情况（加个if判断move(i)返回的是否是空指针就行）

template<class elemType>
elemType sLinkList<elemType>::visit(int i) const {
    return move(i)->data;
}

遍历运算：traverse()

template<class elemType>
void sLinkList<elemType>::traverse() const {
    node* p = head->next;
    std::cout << std::endl;
    while (p != NULL) {
        std::cout << p->data << "  ";
        p = p->next;
    }
    std::cout << std::endl;
}

双链表

双链表的存储实现

• 每个结点附加了两个指针字段，如prev和next
  • prev字段给出直接前驱结点的地址
  • next字段给出直接后继结点的地址
• 为了保证表头、表尾插入删除操作的一致性，通常为双链表设一头结点，设一尾节点
  • 结点中prev字段为空，它的next字段给出线性表中的首结点的地址
  • 尾结点中next字段为空，它的prev字段给出线性表中最后一个结点的地址

循环链表

单循环链表

• 一般的单循环链表不带头节点，使用一个头指针即可

双循环链表

• 头结点中prev字段给出尾结点的地址，尾结点中next字段给出头结点的地址
• 一般也不设头尾结点，有一个头指针就可以

线性表总结

分析	顺序实现	链接实现
连续空间	√	×
空间浪费	√	指针
清除	O(1)	O(N)
插入	O(N)	O(N)
找到位置后插入	O(N)	O(1)
删除	O(N)	O(N)
找到位置后删除	O(N)	O(1)
访问	O(1)	O(N)
查找	O(N)	O(N)
遍历	O(N)	O(N)

Chapter3 栈

栈的定义

• 后进先出(LIFO, Last In First Out)表
• 先进后出(FILO, First In Last Out)表
• 最先(晚)到达栈的结点将最晚(先)被删除
• 只能在一端进行插入和删除的线性表

栈的运算

• 创建一个栈create()：创建一个空的栈；
• 进栈push(x)：将x插入栈中，使之成为栈顶元素；
• 出栈pop()：删除栈顶元素并返回栈顶元素值；
• 读栈顶元素top()：返回栈顶元素值但不删除栈顶元素；
• 判栈空isEmpty()：若栈为空，返回true，否则返回false。

template <class elemType>
class stack
 { 
    public: 
	  virtual bool isEmpty() const = 0; 
	  virtual void push(const elemType &x) = 0; 
	  virtual elemType  pop() = 0;              
      virtual elemType  top() const = 0;        
	  virtual ~stack() {}
 }; 

栈的顺序实现

• 用连续的空间存储栈中的结点，即数组
• 进栈和出栈总是在栈顶一端进行，不会引起类似顺序表中的大量数据的移动。用数组的后端表示栈顶。

栈的链接实现

• 栈的操作都是在栈顶进行的，因此不需要双链表，用单链表就足够了，而且不需要头结点
• 对栈来讲，只需要考虑栈顶元素的插入删除。从栈的基本运算的实现方便性考虑，可将单链表的头指针指向栈顶。

栈的应用

递归的时间复杂度计算

数学归纳法

1. 找到问题中含有的递推关系$T(n) = g(T(n-1))$
2. 找到初始条件$T(1)$
3. 使用数学归纳法进行递推转通项，即可直接写出$T(n)$，自然也就很容易写出$O(n)$

递归方程+主定理

主定理 设$a \geq 1$和$b \geq 1$为常数，设$f(n)$为一函数，则递归方程$T(n) = a T(\dfrac{n}{b}) + f(n), n>1$的解是

1. 若$f(n) < O(n^{\log_b{a}})$，则$T(n) = O(n^{\log_b{a}})$
2. 若$f(n) = O(n^{\log_b{a}})$，则$T(n) = O(n^{\log_b{a}} \log_2 n)$
3. 若$f(n) > O(n^{\log_b{a}})$，则$T(n) = O(f(n))$

生成函数法

设$u_0,u_1,u_2,\cdots,u_n,\cdots$是一无穷序列，称形式幂级数

$$G(t) = \sum_{i \geq 0} u_i t^i$$

为其生成函数

利用生成函数求得序列通项的步骤：

1. 求出生成函数$G(t)$的有限形式：按递归关系消去无限的部分，留下有限部分
2. 把$G(t)$​的有限形式展开成t的幂级数形式，求得通项

递归函数的非递归实现

括号配对

简单的计算器

中缀式和后缀式

对于一个表达式a + b

• 前缀式：+ab

• 中缀式：a+b

• 后缀式：ab+

后缀表达式计算

1. 初始化一个栈。
2. 依次读入后缀式的操作数和运算符。
   1. 若读到的是操作数，则将其进栈。
   2. 若读到的是运算符，则将栈顶的两个操作数出栈，后弹出的操作数为被操作数，先弹出的为操作数，将得到的操作数完成运算符所规定的运算，并将结果进栈。
3. 回到2的读入操作，继续。
4. 当栈中只剩有一个操作数时，弹出该操作数，它就是表达式的值。

中缀转后缀

1. 若读入的是操作数，立即输出。
2. 若读入的是闭括号，则将栈中的运算符依次出栈，并将其放在操作数序列之后。出栈操作一直进行到遇到相应的开括号为止。将开括号出栈。
3. 若读入的是开括号，则进栈。
4. 若读入的是运算符，如果栈顶运算符优先级高或相等，则栈顶运算符出栈；出栈操作一直要进行到栈顶运算符优先级低为止，然后将新读入的运算符进栈保存。
5. 在读入操作结束时，将栈中所有的剩余运算符依次出栈，并放在操作数序列之后，直至栈空为止。

中缀表达式直接计算

建两个栈，一个运算符栈，一个运算数栈

把中缀转后缀中的运算符栈出栈操作，改成直接对运算数栈栈顶的两个操作数出栈，完成运算符所规定的运算，然后再将结果压入运算数栈，就可以实现直接计算中缀表达式了。具体例子如下：

Chapter4 队列

• 先进先出(FIFO:First In First Out)表
• 到达越早的结点，离开的时间越早
• 只能在头端进行删除（队首），在尾端进行插入（队尾）

队列的基本操作

• 创建一个队列create()：创建一个空的队列；
• 入队enQueue(x)：将x插入队尾，使之成为队尾元素；
• 出队deQueue()：删除队头元素并返回队头元素值；
• 读队头元素getHead()：返回队头元素的值；
• 判队列空isEmpty()：若队列为空，返回true，否则返回false。

队列的抽象类

template <class elemType>
class queue
 { public: 
        virtual bool isEmpty() = 0;                  //判队空
        virtual void enQueue(const elemType &x) = 0; //进队
        virtual elemType  deQueue() = 0;             //出队
	    virtual elemType getHead() = 0;              //读队头元素
        virtual ~queue() {}                          //虚析构函数
 };

队列的顺序存储

• 使用数组存储队列中的元素
• 队列中的结点个数最多为MaxSize个
• 元素下标的范围从0到MaxSize-1
• 顺序队列的三种组织方式

  • 队头位置固定（不用）

    

  • 队头位置不固定（不用）

  • 循环队列（常用）

循环队列

入队操作

rear = (rear + 1) % maxSize
elem[rear] = x

出队操作

front = (front + 1) % maxSize

（关键）如何判空和满？

如果直接使用循环数列，会出现空和满时都是 rear == front的情况，无法区分

所以需要解决方案：

一种解决方案是："牺牲"一个单元，规定front指向的单元不能存储队列元素，只起到标志作用

这样，队列为空的条件为

rear == front

队列为满的条件为

(rear + 1) % maxSize == front

当然，这并不是唯一的解决方案，也有很多其他方案。

比如，增加一个变量，记录currentLength，然后结合currentLength是否为0判断当然也是可以的

循环队列类的定义

template <class elemType>
class seqQueue: public queue<elemType>
{
private:
     elemType *elem;
	 int maxSize;
	 int front, rear;	  
	 void doubleSpace();
public:
   seqQueue(int size = 10)；
   ~seqQueue() ；
   bool isEmpty() ；
   void enQueue(const elemType &x) ;
   elemType deQueue();   
   elemType getHead()；
}; 

构造/析构

构造：申请一块空间，首地址存入elem。数组规模保存在MaxSize中，front和rear置成0。

template <class elemType>
  seqQueue<elemType>::seqQueue(int size)
{ 
      elem = new elemType[size];
      maxSize = size; 
      front = rear = 0;
} 

析构：删除数组

template <class elemType>
seqQueue<elemType>::~seqQueue()
{
    delete [] elem;
}

入队：enQueue()

• 首先要判断数组是否已放满，需要时扩大数组空间。
• 将元素放入后面的空位，队尾向后移

template <class elemType>
void seqQueue<elemType>::enQueue
                       (const elemType &x)
{ 
    if ((rear + 1) % maxSize == front)
                doubleSpace();
    rear = (rear + 1) % maxSize;
    elem[rear] = x;
}

doubleSpace()

template <class elemType>
void seqQueue<elemType>::doubleSpace()
{    elemType *tmp =elem;
     elem = new elemType[2 * maxSize];
     for (int i = 1; i < maxSize; ++i)
	  elem[i] = tmp[(front + i) % maxSize];
	 
     front = 0; rear = maxSize - 1;
     maxSize *= 2;
     delete tmp;
}

deQueue()

• 将front往后移一个位置
• 返回elem[front]的内容。

template <class elemType>
elemType seqQueue<elemType>::deQueue()
{
     front = (front + 1) % maxSize;
     return elem[front];
}

getHead()

template <class elemType>
elemType seqQueue<elemType>::getHead() const
{ 
     return elem[(front + 1) % maxSize];
}

isEmpty()

• 前面已经分析过队列判空条件

template <class elemType>
bool seqQueue<elemType>::isEmpty() const 
{
      return front == rear;
}

队列的链接实现

• 由于队列的操作是在队列的两端进行的，不会对队列中的其他元素进行操作，用单链表就足够了。
• 队列要对表的两端作操作，为方便两端操作，我们可以采用空间换时间的方法，同时记住头尾结点的位置。
• 综上，使用无头结点，有头指针和尾指针的单链表

队尾和队首的选择

• 队尾指出的是插入位置，对单链表来说，有了尾指针，在表头插入和表尾插入一样简单。
• 队头指出的是删除位置，删除表头元素很简单，但删除表尾元素必须知道它前一元素的存储地址，因此在表尾删除要花O（N）的时间。
• 为此可以将单链表的表头作为队头，单链表的表尾作为队尾，插入和删除均为O(1)

链接队列类的设计

• 数据成员：
  • 头尾指针
  • 头尾指针的类型：指向结点（数据，下一结点地址）
• 成员函数：
  • 构造和析构函数
  • 抽象类规定的功能

构造函数

template <class elemType>
linkQueue<elemType>::linkQueue() 
{
   front = rear = NULL; 
}

入队enQueue()

• 首先申请一个结点存储 x；
• 将结点x作为单链表的表尾，即rear指向的结点的指针部分指向结点x，将结点x作为尾结点。
• 注意，enQueue操作有个特殊情况，就是队列为空的情况。此时，我们只需要申请一个存放x的结点，让front和rear同时指向这个结点。

template <class elemType>
void linkQueue<elemType>::enQueue(const elemType &x) 
{
    if (rear == NULL)
  	  front = rear = new node(x);
    else 
	  rear = rear->next = new node(x);
}

出队deQueue()

• 返回front指向的结点的值并删除该结点。
• 删除表头结点需要先将表头结点从链表中摘下，然后释放表头结点的空间。
• 注意，deQueue操作有一个特殊情况，即如果执行deQueue操作时队列中只有一个元素，经过deQueue操作，队列为空，此时必须将front和rear同时置成NULL。

template <class elemType>
elemType linkQueue<elemType>::deQueue()
{
    node *tmp = front;
    if (front) {    
    	elemType value = front->data;
    	front = front->next; 
    	if (front == NULL) rear = NULL;      
    	delete tmp;
    	return value;
    }
}

讨论

如果链接实现想只用一个指示器

• 采用（单）循环链表即可
• 此处以链表头为队头，以链表尾为队尾
• 那么就可以不用同时使用头尾指针，只需要保留尾指针就行

如果顺序实现想只用一个指示器且不牺牲空间

• 增加属性队列长度length
  • rear=front+length
• 判断空与满不再需要牺牲一个空间

队列的应用

车厢重排问题

一列货运列车共有n节车厢，重新排列这些车厢，将第n节车厢放在最后，第1节车厢放在最前面。

解决这个问题的方法记住以下几个规则就行：

• 对于每一个入轨上的车进行处理
  • 如果有队尾编号小于该车编号的轨道，从这些轨道中选队尾编号最大的那一个，把车放进去
  • 如果没有队尾编号小于该车编号的轨道，那么就从空轨道中新建一个轨道来放这辆车
  • 如果既没有这样的轨道，也没有空轨道了，那么该问题无法解决
• 处理完一辆入轨的车后，遍历所有的轨道（队列），比较队首车的编号和出轨上最后一辆车（没有车的话就是0）的编号，如果首车编号恰好比出轨上最后一辆车的编号大1，则可以将该车出轨
  • 如果有车成功出轨，那么再进行一轮遍历，知道进行一轮遍历后没有任何车出轨为止
• 以上操作交替进行

Chapter 5 树

树状结构

• 非线性结构
• 层次和从属关系
• 树（第五章）和优先级队列（第六章）

树的定义

树的递归定义

树是n个集合的有限集合T，它或者是空集，或者满足：

1. 有一个被称为根(root)的节点
2. 其余的节点可以分为m个互不相交的子集$T_1,T_2 \cdots T_n$，其中每个子集也是一棵树，称为子树(subtree)

树的术语

• 根节点，叶节点（末端节点，无分叉），内部节点
• 节点的度和树的度
  • 节点的度：一个节点的直接后继的数目
  • 树的度：树中所有节点的度的最大值
• 逻辑关系：子节点，父节点，兄弟节点，祖先节点，子孙节点
• 结点所处层次
• 树的高度
• 有序树和无序树
  • 有序树：将一棵树的节点看成自左向右有序
  • 无序树：无序，节点顺序无关
• 森林：M棵互不相交的树的集合称为森林

树的运算

• 建树
• 清空
• 判空
• 树节点
• 找父节点
• 找字节点
• 删除
• 遍历

树的抽象类

二叉树

二叉树的定义

二叉树或是空集，或由一个根节点和两个左右子树组成，而其左右子树又都是二叉树。

• 二叉树是有序树，必须严格区分左右子树。

满二叉树

如果一棵二叉树中的任意一层的结点个数都达到了最大值，那么这棵树为满二叉树

一个$k$层的满二叉树，具有$2^k -1$个节点

完全二叉树

最底层可以不满，其他层都满，且最底层从左到右依次存放

完全二叉树相当于满二叉树最底层自右向左去掉若干个节点

二叉树的性质

• 具有$n$个节点的完全二叉树的高度$k$为

$$k = [\log_2{n}] + 1$$

• 对于完全二叉树，（假设起始编号为0）节点i的左子树节点编号为$2i$，右子树节点编号为$2i+1$
• 对于完全二叉树，（假设其实编号为0）节点$i$的父节点编号为$[\dfrac{i}{2}]$
• 对于一棵非空二叉树，如果叶节点数为$n_0$，度数为2的节点为$n_2$，则有$n_0 = n_2 + 1$

证明：连接数从发出者来说，可以写成$2n_2+n_1$，从接收者来说，可以写成$n_0 + n_1 + n_2 -1$

$$2n_2+n_1 = n_0 + n_1 + n_2 -1 \implies n_0 = n_2 + 1$$

二叉树的基本运算

• 建树create()
• 清空clear()
• 判空IsEmpty()
• 找根节点root()
• 找父节点parent()
• 找左孩子lchild()
• 找右孩子rchile()
• 删除左子树delLeft()
• 删除右子树delRight()
• 遍历traverse()

二叉树的遍历

• 二叉树是有分叉的，因此在分叉处必须确定下一个要访问的节点：是根节点，左节点还是右节点
• 据此，有三种遍历方法：前序，中序，后序
• 还有层次遍历方法

前序遍历

• 访问根节点
• 如果左子树非空，前序遍历左子树
• 如果右子树非空，前序遍历右子树

中序遍历

• 如果左子树非空，中序遍历左子树
• 访问根节点
• 如果右子树非空，中序遍历右子树

后序遍历

• 如果左子树非空，后序遍历左子树
• 如果右子树非空，后序遍历右子树
• 访问根节点

层次遍历

• 从上到下按层遍历

例子

中序恰好为投影序

从遍历结果确定二叉树

前序+中序 可唯一确定一棵二叉树

• 先用前序确定当前所在树的根
• 用中序确定哪些节点在左子树，哪些在右子树
• 对左子树，右子树分别重复上述操作（递归），直到确定所有节点

后序+中序 可唯一确定一棵二叉树

前序+后序 无法确定

反例：

前序+层次 无法确定

中序+层次 可以

后序+层次 无法确定

二叉树实现

二叉树的抽象类

template<class T>
class bTree {
public:
    virtual void clear() = 0;
    virtual bool isEmpty() const = 0;
    virtual T Root(T flag) const = 0;
    virtual T parent(const T &x,  T flag) const = 0; 
    virtual T lchild (const T &x, T flag) const = 0;
    virtual T rchild (const T &x, T flag) const = 0;
    virtual void delLeft(const T &x) = 0;
    virtual void delRight(const T &x) = 0;
    virtual void preOrder() const = 0;
    virtual void midOrder() const = 0;
    virtual void postOrder() const= 0;
    virtual void levelOrder() const = 0;
};

二叉树的顺序存储

对于完全二叉树而言，可以根据编号性质确定父子关系

对于普通二叉树，修补成完全二叉树进行存储

• 顺序存储适用于完全二叉树或接近于完全二叉树形状的情况
• 最好是形状静态（操作过程中树的结构不会有大的变化）的情况
• 如果形状与完全二叉树相差太多，会有很多空间浪费，树的结构变化会有较大开销

二叉树的链接存储

标准形式（二叉列表）：data数据字段，left左节点指针，right右节点指针

广义标准形式/扩展形式（三叉列表）：二叉列表+一个parent父节点指针

二叉树链接存储时属性为：root根节点指针

二叉树类的定义

template<class T>
class binaryTree : public bTree<T> {
 	friend void printTree(const binaryTree &t, T flag);
private:
    struct Node {                          //二叉树的结点类
        Node  *left , *right ;   
        T data;   
        Node() : left(NULL), right(NULL) {}
        Node(T item, Node *L = NULL, Node * R =NULL ):  data(item), left(L), right(R) {}
        ~Node() {} 
    };
    Node *root; 
public:
    binaryTree() : root(NULL) {}//创建空树
    binaryTree(T x) { root = new Node(x); }//创建只有根节点的树
    ~binaryTree();
    void clear() ;
    bool isEmpty() const;
    T Root(T flag) const;
    T lchild(const T &x, T flag) const;
    T rchild(const T &x, T flag) const; 
    void delLeft(const T &x) ;
    void delRight(const T &x);
    void preOrder() const;
    void midOrder() const;
    void postOrder() const;
    void levelOrder() const;
    void createTree(T flag);//创建树
    T parent(const T &x, T flag) const { return flag; }
private:
    Node *find(const T &x, Node *t ) const;
    void clear(Node *&t);
    void preOrder(Node *t)  const;
    void midOrder(Node *t) const;
    void postOrder(Node *t)  const;
}; 

注意：
前序，中序，后序遍历在private函数中进行具体实现，然后进行用一个public函数包装private函数

二叉树的递归实现

简单的基本运算：isEmpty()，Root()

template<class T>
bool binaryTree<T>::isEmpty() const {
    return root == NULL;
}

template<class T>
T binaryTree<T>::Root(T flag) const {
    if (root == NULL)
        return flag;
    else
        return root->data;
}

前序遍历：preOrder()

思路：（记得判空）如果输入的节点指针为空，直接返回

然后就是正常的前序遍历思路：

1. 先访问该节点自身的data
2. 访问左子树
3. 访问右子树

中序遍历，后续遍历是类似的，就不赘述了

template<class T>
void binaryTree<T>::preOrder(binaryTree<T>::Node *t)  const
{   
    if (t == NULL) return;
    cout << t->data << ' ';
    preOrder(t->left);
    preOrder(t->right);
}
 
template<class T>
void binaryTree<T>::preOrder()  const
{   
    cout << "\n前序遍历：";
    preOrder(root);
}

中序遍历：midOrder()

template<class T>
void binaryTree<T>::midOrder(binaryTree<T>::Node* t) const {
    if (t == NULL)
        return;
    midOrder(t->left);
    cout << t->data << ' ';
    midOrder(t->right);
}

template<class T>
void binaryTree<T>::midOrder() const {
    cout << "\n中序遍历：";
    midOrder(root);
}

后续遍历：postOrder()

template<class T>
void binaryTree<T>::postOrder(binaryTree<T>::Node* t) const {
    if (t == NULL)
        return;
    postOrder(t->left);
    postOrder(t->right);
    cout << t->data << ' ';
}
template<class T>
void binaryTree<T>::postOrder() const {
    cout << "\n后序遍历：";
    postOrder(root);
}

练习：节点个数size()

template<class T>
int size(Node * t) const
{
    if(t == NULL) return 0;
    return size(t->left) + size(t->right) + 1;
}

template<class T>
int size() const
{
    return size(root);
}

树的高度height()

template<class T>
int binaryTree<T>::height(binaryTree<T>::Node *t)  const
{	   
    if (t == NULL) return 0;
    int lt=height(t->left);
    int rt=height(t->right);
    return 1+((lt>rt)?lt:rt);			  
}			  
 
template<class T>
int binaryTree<T>::height()  const
{   
    return height(root);
}

清空树clear()

template<class T>
void binaryTree<T>::clear(binaryTree<T>::Node *&t)
{
    if (t == NULL)  return;
    clear(t->left);
    clear(t->right);
    delete t;
    t = NULL;
}

template<class T>
void binaryTree<T>::clear()
{
    clear(root);
} 

析构

template <class T>
binaryTree<T>::~binaryTree()
{
    clear(root);
}

层次遍历

• 利用队列
• 步骤：若队列非空，一直循环
  • pop取出队首节点
  • 访问该节点自身数据
  • 若左子树非空，左子树入队
  • 若右子树非空，右子树入队

template<class T>
void binaryTree<T>::levelOrder() const
{
    linkQueue< Node * > que;
    Node *tmp; 
    cout << "\n层次遍历：";
    que.enQueue(root);	 
    while (!que.isEmpty()) {
        tmp = que.deQueue();
        cout << tmp->data << ' ';
        if (tmp->left) que.enQueue(tmp->left);
        if (tmp->right) que.enQueue(tmp->right);
    }
}

遍历查找find(x)

template <class T>
struct binaryTree<T>::Node *binaryTree<T>::
       find(const T &x, binaryTree<T>::Node *t) const
{
    Node *tmp;
    if (t == NULL) return NULL;
    if (t->data == x) return t;
    if (tmp = find(x, t->left) ) return tmp;
    else return find(x, t->right);
}

需要使用find()的一些基本操作

delLeft(), delRight(), lchild(x), rchild(x)

template<class T>
void binaryTree<T>::delLeft(const T& x) {
    Node* tmp = find(x, root);
    if (tmp == NULL)
        return;
    clear(tmp->left);
}

template<class T>
void binaryTree<T>::delRight(const T& x) {
    Node* tmp = find(x, root);
    if (tmp == NULL)
        return;
    clear(tmp->right);
}

template<class T>
T binaryTree<T>::lchild(const T& x, T flag) const {
    Node* tmp = find(x, root);
    if (tmp == NULL || tmp->left == NULL)
        return flag;
    return tmp->left->data;
}

template<class T>
T binaryTree<T>::rchild(const T& x, T flag) const {
    Node* tmp = find(x, root);
    if (tmp == NULL || tmp->right == NULL)
        return flag;
    return tmp->right->data;
}

建树createTree(x)

• 使用队列，类似层次遍历的思路

template <class T>
void BinaryTree<T>::createTree(T flag)
{ 
    linkQueue< Node * > que;
    Node *tmp;
    T x, ldata, rdata;

    //创建树，输入flag表示空
    cout << "\n输入根结点：";
    cin >> x;
    root = new Node(x);
    que.enQueue(root);	  
    while (!que.isEmpty()) 
    {
        tmp = que.deQueue();
        cout << "\n输入" << tmp->data
                << "的两个儿子(" << flag 
                << "表示空结点)：";
        cin >> ldata >> rdata;
        if (ldata != flag)
            que.enQueue(tmp->left = new Node(ldata));
        if (rdata != flag)
        	que.enQueue(tmp->right = new Node(rdata));
    }
    cout << "create completed!\n";
}

二叉树遍历的非递归实现

前序遍历的非递归实现

• 使用栈
• 步骤：若栈非空，一直循环
  • pop一个节点
  • 访问该节点，然后先将右子树压入栈，再将左子树压入栈（记得判断非空）

template<typename T>
void binaryTree<T>::preOrder() const {
    stack<Node*> s;
    Node* current;

    cout << "前序遍历：";
    s.push(root);
    while (!s.empty()) {
        current = s.top();
        s.pop();
        cout << current->data;
        if (current->right != NULL)
            s.push(current->right);
        if (current->left != NULL)
            s.push(current->left);
    }
}

中序遍历的非递归实现

• 使用栈
• 注意：每个节点要pop两次
  • 每次pop时要做的操作是不一样的
  • 需要改造node类，使之能够存储pop的次数（加个计数器）
  • 最好新建一个结构体StNode来实现这种计数功能

struct StNode{
    Node *node;
    int pop_times;
    StNode(Node * N = NULL):node(N),pop_times(0) {}
};

• 步骤：若栈非空，一直循环
  • 若为第一次pop，根重新入栈，然后将左子树压进栈
  • 若为第二次pop，访问根节点，然后将右子树压进栈

template<typename T>
void binaryTree<T>::midOrder() const {
    stack<StNode> s;
    StNode current;

    cout << "\n中序遍历：";
    s.push(root);
    while (!s.empty()) {
        current = s.top();
        s.pop();
        ++current.pop_times;
        if (current.pop_times == 1) {
            s.push(current);
            if (current.node->left != NULL)
                s.push(StNode(current.node->left));
        } else if (current.pop_times == 2) {
            cout << current.node->data;
            if (current.node->right != NULL)
                s.push(StNode(current.node->right));
        }
    }
}

后序遍历的非递归实现

• 使用栈，类似中序遍历，node类需要存储pop的次数
• 每个节点要pop三次
• 步骤：若栈非空，一直循环
  • 若为第一次pop，根重新入栈，然后将左子树压进栈
  • 若为第二次pop，根重新入栈，然后将右子树压进栈
  • 若为第三次pop，访问根节点

改进方法

• 每个节点只需pop两次
• 步骤：若栈非空，一直循环
  • 若为第一次pop，根重新入栈，然后先将右子树压入栈，再将左子树压入栈
  • 若为第二次pop，访问该节点

template<typename T>
void binaryTree<T>::postOrder() const {
    stack<StNode> s;
    StNode current;

    cout << "\n后序遍历：";
    s.push(root);
    while (!s.empty()) {
        current = s.top();
        s.pop();
        ++current.pop_times;
        if (current.pop_times == 1) {
            s.push(current);
            if (current.node->right != NULL)
                s.push(StNode(current.node->right));
            if (current.node->left != NULL)
                s.push(StNode(current.node->left));
        } else if (current.pop_times == 2) {
            cout << current.node->data;
        }
    }
}

二叉树遍历算法的应用

• 计算二叉树中结点的个数、度为1的结点的个数
• 判断某个元素是否存在、从上到下/从左到右最早出现在哪里？
  • 从上到下：层次遍历
  • 从左到右：中序遍历
• 计算某个结点的层次数
  • 前中后遍历非递归实现都可，每个节点拉入栈时，将其层数设置为父亲节点层数+1
  • 当遍历到该节点时，即可获得该节点的层数
• 计算二叉树高度
  • 前中后遍历非递归实现都可，每个节点拉入栈时，将其层数设置为父亲节点层数+1
  • 设置一个变量maxHeight，在遍历过程中记录遇到的层数的最大值
  • 当遍历完该二叉树时，maxHeight的值（层数最大值）即为二叉树高度
• 计算某个结点的所有子孙
  • 前序遍历：节点出栈后，这个位置及以后出栈的所有节点
• 计算某个结点的所有祖先
  • 后序遍历非递归实现中，当一个节点pop出来时，栈中前面的所有元素就是它的祖先集合
• 删除分支
  • 后序遍历，当删除分支的根入栈时，后面所有出栈的结点都删除，直到分支的根出栈为止
• 构造二叉树、判断是否为满二叉树/完全二叉树
  • 构造：层次遍历
  • 判满/完全二叉树：层次遍历

**注意：**以下代码是gpt写的，看了一下方法没有问题，可能用了一些STL，理解大致思路就可以

计算二叉树高度/某个节点层次数

c此处以前序遍历为例

#include <iostream>
#include <stack>

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 计算二叉树高度
int getHeight(TreeNode* root) {
    if (!root) return 0;
  
    std::stack<std::pair<TreeNode*, int>> s;
    s.push({root, 1});
    int maxHeight = 0;
  
    while (!s.empty()) {
        TreeNode* node = s.top().first;
        int height = s.top().second;
        s.pop();
      
        maxHeight = std::max(maxHeight, height);
      
        if (node->right) s.push({node->right, height + 1});
        if (node->left) s.push({node->left, height + 1});
    }
  
    return maxHeight;
}

// 查找特定节点的层数
int getLevel(TreeNode* root, TreeNode* target) {
    if (!root) return 0;
    if (root == target) return 1;
  
    std::stack<std::pair<TreeNode*, int>> s;
    s.push({root, 1});
  
    while (!s.empty()) {
        TreeNode* node = s.top().first;
        int level = s.top().second;
        s.pop();
      
        if (node == target) return level;
      
        if (node->right) s.push({node->right, level + 1});
        if (node->left) s.push({node->left, level + 1});
    }
  
    return 0; // 未找到目标节点
}

int main() {
    // 创建一颗二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    // 计算二叉树高度
    int height = getHeight(root);
    std::cout << "二叉树高度: " << height << std::endl;

    // 查找特定节点的层数
    TreeNode* targetNode = root->left->right;
    int level = getLevel(root, targetNode);
    std::cout << "节点 " << targetNode->val << " 所在层数: " << level << std::endl;

    return 0;
}

判断完全二叉树

#include <iostream>
#include <queue>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool isCompleteTree(TreeNode* root) {
    if (root == nullptr) return true;

    std::queue<TreeNode*> q;
    q.push(root);
    bool hasNullChild = false;

    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();

        if (node->left) {
            if (hasNullChild) return false;
            q.push(node->left);
        } else {
            hasNullChild = true;
        }

        if (node->right) {
            if (hasNullChild) return false;
            q.push(node->right);
        } else {
            hasNullChild = true;
        }
    }

    return true;
}

int main() {
    // 创建一个完全二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);

    if (isCompleteTree(root)) {
        std::cout << "The tree is a complete binary tree." << std::endl;
    } else {
        std::cout << "The tree is not a complete binary tree." << std::endl;
    }

    return 0;
}

哈夫曼树与哈夫曼编码

字符的机内表示

前缀编码

• 字符只放在叶结点中
• 字符编码可以有不同的长度
• 由于字符只放在叶结点中，所以每个字符的编码都不可能是其他字符编码的前缀
• 前缀编码可被唯一解码
• 不等长的前缀编码相比等长编码可以更充分的利用空间

哈夫曼树

哈夫曼树是一棵最小代价的二叉树，在这棵树上，所有的字符都包含在叶结点上。

• 要使得整棵树的代价最小，显然权值大的叶子应当尽量靠近树根，权值小的叶子可以适当离树根远一些。
• 哈夫曼编码是一种前缀编码

哈夫曼树的结构特点：没有度为1的节点，只有度为0和度为2的节点，且所有字符只存放在叶节点中

想存$n$个不同的字符，需要一棵有$N = 2n-1$个节点的哈夫曼树

哈夫曼编码的生成

• 每个字符的编码是根结点到该字符的路径
• 左枝为0，右枝为1，加到编码上就行

哈夫曼树类的实现

• 为了便于找出一组符号的哈夫曼编码，我们可以定义一个哈夫曼树类。
• 哈夫曼树类的对象可以接受一组符号以及对应的权值，并返回每个符号对应的哈夫曼编码。因此，哈夫曼树类应该有两个公有的成员函数：
  • 构造函数：接受一组待编码的符号以及它们的权值，构造一棵哈夫曼树。
  • GetCode函数根据保存的哈夫曼树为每个叶结点生成哈夫曼编码。

哈夫曼树的存储

• 在哈夫曼树中，每个要编码的元素是一个叶结点，其它结点都是度数为2的节点

• 一旦给定了要编码的元素个数，由$n_0＝n_2+1$可知哈夫曼树的大小为$2n-1$

• 哈夫曼树可以用一个大小为2n的数组来存储。

  • 0结点不用，根存放在结点1。
  • 叶结点依次放在n+1到2n的位置
  • 0结点作为结束的判断依据

• 每个数组元素保存的信息：结点的数据、权值和父结点和左右孩子的位置

• 哈夫曼树的存储方式不是顺序实现，是一种使用静态存储的链接实现！

  • 一般而言，顺序实现采用静态存储，链接实现采用动态存储。但是哈夫曼树作为一种长度在生成前就可以确定的树，适合采用静态存储+链接实现，可以有效节约空间（哈夫曼树中有很多空节点）。

哈夫曼树的构造（哈夫曼算法）

1. 给定一个具有n个权值{ w1,w2,………wn }的结点的集合：F = { T1,T2,………Tn }
2. 初始时，设集合 A = F
3. 执行 i = 1 至 n -1 的循环，在每次循环时执行以下操作：
   1. 从当前集合中选取权值最小、次最小的两个结点
   2. 以这两个结点作为内部结点 bi 的左右儿子，bi 的权值为其左右儿子权值之和。
   3. 在集合中去除这两个权值最小、次最小的结点，并将内部结点bi 加入其中。这样，在集合A中，结点个数便减少了一个。这样，在经过了n-1 次循环之后，集合A中只剩下了一个结点，这个结点就是根结点。

哈夫曼树类

• 存储设计
  • 结点的表示：结点的数据、权值和父结点和左右孩子的位置
  • 哈夫曼树的存储：
  • 一个结点数组以及一个整型数据成员，保存数组的大小。
• 操作
  • 构建一棵哈夫曼树：构造函数实现。
  • 给出结点数据数组，权值数组和数据个数
  • 获取树上结点的哈夫曼编码
  • 返回一个数组，数组的元素由数据和编码两部分组成的

构造函数

template <class Type>
hfTree<Type>::hfTree(const Type *v, const int *w, int size) 	
{  const int MAX_INT = 32767;
    int min1, min2;    //最小树、次最小树的权值
    int x, y;     //最小树、次最小树的下标

    //置初值 
    length = 2 * size;
    elem = new Node[length];
    for (int i = size; i < length; ++i)
         { elem[i].weight = w[i - size];
            elem[i].data = v[i - size];
           elem[i].parent = elem[i].left = elem[i].right = 0;
         }     
// 构造新的二叉树
 for (i = size - 1; i > 0; --i)
    { min1 = min2 = MAX_INT; x = y = 0;
       for (int j = i + 1; j < length; ++j)
		  if (elem[j].parent == 0) 
		       if (elem[j].weight < min1) 
                          { min2 = min1; min1 = elem[j].weight; 
                             x = y; y = j; }//min1最小值，y最小值下标
                       else if (elem[j].weight < min2)
                               { min2 = elem[j].weight; x = j; } //min2次小值   
         elem[i].weight = min1 + min2;
         elem[i].left = x; elem[i].right = y; elem[i].parent = 0;
         elem[x].parent = i; elem[y].parent = i;
     }
} 

获取哈夫曼编码的函数

template <class Type>
void hfTree<Type>::getCode(hfCode result[]) 
{ 
    int size = length / 2;  
    int p,s; // s是追溯过程中正在处理的结点，p是s的父结点下标
    for (int i = size; i < length; ++i)
    {
        result[i - size].data = elem[i].data;
        result[i - size].code = "";
        p = elem[i].parent; s = i;
	while (p) {
		if (elem[p].left == s) 
                    result[i - size].code = '0' + result[i - size].code;
		    else result[i - size].code = '1' + result[i - size].code;
		s = p; p = elem[p].parent;
	}
    }  
}

树和森林

树的存储实现

标准形式

树中的每个结点除有数据字段之外，还有K个指针字段；其中K为树的度。

广义标准形式：在标准形式的基础上，再增加指向父亲结点的指针。

孩子链表示法

• 将每个结点的所有孩子组织成一个链表。

• 树的结点由两部分组成：

  • 存储数据元素值的数据部分

  • 指向孩子链的指针

  

孩子兄弟链表示法（最常用）

实质上是用二叉树表示一棵树。树中的每个结点有数据字段、指向它的第一棵子树树根的指针字段、指向它的兄弟结点的指针字段。

双亲（父节点）表示法

• 通过指向父结点的指针将树中所有的结点组织在一起

• 在双亲表示法中，每个结点由两部分组成：

  • 存储数据元素的数据字段

  • 存储父结点位置的父指针字段

• 这种表示法对求指定结点的祖先的操作很方便，但对求指定结点的子孙则不方便。

树的遍历

树的前序遍历

树的后序遍历

树的层次遍历

从遍历结果确定一个树

前序+后序 可以

• 由于树的前序+后序等效于对孩子兄弟链表示法的二叉树进行前序+中序遍历，所以可以先用二叉树前序+中序遍历确定孩子兄弟链表示法的二叉树形态
• 再转换成原来的树

前序+层次 可以

后序+层次 可以

树与二叉树的转化和关系

树可以转化为二叉树：树的孩子兄弟链表示法就是将一棵树表示成二叉树的形态，这样就可以将二叉树中的许多方法用在树的处理中。

树通过孩子兄弟链表示法转化后得到的二叉树的中序遍历与转换前的后序遍历相同

森林

• 森林通常定义为树的集合或树的序列。
• 森林的存储：存储一个森林要包括两方面的内容
  • 存储森林中的每一棵树
  • 表示这些树是属于同一个森林。

森林的二叉树存储

• 森林
• 将每棵树$T_i$转换成对应的二叉树$B_i$；
• 将$B_i$作为$B_{i-1}$​根结点的的右子树。

Chapter7 优先级队列

基于线性表的优先级队列

和普通队列差不多（当然多一个变量存储每个节点的优先级），没啥特别的

基于树的优先级队列——二叉堆

二叉堆

堆是一棵完全二叉树，且满足下列关系之一：

1. $$k_i \leq k_{2i} \, and \, k_i \leq k_{2i+1}$$

   • 人话：每个节点都小于自己的左节点和右节点
   • 满足这一条件的堆被称为最小堆

2. $$k_i \geq k_{2i} \, and \, k_i \geq k_{2i+1}$$

   • 人话：每个节点都大于自己的左节点和右节点
   • 满足这一条件的堆被称为最大堆

二叉堆的特性

• 结构性：完全二叉树
• 有序性：满足父结点小于子结点（最小化堆）或父结点大于子结点（最大化堆）

二叉堆的存储

采用顺序存储

• 如果数值越小，优先级越高，则可以用一个最小化堆存储优先级队列
• 在最小化堆中，最小元素是根元素，而根结点永远存放在数组的下标为1的元素中。
• 获取队头元素的操作就是返回下标为1的数组元素值
• 出队操作就是删除下标为1的数组元素中的值，重新调整堆
• 入队操作就是在数组的末尾添加一个元素，但添加后要调整元素的位置，以保持堆的有序性

优先级队列类

定义

template <class Type>
class priorityQueue:public queue<Type>
{
private:
    int currentSize;  
    Type *array;   
    int maxSize;
    void doubleSpace();
    void buildHeap( );//建堆，被priorityQueue调用
    void percolateDown( int hole );  //向下过滤
public:
    priorityQueue( int capacity = 100 ) 
    { 
        array = new Type[capacity];
        maxSize = capacity;   
        currentSize = 0;
    }
    priorityQueue( const Type data[], int size );
    ~priorityQueue() { delete [] array; }
    bool isEmpty( ) const { return currentSize == 0; }
    void enQueue( const Type & x );
    Type deQueue();
    Type getHead() { return array[1]; }
};

enQueue(x)

• enQueue操作是在堆中插入一个新元素
• 堆的插入是在具有最大序号的元素之后插入新的元素或结点，否则将违反堆的结构性。
• 如果新元素放入后，没有违反堆的有序性，那么操作结束。否则，让该结点向父结点移动，直到满足有序性或到达根结点。
• 新结点的向上移动称为向上过滤(percolate up)

template <class Type>
void priorityQueue<Type>::enQueue( const Type & x )
{  
    if( currentSize == maxSize - 1 )  doubleSpace();
  
    // 向上过滤
    int hole = ++currentSize;
    for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )
        array[ hole ] = array[ hole / 2 ];
    array[ hole ] = x;
} 

• 最差时间复杂度为$O(log n)$（对数）
• 平均好于最差

deQueue(x)

• 当最小元素被删除时，在根上出现了一个空结点。堆的大小比以前小1，堆的结构性告诉我们，最后一个结点应该删掉。
• 如果最后一项可以放在此空结点（根节点）中，就把它放进去。然而，这通常不符合堆的有序性。
• 需要与插入操作类似的操作：把某些项放入空结点，然后移动空结点。仅有的区别在于：对DeQueue操作，空结点是往下移动，称为向下过滤percolateDown 。

 template <class Type>
Type priorityQueue<Type>::deQueue()
{
    Type minItem;
    minItem = array[1];//输出最小值
    array[1] = array[currentSize--];
    percolateDown(1);
    return minItem;
}

向下过滤：percolateDown(x)

• 找到空结点的一个较小的子结点，如果该儿子的值小于我们要放入的项，则把该儿子放入空结点，把空结点往下推一层
• 重复这个动作，直到该项能被放入正确的位置。

template <class Type>
void priorityQueue<Type>::percolateDown( int hole )
{  
    int child;
    Type tmp = array[ hole ];
  
    for( ; hole * 2 <= currentSize; hole = child )
    {  
        child = hole * 2;
        if( child != currentSize && array[child + 1] < array[child] )
            child++;//child保留较小的子结点
        if( array[ child ] < tmp )   array[hole] = array[child];
        else break;
    }
   array[hole] = tmp;
}

时间复杂度分析：

• 因为树有对数的深度，在最坏情况下，deQueue是一个对数时间的操作。
• 根据堆的有序性，堆中最后一个结点的值一般都是比较大的。因此，向下过滤很少有提前结束的，所以deQueue操作平均也是对数时间。

建堆

一种不实用的方法

• 看成N次连续插入
• 时间复杂度为$O(n log n)$
• 输入数据和顺序都相同的情况下，该方法得出的二叉堆是唯一的
• 事实上，在构造过程中，我们并不关心每个元素加入后堆的状态，我们关心的是N个元素全部加入后的最后状态，最后的状态是要保证堆的有序性。至于中间过程中的有序性是否成立并不重要。
• 事实上，采用合适方法可以将时间复杂度降到O(n)

更合适的建堆方法

• 利用堆的递归定义
• 时间复杂度为$O(N)$
• 具体方法：
  • 函数buildHeap可以将一棵完全二叉树调整为一个堆
  • 先对左子堆和右子堆递归调用buildHeap，保证除了根结点外，其余的地方都建立起了堆的有序性
  • 然后对根结点调用percolateDown，以创建堆的有序性

最好的方法：建堆的非递归实现

• 以逆向层次的次序对结点调用percolateDown，直到根结点为止。
• 注意：不需要对叶结点执行percolateDown。因此，我们是从编号最大的非叶结点$\dfrac{i}{2}$开始。
• 时间复杂度O(N)

最终采用的方法：buildHeap()

template <class Type>
void priorityQueue<Type>::buildHeap( )
{  
    for ( int i = currentSize / 2; i > 0; i-- )
        percolateDown( i );
} 

总结：最好的方法是非递归实现

• 逆向层次次序调整每一个子堆
• 在调整每个子堆时，除子堆的根以外，所有结点满足堆的定义
• 根结点的调整和删除时一样，可以通过调用向下过滤percolateDown实现

集合

集合的操作：查找和排序

集合包括一下内容：

• Chapter8 静态查找表
• Chapter9 动态查找表：查找树，散列表
• Chapter10 排序算法
• Chapter11 外存储器上的查找和排序

集合的基本概念

• 集合中的数据元素除了属于同一集合之外，没有任何逻辑关系。
• 在集合中，每个数据元素有一个区别于其他元素的唯一标识，通常称为键值或关键字值
• 说人话，集合的元素是键值对（key-value）

集合元素的类型

template <class KEY, class OTHER>
struct SET {
    KEY key;
    OTHER other;
};

集合的主要运算

1. 查找某一个元素
2. 将集合集合中的元素按照它的唯一标识排序
   （都是对key的操作）

集合的存储

1. 任何容器都能存储集合
2. 常用的表示形式是借鉴于线性表或树
3. 唯一一个仅适合于存储和处理集合的数据结构是散列表

查找的基本概念

1. 用于查找的集合称之为查找表
2. 查找表的分类：
   • 静态查找表
   • 动态查找表
   • 内部查找
   • 外部查找
3. 查找的结果：成功/不成功

静态查找表

• 数据元素的个数和值不允许变化的查找表称为静态查找表
• 不允许插入和删除
• 实例：字典
• 可以用顺序表seqList存储，或直接存储在C++的原始数组中

无序表的查找

• 无序表：数组中的元素是无序的
• 无序表的查找：只能做线性的顺序查找
• 时间复杂度O(N)
• 顺序查找的优化：利用哨兵减少n次比较

顺序查找代码

template <class KEY, class OTHER>
int seqSearch(SET<KEY, OTHER> data[], 
                       int size, const KEY &x) 
{
    data[0].key = x;
    for (int i = size ; x != data[i].key; --i);
    return i;
}

优化的小trick:把要查找的key放到根节点，省得每次循环检查是否越界

有序表的查找

有以下几种方法：

• 顺序查找
• 二分查找
• 插值查找
• 分块查找

二分查找

• 每次检查排在中间的那个元素
  • 如中间元素等于要查找的元素，则查找完成
  • 否则，确定要找的数据是在前一半还是在后一半，然后缩小范围，在前一半或后一半内继续查找。
• 时间复杂度O(logN)

代码：

template <class KEY, class OTHER>
int binarySearch(SET<KEY, OTHER> data[],
                            int size, const KEY &x) 
{
    int low = 1,  high = size, mid;
    while (low <= high ) {                 //查找区间存在
        mid = (low + high) / 2;         //计算中间位置
    if ( x == data[mid].key )  return mid; 
    if ( x < data[mid].key) high = mid - 1;
        else low = mid + 1;
    }	
    return 0;
}

插值查找

• 适用于数据分布比较均匀的情况查找位置估计

• 查找位置估计：

  

• 缺点：计算量大

适用情况：

• 访问一个数据元素必须比一个典型的指令费时得多。例如，数组可能在磁盘里而不是在内存里，而且每次比较都需要访问一次磁盘。
• 这些数据必须不仅有序，而且分布相当均匀，这可以使每次估计都相当准确，可以将大量的数据排除出查找范围。这样，花费这些计算代价是值得的

分块查找

• 分块查找也称为索引顺序块的查找。
• 是处理大量数据查找的一种方法。
• 它把整个有序表分成若干块，块内的数据元素可以是有序存储，也可以是无序的，但块之间必须是有序的。

时间分析

查找由两个阶段组成：查找索引和查找块。设表长为n，被分为m块，采用顺序查找，平均所需时间为

$$\dfrac{m+1}{2}+\dfrac{\frac{n}{m}+1}{2} = \dfrac{m+\frac{n}{m}}{2} +1$$

• 故易知当$m = \sqrt{n}$时，平均时间最小=$\sqrt{n}+1$

Chapter9 动态查找表

• 既要支持快速查找，又要支持插入删除
• 动态查找表的抽象类

template <class KEY, class OTHER>
class dynamicSearchTable {
public:
    virtual SET<KEY, OTHER> *find(const KEY &x) const = 0;
    virtual void insert(const SET<KEY, OTHER> &x) = 0;
    virtual void remove(const KEY &x) = 0;
    virtual ~dynamicSearchTable() {};
};

实现方法

• 通常用树和哈希表实现
• 常用三种方法：
  • 二叉查找树
  • AVL树
  • 散列表

二叉查找树

• 二叉查找树是二叉树在查找方面的重要应用。
• 二叉查找树或者为空，或者具有如下性质：
  对任意一个结点p：
  • 如果p的左子树非空，则左子树上的所有结点的关键字值均小于p结点的关键字值。
  • 如果p的右子树非空，则右子树上的所有结点的关键字值均大于p结点的关键字值。
  • 结点p的左右子树同样是二叉查找树。

注意：
在二叉查找树中，最大和最小的元素不一定是叶节点，但最多只能有一个分支。

二叉查找树存储设计

• 采用标准的二叉链表存储一棵二叉查找树，需要一个指向根结点的数据成员

二叉查找树类

• 公有的成员函数：find、insert和remove 以及构造、析构函数
• 二叉查找树的插入、删除和查找都是通过递归实现的，而这三个公有函数的参数表中并不需要包含递归参数。
  • 为此，对于每个公有的成员函数都定义了一个对应的带有递归参数的私有的成员函数（包裹函数）

类的定义

template <class KEY, class OTHER>
class BinarySearchTree: public dynamicSearchTable<KEY, OTHER>
{ 
private:
    struct BinaryNode
    {
        SET<KEY, OTHER> data;
        BinaryNode *left;
        BinaryNode *right; 
        BinaryNode( const SET<KEY, OTHER> & thedata,
                    BinaryNode *lt=NULL,  BinaryNode *rt=NULL )
        : data( thedata ), left( lt ), right( rt ) { }
    };
   BinaryNode *root;
public:
    BinarySearchTree() ;
    ~BinarySearchTree();
    SET<KEY, OTHER> *find(const KEY &x) const ;
    void insert( const SET<KEY, OTHER> & x );
    void remove( const KEY & x );
 
private:  
    void insert( const SET<KEY, OTHER> & x, BinaryNode * & t );
    void remove( const KEY & x, BinaryNode * & t );
    SET<KEY, OTHER> *find(const KEY &x, BinaryNode *t ) const;
    void makeEmpty( BinaryNode *t );//析构用，同二叉树的clear
};

二叉查找树的操作

• 包括
  • 查找
  • 插入
  • 删除
• 由于树是递归定义的，因此这些操作往往也用递归实现。因为二叉树的平均高度为logN，这些操作的时间复杂度也是O(logN)

查找:find()

• 若根结点的关键字值等于查找的关键字，成功。
• 否则，若关键字值小于根结点，查其左子树；若关键字值大于根结点，查其右子树。在左右子树上的操作类似。
• 递归描述：
  • 如果树为空，返回空//没找到
  • 如果根结点等于被查结点，返回根结点地址//找到
  • 如果被查结点小于根结点，递归查找左子树，否则递归查找右子树

代码实现：

template <class KEY, class OTHER>
SET<KEY, OTHER> * BinarySearchTree<KEY, OTHER>::find(
                                        const KEY &x ) const
{      return find( x, root );     }
 
template <class KEY, class OTHER>
SET<KEY, OTHER> *BinarySearchTree<KEY, OTHER>::find( 
                                         const KEY & x, BinaryNode *t ) const
{   
    if  ( t == NULL || t->data.key == x )
        return (SET<KEY, OTHER> *) t;//强制类型转换
    if( x < t->data.key )   return find( x, t->left );  
    else return find( x, t->right );  
}

插入：insert()

• 若二叉树为空，则新插入的结点成为根结点。
• 如二叉树非空
  • 首先执行查找算法，找出被插结点的父亲结点。
  • 判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶结点插入。

注意：

• 新插入的结点总是叶结点
• 什么样的输入会使二叉查找树退化成表？从小到大插入数据或者一直从大到小插入数据

插入操作的递归实现：

• 如果当前树为空，插入值作为树的根结点，返回
• 如果插入值小于根结点，插入到左子树，否则插入到右子树。

代码实现：（递归实现）
使用两个指针（父节点和要插入的节点本身），可以有非递归实现

template <class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::insert( const SET<KEY,
                                                 OTHER> & x )
{    insert( x, root );    } 
template <class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::insert( const SET<KEY, 
                                                          OTHER> & x, BinaryNode *&t )
{	  
    if( t == NULL )
        t = new BinaryNode( x, NULL, NULL );
    else if( x.key < t->data.key )
        insert( x, t->left );
    else if( x.key > t->data.key )
        insert( x, t->right );
    else cout<<x.key<<“is exist”<<endl;
}

删除操作

分三种情况

删除叶节点

直接删除，更改它的父亲结点的相应指针字段为空。这不会改变二叉查找树的特性。

删除有一个儿子的结点

若被删结点只有一个唯一的儿子，将此儿子取代被删结点的位置，就能保持二叉查找树的有序性

删除有两个儿子的结点

• 删除这个结点会使其他结点从树上脱离。
• 选取“替身”取代被删结点。
• 替身的要求：维持二叉查找树的特性不变，故有以下两种方法：
  • 用左子树中的最右结点做替身
  • 用右子树中的最左结点做替身

AVL树

二叉平衡树介绍

1. 二叉平衡树就是满足某种平衡条件的二叉查找树，需满足排序条件
2. 平衡条件
   1. 容易维护
   2. 满足树的高度是$O(logN)$

为了查找树的性能尽可能好，要使树尽可能丰满

平衡树(AVL树)的定义

1. 定义：对于任一结点两棵子树的高度至多相差1。
2. 平衡因子（平衡度）：结点的左子树的高度－右子树的高度。平衡树上每个结点的平衡因子都为 ＋1、-1、0 。
3. 平衡树的优点：查找、插入、删除的复杂性均为O(logN)。

注意：

1. 平衡树不一定是丰满树

二叉平衡树的查找性能

易知查找性能与二叉树的高度成正比

定义：具有N个结点的平衡树，高度h满足

$$log_2(N+1) \leq h \leq 1.44 log_2(N+1) - 0.328$$

易知，最好情况：平衡二叉树

$$N \leq 2^h - 1 \\ h \geq \lceil log_2(N+1) \rceil$$

最坏情况为：斐波那契树，即每一子树的左右子树高度都相差1

斐波那契树

定义：

1. 空树是高度为0的斐波那契树。
2. 单个结点是高度为1的斐波那契树。
3. 若$T_{h-1}$和与$T_{h-2}$分别是高度为h-1和h-2的斐波那契树，则Th={Th-1,x,Th-2}是高度为h的斐波那契树。
4. 没有其他的树是斐波那契树。

对于高度为h的斐波那契树，其结点数n与高度有如下关系：

$$n_0 = 0 n_1 =1 n_h = n_{h-1} + n{h-2} + 1$$

差分后是斐波那契数列的递推式，故易知$n_h$其实是斐波那契数列的各项和

易知结论

$$n_{h} = F_{h+2} - 1$$

$$\implies n_h =$$

AVL树的存储实现

1. 采用二叉链表
2. 每个结点必须保存平衡信息
3. 平衡信息采用每棵树的高度，结点的平衡度是左右子树高度差

AVL树类的实现

template <class KEY, class OTHER>
class AvlTree: public dynamicSearchTable<KEY, OTHER> {
    struct AvlNode
    {    
        SET<KEY, OTHER>   data;
        AvlNode           *left;
        AvlNode           *right;
        int               height; //结点的高度
  
        AvlNode( const SET<KEY, OTHER> &element , 
                                    AvlNode *lt, AvlNode *rt, int h=1)
        : data(element), left( lt ), right( rt ), height(h) { }
     };
 
    AvlNode *root;
public:
    AvlTree() { root = NULL; }
    ~AvlTree( ) { makeEmpty( root); }
    SET<KEY, OTHER> *find( const KEY & x ) const;
    void insert( const SET<KEY, OTHER> & x ) ;
    void remove( const KEY & x );
private:
    void insert( const SET<KEY, OTHER> & x, AvlNode * & t ) ;
    bool remove( const KEY & x, AvlNode * & t ) ;
    void makeEmpty( AvlNode *t );
    int height( AvlNode *t ) const { return t == NULL ? 0 : t->height;}
    void LL( AvlNode * & t );//用于插入
    void LR( AvlNode * & t ); //用于插入
    void RL( AvlNode * & t ); //用于插入
    void RR( AvlNode * & t ); //用于插入
    int max(int a, int b) {return (a>b)?a:b;}//用于树的高度计算
    bool adjust(AvlNode *&t, int subTree); //用于删除
};

AVL树的插入

• 插入过程与二叉查找树的插入相同，只是插入后可能出现两种情况：
  • 插入后，不破坏平衡性，只是改变了树根到插入点的路径上的某些结点的平衡度，因此需要自底向上修改结点的平衡度
  • 破坏了路径上的某些结点的平衡性，需要向上调整树的结构
  • 在调整平衡的过程中，只要有一个结点的平衡度不变，它上面的结点的平衡度也不变，调整可以结束。
• 时间复杂度O(log N)

重新平衡的基本思路

• 从插入位置向根回溯
• 如果结点原来的平衡度为0，则插入后该结点不可能失衡，重新计算平衡度，继续往上回溯（可能会影响上层结点）
• 如果结点原来的平衡度非0，可能成为失衡结点
  • 重新计算平衡度
  • 如果平衡度在合法范围，调整结束（因为这种情况下该节点的子树树高肯定没变）
  • 如果失去平衡，重新调整树的结构，调整结束

可能引起不平衡的情况

• 在结点的左孩子的左子树上插入（LL）
• 在结点的左孩子的右子树上插入（LR）
• 在结点的右孩子的左子树上插入（RL）
• 在结点的右孩子的右子树上插入（RR）
• LL和RR镜像对称，LR和RL镜像对称

重新平衡的方法

LL问题

解决方法：单次旋转，对不平衡节点右旋(RightRotate)，将该方法称为LL单旋

• 将失衡结点的左儿子作为根
• 原来的根结点作为他的右子树
• 原先的右儿子作为原先根的左儿子

该方法满足平衡调整的要求：

• 保持了树的有序性
• 保持了原先的高度

RR问题

与LL问题为镜像对称

解决方法：单次旋转，对不平衡节点左旋(LeftRotate)，将该方法称为RR单旋

LR问题

解决方法：双旋转

• 先对不平衡节点的左子节点进行RR单旋（LeftRotate，左旋）
• 再对不平衡节点进行LL单旋（RightRotate，右旋）

RL问题

解决方法：双旋转

• 先对不平衡节点的右子节点进行LL单旋（RightRotate，右旋）
• 再对不平衡节点进行RR单旋（LeftRotate，左旋）

总结

• LL和RR
  • LL和RR的解决方案互为镜像对称
  • 两者都是单旋转解决，对不平衡节点本身做单旋转
  • 引起失衡的儿子作根节点
• LR和RL
  • LR和RL的解决方案互为镜像对称
  • 两者都是双旋转，即先对引起失衡的子节点单旋转，再对不平衡节点本身单旋转
  • 最终结果是引起失衡的孙子作根节点
• 所有情况的共性
  • 重构不会破坏有序性
  • 重构后树的高度保持不变，调整可以结束！

程序实现

私有的insert函数

template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::insert( const SET<KEY, OTHER> & x, AvlNode * & t )
{  
  if( t == NULL )              //在空树上插入
    t = new AvlNode( x, NULL, NULL);
  else if( x.key < t->data.key) {                          //在左子树上插入
    insert( x, t->left );
    if ( height( t->left ) - height( t->right ) == 2 )    //t失衡
    if( x.key < t->left->data.key ) LL( t ); else LR(t);
  }
  else if( x.key > t->data.key )  {                        //在右子树上插入
    insert( x, t->right );
  if( height( t->right ) - height( t->left ) == 2 )     //t失衡
    if( t->right->data.key < x.key ) RR(t); else RL(t);
  }
  //重新计算t的高度 
  t->height = max( height( t->left ) , height( t->right ) ) + 1;
}

LL单旋(右旋)

template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::LL( AvlNode * & t )
{
  AvlNode *t1 = t->left;       // 未来的树根
  t->left = t1->right;
  t1->right = t;
  t->height = max( height( t->left ),  height( t->right ) ) + 1;
  t1->height = max( height( t1->left ), height(t)) + 1;
  t = t1;//儿子做根
}

RR单旋（左旋）

template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::RR( AvlNode * & t )
{
  AvlNode *t1 = t->right;
  t->right = t1->left;
  t1->left = t;
  t->height = max( height( t->left ),  height( t->right ) ) + 1;
  t1->height = max( height( t1->right ), height(t)) + 1;
  t = t1;
}

LR和RL（双旋）

template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::LR( AvlNode * & t )
{
  RR( t->left );
  LL( t );
}
 
template <class KEY, class OTHER>
void AvlTree<KEY, OTHER>::RL( AvlNode * & t )
{
  LL( t->right );
  RR( t );
}

AVL树的删除

• 首先在AVL树上删除结点x，删除结点的操作与二叉查找树一样
• 然后调整平衡，调整平衡与插入类似

平衡调整的基本思路

• 与插入操作一样， 失衡结点存在于被删结点到根结点的路径上。在删除了一个结点后，必须沿着到根结点的路径向上回溯，随时调整路径上的结点的平衡度。
• 删除操作没有插入操作那么幸运。插入时，最多只需要调整一个结点。而删除时，我们无法保证子树在平衡调整后的高度不变。只有当某个结点的高度在删除前后保持不变，才无需继续调整。
• 递归的删除函数有一个布尔型的返回值。当返回值为true时，调整停止。当返回值为false时，继续调整。

平衡调整的各种情况及方法

注意：

• 此处讨论时假设删除发生在左子树
• 删除发生在右子树的情况和发生在左子树的情况是对称的，处理方法也对称
• 总体的情况个数是这边讨论的*2

技巧：

• 重构时，可以将删除看成在另外的子树插入了一个元素，这样就可以套用插入时的平衡调整方法。

情况a

没有失衡，高度没变，返回true

情况b

没有失衡，高度变矮，返回false

情况c

• 发生了失衡，需要调整：对不平衡节点P进行RR旋转（单次LeftRotate，左旋），重新平衡
• 高度变矮（$h+1\to h$），返回false

情况d

• 发生了失衡，需要调整：对不平衡节点P进行RL旋转（先对引起失衡的子节点右旋，再对不平衡节点本身左旋），重新平衡
• 高度变矮（$h+1\to h$），返回false

情况e

• 发生了失衡，需要调整：对不平衡节点P进行RL旋转（先对引起失衡的子节点右旋，再对不平衡节点本身左旋）或RR旋转（单次LeftRotate，左旋），重新平衡
• 高度不变（一直是$h+1$），返回true

删除总结

• 结点删除同二叉查找树。在删除了叶结点或只有一个孩子的结点后，子树变矮，返回false
• 每次递归调用后，检查返回值。如果是true，直接返回true。否则分5*2=10种情况进行处理

程序实现

私有的remove函数

template <class KEY, class OTHER>
bool AvlTree<KEY, OTHER>::remove( const KEY & x, AvlNode * & t ) 
{   
  if( t == NULL )     return true;   //被删除结点不存在
  if (x == t->data.key) {                           // 删除根结点
    if ( t->left == NULL || t->right == NULL ) {   
      AvlNode *oldNode = t;
      t = ( t->left != NULL ) ? t->left : t->right;
      delete oldNode;
      return false;
    }
    else {   
      AvlNode *tmp = t->right;
      while(tmp->left != NULL) tmp = tmp->left; 
      t->data = tmp->data;
      if (remove(tmp->data.key, t->right)) return true;
      else return adjust(t, 1);//右子树高度降低，调整
    }
  }
  if( x < t->data.key )   {                          // 在左子树上删除
    if (remove( x, t->left )) return true;
    else return adjust(t, 0);//左子树高度降低，调整
  }
  else  {                                        // 在右子树上删除
    if (remove( x, t->right )) return true;
    else return adjust(t, 1); //右子树高度降低，调整
  }
  }

调整函数adjust

• 进入调整函数，一定是某棵子树变矮了
• 调整函数检查结点有没有失衡。如果失衡，则做相应的调整。
• 函数的返回值是子树有没有变矮，变矮返回false，否则返回true
• 函数的第一个参数是所要检查的结点的地址t。第二个参数是t的哪棵子树变矮了。0是左子树变矮，1 是右子树变矮

template <class KEY, class OTHER>
bool AvlTree<KEY, OTHER>::adjust(AvlNode * &t, int subTree)
{   
  if (subTree) {                           //  在右子树上删除，使右子树变矮
    if (height(t->left) - height(t->right) == 1 ) return true;            // 情况a
    if (height(t->right) == height(t->left)) { --t->height; return false;} // 情况b
		if (height(t->left->right) > height(t->left->left))                 // 情况d
    { 
      LR(t);
      return false;
    }
		LL(t);//情况c和e
		if (height(t->right) == height(t->left)) return false;
    else return true;
	}
	else {      // 在左子树删除
		if (height(t->right) - height(t->left) == 1 ) return true;             // 情况a
		if (height(t->right) == height(t->left)) { --t->height; return false;} // 情况b
		if (height(t->right->left) > height(t->right->right))               // 情况d
    {
      RL(t);
      return false;
    }
		RR(t); //情况c和e
		if (height(t->right) == height(t->left)) return false;
    else return true;
	}
}

散列表

散列法，也称哈希法。它不用比较的办法，而是直接根据所求结点的关键字值 KEY 找到这个结点。因此理论上，它的时间复杂性为 O(1)，优于任何其它的查找算法。

一些概念：

• 负载因子：非空单元的比例

散列函数

D = H（key）

• D为存储位置，key为关键值，H为散列函数
• 散列函数的值域为[0,m-1]，m为散列表的长度
• 两个问题：
  1. 设计散列函数
  2. 解决冲突（碰撞）
• 散列函数的选择标准
  • 计算速度快
  • 散列地址尽可能均匀，使得冲突机会尽可能的少

除留余数法

H(key)= key MOD p 或 H(key)= key MOD p + c

• 这里p为小于等于m的素数。如：m = 1024, 则 p = 1019 。
• 最常用，余数总在0～p-1之间。
• 选取p为素数的理由：较为均匀，碰撞较少

数字分析法

对关键字集合中的所有关键字，分析每一位上数字分布。取数字分布均匀的位作为地址的组成部分

平方取中法

• 如果关键字中各位的分布都比较均匀，但关键字的值域比数组规模大，则可以将关键字平方后，取其结果的中间各位作为散列函数值。由于中间各位和每一位数字都有关系，因此均匀分布的可能性较大。

• 比如：47314731 = 22，382，361。中间部分究竟要选取几位，依赖于散列表的单元总数。若散列表总共有100
  个单元，我们可以选取最中间的部分，即第4、5位，那么关键字值为4731的结点的散列地址可选为82。

冲突问题及解决方法

冲突解决的方法：

• 闭散列表：利用本散列表中的空余单元
  • 线性探测法
  • 二次探测法
  • 再次散列法
• 开散列表：将碰撞的结点存放在散列表外的各自的线性表中（链接法）

线性探测法

• 当散列发生冲突时，探测下一个单元，直到发现一个空单元
• 在一个规模为11的散列表中依次插入关键字17、12，23，60、29、38 ，采用的散列函数为H(key) = key MOD 11。
• 负载因子小于0.5时，插入新元素一定能找到位置
• 也就是说，如果提前知道元素数量，申请元素数量*2倍的空间即可

• 查找：

  计算 addr = H(key)
  while (addr的内容非空 && 不等于要查找的键)
  	++addr
  	if (addr内容为空）
  		没有找到
  	else
  		找到

• 删除：一般来讲，删除某一元素，先要找到该元素，然后把该空间的内容清空。但这样就给查找带来了问题，某些元素会查不到。解决的方案是采用迟删除，即不真正删除元素，而是做一个删除标记。

二次探测法

地址序列为$H+1^2$, $H+2^2$, $H+3^2$​, ……

保证探测到的是新单元

• 定理：如果采用二次探测法，并且表的大小是一个素数，那么，如果表至少有一半是空的（负载因子<0.5），新的元素总能被插入。而且，在插入过程中，没有一个单元被探测两次。

散列表扩展

• 如果负载因子>0.5，需将数组扩大一倍
• 不能把原数组的内容复制到新数组的前半部分，需要重新计算每一元素的散列值，称为重新散列

再次散列法

• 采用第二个散列函数 H1(x),H1(x)+H2(x), H1(x)+2*H2(x),……
• H2(x)的选择是非常重要的。建议采用H2(x) = R - (x mod R)，其中R是小于表长的一个素数

闭散列表的共性

• 都需要迟删除！
• 不论用什么方法，闭散列表在处理冲突问题时都无法完全避免聚集！！！

开散列表

将碰撞的结点存放在散列表外的各自的线性表中（链接法）

链地址法

开散列表的实现

• 开散列表是将所有散列到同一地址的元素链成一个单链表，于是需要定义了一个单链表中的结点类。
• 采用不带头结点的单链表散列表保存在一个数组中，数组的每个元素是一个指针，指向对应的单链表的首地址。

代码实现

闭散列表的实现

• 散列表必须支持的三个操作：查找、插入、删除。
• 闭散列表是用一个数组实现，数组的大小是由用户定义散列表时指定
• 由于闭散列表中的删除是用迟删除的方法实现的，为此每个数组元素除了要保存对应的数据元素之外还必须保存一个数组元素的状态（空/正常存储/已删除）。

template <class KEY, class OTHER>
class closeHashTable:public dynamicSearchTable<KEY, OTHER> {
  private:
      struct node { //散列表的结点类
          SET <KEY, OTHER>  data;
		  int state;  //0 -- empty   1 -- active   2 -- deleted
		  node() {state = 0;}
	  };
      node *array;
      int  size;
      int (*key)(const KEY &x);//哈希函数
      static int defaultKey(const int &x) {return x;} 
  public: 
     closeHashTable(int length = 101, int (*f)(const KEY &x) = defaultKey) ;
     ~closeHashTable() {delete [] array;}
     SET<KEY, OTHER> *find(const KEY &x) const;
      void insert(const SET<KEY, OTHER> &x);
      void remove(const KEY &x) ;
};

构造函数

template < class KEY, class OTHER >
closeHashTable<KEY, OTHER>:: 
closeHashTable
            (int length, int (*f)(const KEY  &x) )
{
	size = length;
	array = new node[size];
	key = f;    //哈希函数为f
} 

insert函数的实现

template <class KEY, class OTHER>
void closeHashTable<KEY, OTHER>::insert(const SET<KEY, OTHER> &x)
{
	   int initPos, pos ;
	
	   initPos = pos = key(x.key) % size;  //%size保护作用，避免越界
	   do {  
              if (array[pos].state != 1) {       // 0或2，找到空单元
                   array[pos].data = x; 
                   array[pos].state = 1; 
                   return;
              }
	       pos = (pos+1) % size;
        } while (pos != initPos);
}

remove函数的实现

template <class KEY, class OTHER>
void closeHashTable<KEY, OTHER>::remove(const KEY &x) 
{
	   int initPos, pos ;
 
	   initPos = pos = key(x) % size;
       do {
            if (array[pos].state == 0) return;  //没找到
 	        if (array[pos].state == 1 && array[pos].data.key == x) {  // 找到，删除
		      array[pos].state = 2;
		      return;
	        }
	        pos = (pos+1) % size;  //没找到，需要往后找
       } while (pos != initPos);
}

find函数的实现

template <class KEY, class OTHER>
SET<KEY, OTHER> *closeHashTable<KEY, OTHER>::find(const KEY &x) const
{
 	    int initPos, pos ;
 
	    initPos = pos = key(x) % size;
         do {
              if (array[pos].state == 0) return NULL;     // 没有找到
	          if (array[pos].state == 1 && array[pos].data.key == x)    // 找到
                   return (SET<KEY,OTHER> *)&array[pos];
	           pos = (pos+1) % size;
          } while (pos != initPos);
}

开散列表的实现

Chapter10 排序

基本概念

• 关键字值相同的数据元素在排序前后的相对次序保持不变，则称为稳定排序，否则称为不稳定排序。

排序算法的衡量标准

1. 时间复杂度：考虑比较操作和搬移操作
2. 空间复杂度
3. 稳定性

插入排序

基本原理： 首先将由第一个数据元素组成的序列看成是有序的，然后将剩余的n-1个元素依次插入到前面的已排好序的子序列中去，使得每次插入后的子序列也是有序的。

常见的几种插入排序：

• 直接插入排序
• 折半插入排序
• 希尔排序

直接插入排序

时间复杂度

1. 最佳情况：

   
   • 比较N-1次，$O(N)$
   • 搬移2(N-1)，$O(N)$

2. 最差情况：

   
   • 比较$\sum_{i=1}^{N-1}(i+1)=O(N^2)$​
   • 搬移$\sum_{i=1}^{N-1}(i+2)=O(N^2)$

3. 平均情况

   • 比较$\sum_{i=1}^{N-1}(\dfrac{i}{2}+1)=O(N^2)$​

   • 搬移$\sum_{i=1}^{N-1}(\dfrac{i}{2}+2)=O(N^2)$

空间复杂度

O(1)

稳定性

有稳定性，同样的key顺序可以不变

适用情况

短序列或者几乎是已排序（有序性好）的序列

template <class KEY, class OTHER>
void simpleInsertSort(SET<KEY, OTHER> a[], int size)
{    
	int k;
	SET<KEY, OTHER> tmp; 
    for (int j=1; j<size; ++j) {
         tmp = a[j];
         for ( k = j-1; tmp.key < a[k].key && k >= 0; --k)
             a[k+1] = a[k];
         a[k+1] = tmp;
    }
}

折半插入排序

利用二分查找法，快速地找到a[j]的插入位置。从而使比较次数下降到O(logN)

时间复杂度

• 比较：

$$\sum_{i=1}^{N-1} log(i+1) = O(N log N)$$

• 搬移：

希尔排序

希尔排序的思想是避免大量的数据搬移，先是比较那些离得稍远些的元素，这样，一次交换就相当于直接插入排序中的多次交换。然后比较那些离得近一点的元素，以此类推，逐步逼近直接的插入排序

利用了直接插入排序的两个性质：

1. 在最佳情况下（正序）时间复杂度为O(N);

2. 对于短序列，直接插入排序比较有效。

算法思想

• 先将序列分割成若干个小序列，在这些小序列内进行插入排序；
• 分割方法：相隔一定距离的各个记录组成一个子序列逐渐扩大小序列的规模，
• 减小小序列的个数，使得待排序列处于更有序的状态；
• 最后对整个序列进行直接插入排序，从而完成排序

步长（增量）的选择

如果选择1，2，4，8…… ，时间复杂度为$O(N^2)$

但事实上：

• 步长不应互为倍数

• 最后一次排序步长为1

• Knuth的推荐序列：1，3，7，15，…… ，即$2^n -1$

• 平均时间复杂性是$O(N^\frac{3}{2})$

• 空间复杂度： O(1)

• 不稳定！

代码实现

template <class KEY, class OTHER>
void shellSort(SET<KEY, OTHER> a[], int size)
{
    int step, i, j;
    SET<KEY, OTHER> tmp;
 
    for (step = size/2; step > 0; step /= 2)     //step为希尔增量
    for (i = step; i < size; ++i) {
	     tmp = a[i];
         for (j = i - step; j >= 0 && a[j].key > tmp.key;  j -= step) 
	           a[j+step] = a[j];
	     a[j+step] = tmp;
    }
}

选择排序

• 首先，从n个元素中选出关键字最小的元素。
• 再从剩下的(n-1)个元素中选出关键字最小的元素
• 依次类推，每次从剩下的元素序列中挑出关键字最小的元素，直至序列中最后只剩下一个元素为止。
• 这样，把每次得到的元素排成一个序列，就得到了按非递减序排列的排序序列。

直接选择排序

• 特点：逐个比较
• 首先在所有元素中用逐个比较的方法选出最小元素，把它与第一个元素交换；
• 然后在剩下的元素中再次用逐个比较的方法选出最小元素，把它与第二个元素交换；
• 以此类推，直到所有元素都放入了正确的位置。

分析

• 比较次数：$\dfrac{N^2 -N}{2}$
• 搬移次数：$3(N-1)$​
  • 1次交换=3次搬移
• 时间复杂度：$O(N^2)$​
• 适合短序列；搬移次数少，适合大记录排序
• 不稳定
  • 例子

堆排序

• 直接选择排序在n个元素中选出最小元素需要n-1次比较，而利用基于堆的优先级队列选出最小元素只需要O(logN)的时间
• 排序N个元素，步骤如下：
  • 应用buildHeap对N个元素创建一个优先级队列（堆）
  • 通过调用N-1次deQueue取出每个项，结果就排好序了。

分析

• 时间复杂度：建堆用了$O(N)$的时间，deQueue是对数时间。因此总的时间是$O(NlogN)$。
• 空间复杂度：$O(1)$
• 稳定性：不稳定
• 适用情况：适合长序列

交换排序

• 交换排序就是根据序列中两个数据元素的比较结果来确定是否要交换这两个数据元素在序列中的位置。
• 交换排序的特点是：通过交换，将关键字值较大的数据元素向序列的尾部移动，关键字值较小的数据元素向序列的头部移动。

冒泡排序（直接交换排序）

• 优化：设置交换标志，当一轮冒泡中没有出现交换时，代表序列已经有序，即可终止

分析

• 比较次数：$O(N^2)$
  • 优化后最好情况：有序，只需进行$N-1$次比较，时间复杂度$O(N)$
• 搬移次数：
  • 最好情况：正序$O(1)$
  • 最差情况：逆序$O(N^2)$
  • 平均$O(N^2)$
• 空间复杂度：$O(1)$
• 稳定性：稳定
• 不一定适合接近有序的序列因为有不确定性
  • 改进措施：摇动排序，一次向后冒泡，一次向前冒泡，向后和向前交替进行
• 冒泡排序是最差的，即使改进也不如直接插入和直接选择。

快速排序

• 在待排序的序列中选择一个数据元素，以该元素为标准，将所有数据元素分为两组：
  • 第一组的元素均小于或等于标准元素，放在数组的前面部分；
  • 第二组的数据元素均大于标准元素，放在数组的后面部分；
  • 标准元素放在中间，这个位置就是标准元素的最终位置。
  • 这称为一趟划分。
• 然后对分成的两组数据重复上述过程（递归），直到所有的元素都在适当的位置为止。

程序实现

• 执行一次划分，再执行两个递归
• 快速排序是用递归的方式实现的，它的递归参数就是排序的范围

划分函数divide()

template <class KEY, class OTHER>
int divide( SET<KEY, OTHER> a[], int low, int high)
{
     SET<KEY, OTHER>  k = a[low];
     do  {
          while (low < high && a[high].key >= k.key) --high;
          if (low < high) { a[low] = a[high]; ++low;}
          while (low < high && a[low].key <= k.key) ++low;
          if (low < high)  {a[high] = a[low]; --high;}
     } while (low != high);
     a[low] = k;
     return low;
}

快速排序函数quickSort()

template <class KEY, class OTHER>
void quickSort(SET<KEY, OTHER> a[], int low, int high)
{ 
    int mid;

    if (low >= high) return; 
    mid = divide(a, low, high); 
    quickSort( a, low, mid-1);//排序左一半
    quickSort( a, mid+1, high);//排序右一半
}

（可选）包装函数

template <class KEY, class OTHER>
void quickSort(SET<KEY, OTHER> a[], int size)
{
    quickSort(a, 0, size-1);
}

快速排序性能分析

根据快排算法，可以写出运行时间的递归表达式

$$T(N) = T(i) + T(N-i-1) + cN \\ T(0) = T(1) = 1$$

最好情况分析

快速排序的最好情况是中心点将集合划分成两个相同规模的子集，且这种划分发生在递归的每个阶段。 那么就有

$$T(N) = 2T(\dfrac{N}{2}) + cN$$

式子两边同除以N，进行递推转通项

$$\dfrac{T(N)}{N} = \dfrac{T(\frac{N}{2})}{\frac{N}{2}} + c \\ \dfrac{T(\frac{N}{2})}{\frac{N}{2}} = \dfrac{T(\frac{N}{4})}{\frac{N}{4}}+ c \\ \cdots \\ \dfrac{T(2)}{2} = \dfrac{T(1)}{1} + c$$

进行递推转通项，可得

$$T(N) = cNlogN + T(1) = O(NlogN)$$

最坏情况分析

快速排序的最坏情况是中心点是最大或最小，将集合划分成规模为0和N-1的子集，此时

$$T(N) = T(N-1) + cN$$

递推转通项，得到

$$T(N) = T(1) + c \sum_{i=2}^N i = O(N^2)$$

平均情况分析

考虑每个可能的子集规模的开销并求平均值，由于有两个递归调用加上用来执行划分的线性时间

$$T(N) = 2T(\dfrac{\sum_{i=0}^{N-1}T(i)}{N}) + cN$$

这推导真的太烦了，应该不考吧，随便写写了

$$NT(N) - (N-1)T(N-1) = 2T(N-1) + c(2N-1) \\ NT(N) = (N+1)T(N-1) + 2cN$$

然后递推转通项

$$\frac{T(N)}{N+1} = \frac{T(N-1)}{N} + \dfrac{2c}{N+1} \\ \frac{T(N-1)}{N} = \frac{T(N-2)}{N-1} + \dfrac{2c}{N} \\ \cdots$$

相加得到

$$\frac{T(N)}{N+1} = \frac{T(1)}{2} + 2c\sum_{i=3}^{N+1}\dfrac{1}{i} = O(\log N)$$

最终得到结论

$$T(N) = O(N\log N)$$

结论

1. 时间复杂度
   • 每次

归并排序

• Merge sort的思想来于合并两个已排序的有序表
• 实现方法：
  • 顺序比较两者的相应元素，小者移入另一表中
  • 反复如此，直至其中一表为空为止
  • 将另一表中剩余结点自左至右复制到表C的剩余位置。

程序实现

template <class KEY, class OTHER>
void merge(SET<KEY, OTHER> a[], int left, int mid, int right)
{
    SET<KEY, OTHER> *tmp = new SET<KEY,OTHER>[right-left+1]; 
    int i= left, j = mid, k = 0;
 
    while (i < mid && j <= right)                          //两表都未结束
	       if (a[i].key < a[j].key)     tmp[k++] = a[i++]; 
	       else tmp[k++] = a[j++]; 
 
    while ( i<mid )  tmp[k++] = a[i++];       //前半部分没有结束
    while ( j<=right )  tmp[k++] = a[j++];    //后半部分没有结束
	 
    for (i=0, k = left; k<=right; ) a[k++] = tmp[i++];
    delete [] tmp;
}

template <class KEY, class OTHER>
void mergeSort(SET<KEY, OTHER> a[], int left, int right)
{
     int mid = (left+right)/2;
 
     if (left == right) return;
     mergeSort(a, left, mid);
     mergeSort(a, mid+1, right);
     merge(a,left,mid+1,right);
}

（可选）包装函数

template <class KEY, class OTHER>
void mergeSort(SET<KEY, OTHER> a[], int size)
{
    mergeSort(a, 0, size-1);
}

分析

1. 简单地将原始序列分为两个子序列$O(1)$
2. 分别对每个子序列递归排序$OT(N/2)$
3. 最后将排好序的子序列合并为一个有序序列$O(N)$

综上，写出递推公式，并且使用主定理可以得到时间复杂度

$$T(N) = 2T(\frac{N}{2})+ O(N) = O(Nlog_2N)$$

时间复杂度

写出递推公式

• 归并排序具有稳定性，而且也是优化算法中为数不多具有稳定性的
• 时间复杂度$O(NlogN)$
• 空间复杂度$O(N)$​，这是个重要的缺点
• 经常应用在外排序中

基数排序

低位优先法（LSD）

• 先对最低位K0进行口袋排序，然后把所有记录按口袋的顺序收在一起；
• 再对序列按照次低位K1进行口袋排序，然后把所有记录按口袋的顺序收在一起；
• 依次类推，直到对最高位Kd-1排序，序列就变成有序的了。
• 总结：这是一个分、收；分、收；…；分、收的过程。

分析

• 时间复杂度：O(d(N+r))
  • 分：O(N)
  • 收：O®
  • 循环次数d
  • 由于大部分情况下$N >> d,r$，所以可以认为基数排序具有常数级别的时间复杂度$O(N)$
• 空间复杂度：O®
• 稳定
• 注：N指排序的数字数目，r指桶的个数，d为最大数字的位数

程序实现

• 思路：采用带首尾指针的链表，便于收集。
• 每个口袋用单链表表示，建立基数个首尾指针，以指针数组表示。
• 分：对每个口袋建立单链表
• 收：将单链表的首尾指针相连

template <class OTHER>
struct node {
    SET<int, OTHER> data;
    node *next;
 
    node() { next = NULL; }
    node(SET<int, OTHER> d): data(d)
          { next = NULL; }
};

template <class OTHER>
void bucketSort(node<OTHER> *&p)                // p是链表头
{
    node<OTHER> *bucket[10], *last[10], *tail ;        
    int i, j, k, base = 1, max = 0, len = 0;
    for (tail = p; tail != NULL; tail = tail->next)        // 找最大键值
	  if (tail->data.key > max) max = tail->data.key;

    // 寻找最大键值的位数
    if (max == 0) len = 0;
    else while (max > 0) { ++len; max /= 10; }
    for (i = 1; i <= len; ++i) {                 // 执行len次的分配与重组
       for (j = 0; j <= 9; ++j) bucket[j] = last[j] = NULL;      
       while (p != NULL) {                                  // 执行一次分配
  	      k = p->data.key / base % 10;                    
	      if (bucket[k] == NULL)  bucket[k] = last[k] = p;
	      else last[k] = last[k]->next = p; 
	      p = p->next;
       }
       p = NULL;                                             // 重组后的链表头
       for (j = 0; j <= 9; ++j) {                                  // 执行重组
          if (bucket[j] == NULL) continue;
          if (p == NULL)  {p = bucket[j]; tail = last[j];} 
          else tail->next = bucket[j];
          tail = last[j];
       }
       tail->next = NULL;                   // 表尾置空
       base *= 10;                          // 为下一次分配做准备
     }
}

总结

内排序方法比较

算法	最大时间	最小时间	平均时间	辅助空间	稳定性
直接插入排序	$O(N^2)$	$O(N)$	$O(N^2)$	$O(1)$	稳定
折半插入排序	$O(N^2)$	$O(Nlog_2N)$	$O(N^2)$	$O(1)$	稳定
希尔排序	$O(N^2)$	$O(N^{1.5})$	$O(N^{1.5})$	$O(1)$	不稳定
直接选择排序	$O(N^2)$	$O(N^2)$	$O(N^2)$	$O(1)$	不稳定
堆排序	$O(NlogN)$	$O(NlogN)$	$O(NlogN)$	$O(1)$	不稳定
直接交换（冒泡）排序	$O(N^2)$	$O(N^2)$	$O(N^2)$	$O(1)$	稳定
快速排序	$O(N^2)$	$O(NlogN)$	$O(NlogN)$	$O(1)$	不稳定
归并排序	$O(NlogN)$	$O(NlogN)$	$O(NlogN)$	$O(N)$	稳定
基数排序	$O(d(N+r))$	$O(d(N+r))$	$O(d(N+r))$	$O(r)$	稳定

注：

• 希尔排序指选定最优序列情况下的希尔排序
• 直接交换（冒泡）排序指没有使用交换标志和摇动排序优化的版本

外部查找与排序

外部查找

B树

设计思想

• 提供外存中的随机查找
• 访问磁盘的次数与查找树的高度成正比
• 增加树的分叉，就能降低树的高度，即采用M叉查找树
• M叉查找树的最佳高度为：$log_MN$
• 在M叉查找树的基础上考虑平衡，避免退化

概念

• B树是一棵平衡的M叉查找树，是索引存储中的索引结构M叉查找树
• 需要保存M-1个关键值来判断到哪个分支查找

定义

一棵 m 阶 B 树或者为空，或者满足以下条件：

• 根结点要么是叶子，至少有两个儿子，至多有m个儿子

• 除根结点和叶子结点之外的中间结点，每个结点的儿子个数$s$满足 $⌈\dfrac{m}{2}⌉ ≤s≤m$

• 有 s 个儿子的非叶结点具有$n = s － 1$个关键字，这些结点的数据信息为

  $$(n, A_0, (K_1, R_1), A_1, (K_2, R_2), A_2, ……… (K_n, R_n), A_n)$$

• 所有的叶子结点都出现在同一层上，即它们的深度相同，并且不带信息

B树的插入

• 与二叉查找树类似，插入总是在最底层
• 首先在m阶 B 树上进行查找操作，确定新插入的关键字key 在最底层的非叶结点的插入位置，将 key 和记录的存储地址按序插入到最底层上的某个结点。
• 若被插入结点的关键字个数小于等于m-1, 则插入操作结束；如插入10
• 若该结点原有的关键字个数已经等于m-1,必须分裂成两个结点。如插入39

B树的删除

• 类似于二叉查找树的删除操作，同样采用了“替身”的方法，替身为右子树最左面的关键字或左子树最右面的关键字
• 删除最底层的关键字，有以下几种情况：
  • 若删除关键字之后，结点的关键字的个数满足B树的结点的定义，删除结束。
  • 若删除后关键字个数小于下限：
    • 向结点的左或右兄弟结点借一个关键字过来。
    • 若该结点的左或右兄弟结点的关键字的个数正好为下限 ，则合并结点的操作

B+树

B+树是既能提供随机查找，也能提供顺序访问的存储结构。

定义

B+树是满足某些平衡条件的M叉树。M阶的B+树是具有以下性质的M叉树：

• 所有数据记录被存贮在叶子中，所有的叶子连成一个单链表。
• 非叶子结点至多保存M-1个键来引导查找，键i表示子树i+1中键的最小值。
• 根或者是叶子，或者是有2到M个儿子。
• 除根之外所有的非叶结点的儿子数为⌈M/2⌉到M之间。这保证了B树不会退化成二叉树。
• 所有的叶子都在同一层上，并且每个叶子有⌈L/2⌉ 到L个数据项

B+树的插入

• 叶结点不满：把新结点插入叶子，重新调整该叶子中数据的顺序
• 叶子已经装满 ：
  • 通过分裂该叶子，形成两个半满的叶子来插入一个新的项 。更新父结点如果父亲的儿子数量已经满了，我们就继续分裂父亲。最坏情况要分裂根。这就是为什么根结点允许只有两个孩子。

B+树的删除

• 删除操作首先查找到要删除的项，然后删除它
• 如果此时它所在的叶子的元素数量正好满足要求的最小值，删除该项就会使它低于最小值
  • 如果邻居不是最少的情况，就借一个过来领养；
  • 如果邻居也处于最少的情况，就把两个结点合并成一个满的结点。很不幸的是，在这种情况下父亲就失去了一个儿子。如果它引起父亲的儿子数少于了最小值，我们就要使用同样的策略了。这个过程一直向上进行过滤到根。如果在寄养的过程中，根只剩下了一个儿子，就把根删除，让它的儿子作为新的树根，这也是唯一能使B树变矮的情况。

外部排序

置换选择排序

多路归并

• k路归并需要2k条磁带。A1到Ak和B1到Bk。归并数据在A1上
• 过程：
  • 回绕2k根磁带
  • 归并A1到Ak条磁带上的有序片段轮流放入B1到Bk
  • 回绕所有磁带归并B1到Bk条磁带上的有序片段轮流放入A1到Ak重复上述过程，直到只剩下一个有序片段

多阶段归并

• 按非均匀的方法分解原先的34个已排序片段。
• 如果把21个已排序片段放在T2，13个已排序片段放在T3
  • 在T3为空以前我们能够归并13个已排序片段到T1上。然后回绕T1和T3
  • 并将具有13个已排序片段的T1和具有8个已排序片段的T2归并到T3上
  • 然后归并T1和T3

Chapter13 图

图的定义

• 图可以用G=(V, E)表示。其中，V是顶点集，E是边集。
• 有向图：如果边是有方向的，称为有向图。
  • 有向图的边用<>表示。<A,B>表示从A出发到B的一条边。在有向图中，<A,B>和<B,A>是不一样的。

• 无向图：如果边是无方向的，称为无向图。无向图的边通常用（）表示。（A，B）表示顶点A和B之间有一条边。无向图也称为双向图。

  

• 加权图：边被赋予一个权值的图称为加权图。如果图是有向的，称为加权有向图，如果是无向的，称为加权无向图。

图的基本术语

• 邻接：若（Vi，Vj）是图中的一条边，则称Vi和Vj是邻接的。如<Vi，Vj>是图中的一条边，则称Vi邻接到Vj，或Vj和Vi邻接。

• 度：无向图中邻接于某一顶点的边的总数。

• 入度：有向图中进入某一顶点的边数，称为该顶点的入度

• 出度：有向图中离开某一顶点的边数，称为该顶点的出度

• 边与度的关系：度是二分之一边的数目（对于无向图和有向图都适用！）

  $$e = \dfrac{1}{2} \sum d_i$$

子图

设有两个图G=（V，E）和G‘=（V’，E’），如果$V' \subseteq V,E' \subseteq E$，则称G’是G的子图

• 人话：一个图是另外一个图的一部分

路径

• 对1<i<N，顶点序列w1,w2,……wN 中的顶点对（wi, wi+1）都有（wi, wi+1）∈ E或<wi, wi+1> ∈ E，那么，w1,w2,……wN是图中的一条路径。

• 非加权的路径长度就是组成路径的边数，对于路径w1,w2,……wN，非加权路径长度为N-1。

• 加权路径长度是指路径上所有边的权值之和。

• **简单路径和环：**如果一条路径上的所有顶点，除了起始顶点和终止顶点可能相同外，其余的顶点都不相同，则称其为简单路径。一个回路或环是一条简单路径，其起始顶点和终止顶点相同，且路径长度至少为1。

无向图的连通性

• 连通：顶点v至v’ 之间有路径存在

• 连通图：无向图 G 的任意两点之间都是连通的，则称 G 是连通图。

• 连通分量：非连通图中的极大连通子图

有向图的连通性

• 强连通图：有向图 G 的任意两点之间都是连通的，则称 G 是强连通图。
• 强连通分量：极大连通子图
• 弱连通图：如有向图G不是强连通的，但如果把它看成是无向图时是连通的，则称该图是弱连通的

完全图

• 完全图：每两个顶点之间都有边的无向图称为完全图。完全图有$C_n^2 = \dfrac{n(n-1)}{2}$​​条边。其中n是顶点个数
• 有向完全图：每两个顶点之间都有边的无向图称为完全图。完全图有$P_n^2 = n(n-1)$条边。其中n是顶点个数
• 有向无环图：如果一个有向图中没有环，则称为有向无环图

生成树与最小生成树

• 生成树是图G的极小连通子图G’，其中V(G’)=V(G)
• 用一颗树把图中所有的顶点都连起来（没有回路！）
• 生成树有n个顶点，n-1条边
• 生成树可以有多个
• 最小生成树（MST）：最小代价生成树

图的运算

• 常规操作：
  • 构造一个由若干个顶点、若干条边组成的图；
  • 判断两个顶点之间是否有边存在；
  • 在图中添加或删除一条边；
  • 返回图中的顶点数或边数；
  • 按某种规则遍历图中的所有顶点。
• 和应用紧密结合的运算：
  • 拓扑排序和关键路径
  • 找最小生成树
  • 找最短路径等。

图的存储

邻接矩阵和加权邻接矩阵

表示有向图

设有向图具有 n 个顶点，则用 n × n列的布尔矩阵 A 表示该有向图

在物理实现时的考虑：分别用 0、1、2、3 分别标识顶点A、B、C、D。而将真正的顶点数据字段之值放入一个一维数组之中。

注意：

• 出度: i行之和。
• 入度: j列之和。

表示无向图

设无向图具有 n 个顶点，则用 n × n的布尔矩阵 A 表示该无向图：

注意：

• 无向图的邻接矩阵是一个三角对称矩阵

• 顶点i的度: 第i行或第i列之和。

表示加权图

设有向图具有 n 个顶点，则用 n × n 的矩阵 A 表示该有向图； 如果i 至 j 有一条有向边且它的权值为a ，则A[i,j] = a 。如果 i 至 j 没有一条有向边。则A[i,j] = 空 或其它标志

特点

• 优点：判断任意两点之间是否有边方便，仅耗费 O(1) 时间。
• 缺点：即使 << n2 条边，也需内存 n2 单元，太多; 仅读入数据耗费 O( n2 ) 时间，太长。而大多数的图的边数远远小于n2。
• 适合稠密网不适合增加删除顶点

邻接表

• 设有向图或无向图具有 n 个顶点，则用顶点表和边表表示该有向图或无向图。

• 顶点表：用数组或单链表的形式存放所有的顶点。

  • 如果顶点数n已知，则采用数组形式，否则应采用单链表的形式。每个元素包含两个部分：顶点值和指向该顶点对应的边表的首地址。

• 边表（边结点表）：每条边用一个结点进行表示。同一个顶点出发的所有的边形成它的边结点单链表。

特点

• 邻接表是图的标准存储方式
• 优点：内存 ＝ 顶点数 ＋ 边数，处理时间也是顶点数 ＋ 边数，即为O(|V|+|E|)，适合稀疏网。
• 当谈及图的线性算法时，一般指的是O(|V|+|E|)
• 缺点：
  • 确定 i --> j 是否有边，最坏需耗费 O(n) 时间。
  • 无向图同一条边表示两次。边表空间浪费一倍。
  • 有向图中寻找进入某结点的边，非常困难（逆邻接表）。

图的遍历

对有向图和无向图进行遍历是按照某种次序系统地访问图中的所有顶点，并且使得每个顶点需且只能被访问一次。在图中某个顶点可能和图中的多个顶点邻接并且存在回路，因此在图中访问一个顶点u之后，在以后的访问过程中，又可能再次返回到顶点u，所以需对访问过的顶点加以标记。

深度优先搜索（dfs）

1. 选中第一个被访问的顶点；
2. 对顶点作已访问过的标志；
3. 依次从顶点的未被访问过的第一个、第二个、第三个…… 邻接顶点出发，进行深度优先搜索。

这是一个递归的过程，如果相邻顶点都被访问过时，则需要回溯，返回到前面的顶点进行搜索。回溯以栈的记忆功能实现。

深度优先搜索的实现

• 深度优先搜索DFS的实现方法和树的前序遍历算法类似，但必须对访问过的顶点加以标记

• dfs函数不需要参数，也没有返回值。它从编号最小的结点出发开始搜索，并将对当前对象的深度优先搜索的序列显示在显示器上。

• 以邻接表为例

  • 设置一个数组visited，记录顶点是否被访问过

  • 设计一个私有的深度优先搜索的函数，从某一顶点出发访问所有可达顶点

  • 如果是无向非连通图的或有向非强连通，则对图中尚未访问的顶点反复调用深度优先搜索，形成深度优先搜索的森林。

公有的dfs函数

void dfs( )
{ 
    对每个节点 v
        visited [v] = false;
  
    while (v = 尚未访问的节点）
       dfs(v，visited);  
}

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>::dfs() const
{
   bool *visited = new bool[Vers]; 

   for (int i=0; i < Vers; ++i) visited[i] = false;

   cout << "当前图的深度优先遍历序列为：" << endl;
   for (i = 0; i < Vers; ++i) {
	   if (visited[i] == true) continue;
	   dfs(i, visited);
	   cout << endl;
   }
} 

私有的dfs函数

访问从结点v出发可以访问到的所有结点

void dfs( v，visited )
{
    visited[v] = true;
    for 每个 v的邻接点w
        if( ! visited[w] )
            dfs( w,visited );
}

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>::dfs
                              (int start, bool visited[]) const
{ 
    edgeNode *p = verList[start].head;
  
    cout << verList[start].ver << '\t';  
    visited[start] = true;
    while (p != NULL){ 
	    if (visited[p->end] == false) dfs(p->end, visited);
	    p = p->next;
    }
}

时间性能分析

• dfs函数将对所有的顶点和边进行访问，因此它的时间代价和顶点数 |V| 及边数 |E| 是相关的，即是O(|V|+|E|)。
• 如果图是用邻接矩阵来表示，则所需要的时间是O（|V|2）。

广度优先搜索（bfs）

1. 选中第一个被访问的顶点；
2. 对顶点作已访问过的标志；
3. 依次访问已访问顶点的未被访问过的第一个、第二个、第三个……第 m 个邻接顶点 W1 、W2、W3…… Wm ，进行访问且进行标记，转向3；
4. 如果还有顶点未被访问，则选中一个起始顶点，转向2；
5. 所有的顶点都被访问到，则结束。

广度优先搜索一般使用队列实现

广度优先搜索的实现

广度优先搜索和树的层次遍历算法类似

• 需要记录每个顶点是否已被访问
• 需要记住每个已被访问的顶点的后继顶点，然后依次访问这些后继顶点。这可以用一个队列来实现
• 过程：
  • 将序号最小的顶点放入队列重复取队列的队头元素进行处理，直到队列为空。
  • 对出队的每个元素，首先检查该元素是否已被访问。如果没有被访问过，则访问该元素，并将它的所有的没有被访问过的后继入队
  • 检查是否还有顶点未被访问。如果有，重复上述两个步骤

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>::bfs() const
{ 
   bool *visited = new bool[Vers];
   int currentNode;
   linkQueue<int> q;
   edgeNode *p; 
   for (int i=0; i < Vers; ++i) visited[i] = false; 
   cout << "当前图的广度优先遍历序列为：" << endl; 
   for (i = 0; i < Vers; ++i) {
	 if (visited[i] == true) continue;
	 q.enQueue(i);
      while (!q.isEmpty()) {
		 currentNode = q.deQueue();
		 if (visited[currentNode] == true) continue;
		 cout << verList[currentNode].ver << '\t';
		 visited[currentNode] = true;
		 p = verList[currentNode].head;
		 while (p != NULL){
	        if (visited[p->end] == false) q.enQueue(p->end);
	        p = p->next;
		 }      
     }
	 cout << endl;
  }
}

图遍历的应用

无向图的连通性

如果无向图是连通的，则从无向图中的任意顶点出发进行深度优先搜索或广度优先搜索都可以访问到每一个顶点。访问的次序是一棵深度/广度优先生成树。

如果图是非连通的，深度/广度优先搜索可以找到一片深度/广度优先生成森林。每棵树就是一个连通分量。对无向图来说，深度/广度优先搜索可以找到了它的所有连通分量。

前面介绍的讨论的深度优先和广度优先遍历中，都已实现了这个功能。在这两个函数的输出中，每一行代表一个连通分量。

有向图的连通性

对有向图，深度优先搜索可以测试是否强连通，并找出所有强连通分量：

• 从任意顶点开始深度优先遍历G；
• 对森林中的每棵树进行后序遍历，并按遍历的顺序给每个顶点编号；
• 将G的每条边逆向，形成Gr；
• 从编号最大的顶点开始（按编号从大到小的顺序）深度优先遍历Gr，得到的深度优先遍历森林的每棵树就是G的强连通分量。

欧拉回路

如果都是偶数桥，从任意地方出发都能回到原点（欧拉回路）。

如果只有两个地方有奇数桥，可以从这两个地方之一出发，经过所有的桥一次，再回到另一个地方（欧拉路径）。如果有奇数桥的地方不止两个，满足要求的路径是找不到的。

寻找欧拉回路的思想

• 执行一次深度优先的搜索。从起始顶点开始，沿着这条路一直往下走，直到无路可走。而且在此过程中不允许回溯。

• 找出路径上的另外一个尚有未访问的边的顶点，开始另一次深度优先的搜索，将得到的遍历序列拼接到原来的序列中，直到所有的边都已被访问。

具体方法

• 检查存在性
• 找出回路：
  • 执行一次深度优先的搜索。
  • 从起始顶点开始，沿着这条路一直往下走，直到无路可走。而且在此过程中不允许回溯。
  • 路径上是否有一个尚有未访问的边的顶点。如果有，开始另一次深度优先的搜索，将得到的遍历序列拼接到原来的序列中，直到所有的边都已被访问。

欧拉回路的实现

拓扑排序

• 设G=（V，E）是一个具有n个顶点的有向无环图。
• V中的顶点序列V1，V2，…，Vn称为一个拓扑序列，当且仅当该序列满足下列条件：若在G中，从Vi到Vj有一条路径，则序列中Vi必须排在Vj的前面。
• 拓扑排序将图转化为线性序，相对前驱后继关系保持不变。

顶点活动网络（Activity On Vertex network）

• 顶点表示各项子任务（活动）
• 有向边表示具有先决条件关系，仅当作为某一子任务的所有作为先决条件的子任务实施完成后，该项子任务才能得以实施。
• AOV的特点：
  1. 有起始顶点
  2. 无回路

找出拓扑排序的过程

• 第一个输出的顶点（序列中的第一个元素）： 必须无前驱，即入度为0
• 后继：它的前驱全部输出之后才能输出。
• 无前驱及后继的顶点：任何时候都可输出。
• 逻辑删除法：
  • 当某个顶点被输出后，该顶点以及从该顶点出发的边都被删除，所有以该顶点作为前驱的所有顶点的入度减1。
  • 实现的时候，不需要真正去删边，只需要维护一个存储每个节点入度的数组，然后输出顶点时，将所有以该顶点作为前驱的所有顶点的入度减1即可

for example

• 有可能一次操作有多个节点的入度变成0，但实现的时候一次只能输出一个值，故使用一个队列来处理输出操作

拓扑排序的实现

• 计算每个顶点的入度，保存在数组inDegree中；
• 检查inDegree中的每个元素，将入度为0的顶点入队；
• 不断重复以下操作，直到队列为空
  • 从队列中将入度为0的顶点出队
  • 输出此顶点，并将该顶点的后继顶点的入度减1；
  • 如果某个邻接点的入度为0，则将其入队。

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>::topSort( ) const
{  
   linkQueue<int> q;
   edgeNode *p;
   int current, *inDegree = new int[Vers];
   for (int i = 0; i < Vers; ++i)   inDegree[i] = 0;
   for ( i = 0; i < Vers; ++i){
     for (p = verList[i].head; p != NULL; p = p->next)
	   ++inDegree[p->end];
   }//计算入度
   for (i = 0; i < Vers; ++i)
       if (inDegree[i] == 0) q.enQueue(i);//入度0节点入队
   cout << "拓扑排序为：" << endl;
   while( !q.isEmpty( ) ){
        current = q.deQueue( );
        cout << verList[current].ver << '\t';
        for (p = verList[current].head; p != NULL; p = p->next)
            if( --inDegree[p->end] == 0 )  q.enQueue( p->end );
    }//出队，删除关联的边
   cout << endl;
} 

时间复杂度分析

• 如果图以邻接表表示
• 总的执行时间也是O（|V|+|E|）
  • 计算入度需要O（|V|+|E|）的时间
  • 搜索入度为0的顶点需要O（|V|）的时间
  • 每个顶点入一次队、出一次队。每出一次队，需要检查它的所有后继顶点，因此也需要O（|V|+|E|）的时间。

关键路径

边活动网络AOE(Activity on Edge)

• AOE网络：加权有向无环图。
• 顶点表示事件，边表示活动，有向边的权值表示活动的持续时间，有向边的方向表示事件发生的先后次序。
• 顶点的进入边表示事件发生的条件
• 顶点的发出边表示事件发生后允许开始的活动。有一个源点、一个终点。

最早发生时间

• 设顶点x的最早发生时间记为ee(x)，边<u,v>的长度记为Luv；
• 首先设所有顶点的最早发生时间是0；
• 对每个被遍历的顶点u检查它的后继v。如果ee(u)+Luv > ee(v)，则更新ee(v)为ee(u)+Luv。终点的最早发生时间即关键路径的长度。

找关键路径的思路

• 计算每个顶点的活动时间余量：最迟发生时间-最早发生时间余量为0的顶点就是关键路径上的顶点
  • 最早开始时间：记为ee(x)，每个直接前驱的最早发生时间加上从该前驱到该顶点的活动时间的最大者
  • 最迟发生时间：记为le(x) ，每个直接后继的最迟发生时间减去顶点到该直接后继的活动时间的最小者就是该顶点的最迟发生时间。

关键路径算法

• 按照从头到尾遍历拓扑序列，计算每个顶点的最早发生时间；
• 按照从尾到头遍历逆向遍历拓扑序列，计算每个顶点的最迟发生时间；
• 从头到尾遍历拓扑序列，找出最早发生时间和最迟发生时间相等的顶点，组成关键路径。

最早发生时间计算方法

• 设顶点x的最早发生时间记为ee(x)，边<u,v>的长度记为Luv；
• 首先设所有顶点的最早发生时间是0；
• 对每个被遍历的顶点u检查它的后继v。如果ee(u)+Luv > ee(v)，则更新ee(v)为ee(u)+Luv。终点的最早发生时间即关键路径的长度。

最迟发生时间计算方法

• 设顶点x的最迟发生时间记为le(x)；
• 首先设所有顶点的最迟发生时间是关键路径的长度
• 对每个被遍历（从尾到头）的顶点u检查它的后继v。如果le(v) - Luv < le(u)，则更新le(u)为le(v)-Luv。

代码实现

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>
                                        ::criticalPath( ) const
{ 
    TypeOfEdge *ee = new TypeOfEdge[Vers],*le = new TypeOfEdge[Vers];
    int *top = new int[Vers], *inDegree = new int[Vers];      
    linkQueue<int> q;
    int i;
    edgeNode *p;
    // 找出拓扑序列，放入数组top
    for (i = 0; i < Vers; ++i) {      //计算每个结点的入度
	      inDegree[i] = 0;
	      for (p = verList[i].head; p != NULL; p = p->next)
		     ++inDegree[p->end]; 
    }
    for (i = 0; i < Vers; ++i)          //将入度为0的结点入队
	     if (inDegree[i] == 0) q.enQueue(i); 
    i = 0;
	while( !q.isEmpty( ) ) {
	      top[i] = q.deQueue( );		  
	      for (p = verList[top[i]].head; p != NULL; p = p->next)
               if( --inDegree[p->end] == 0 )    q.enQueue( p->end );
	       ++i;
     }
        // 找最早发生时间
   for (i = 0; i < Vers; ++i) ee[i] = 0;
   for (i = 0; i < Vers; ++i) {         // 找出最早发生时间存于数组ee
      for (p = verList[top[i]].head; p != NULL; p = p->next)
	   if (ee[p->end] < ee[top[i]] + p->weight )  
                 ee[p->end] = ee[top[i]] + p->weight; // ee(u)+Luv > ee(v)
    }

     // 找最晚发生时间
    for (i = 0; i < Vers; ++i) le[i] = ee[Vers -1];
    for (i = Vers - 1; i >= 0 ; --i)        // 找出最晚发生时间存于数组le
        for (p = verList[top[i]].head; p != NULL; p = p->next)
	   if(le[p->end] - p->weight < le[top[i]]  )
                    le[top[i]] = le[p->end] - p->weight; // le(v) - Luv < le(u)
    // 找出关键路径
    for (i = 0; i < Vers; ++i)
        if (le[top[i]] == ee[top[i]]) 
	   cout << "(" << verList[top[i]].ver 
                   << ",  " << ee[top[i]] << ")  ";
}