1. 前言
本系列笔记基于 清华大学出版社的《数据结构：用面向对象方法与C++语言描述》第二版进行学习。
2. 概念
使用基于关键码的搜索，搜索结果应该是唯一的。使用基于属性的搜索方法，搜索结果可能不唯一。
搜索的环境有两种，静态环境和动态环境。区别在于插入和删除后搜索结构会不会变化。
衡量搜索的时间效率的标准是：
在搜索过程中关键码的平均比较次数或平均读写磁盘次数，成为平均搜索长度ASL。
3 静态搜索结构
3.1 静态搜索表
最简单的基于数组的数据表类。
#include <iostream>
#include<assert.h>
using namespace std;
const int defaultSize = 100;
class dataList;
class dataNode {
friend class dataList;
public:
dataNode(const int x = 99):key(x),data(0){
}
int getKey() const {
return key; }
void setKey(int k) {
key = k; }
private:
int key; // 关键码
int data;
};
class dataList {
public:
dataList(int sz = defaultSize) :ArraySize(sz), CurrentSize(0) {
Element = new dataNode[sz];
assert(Element != NULL);
}
dataList(dataList& R);
virtual ~dataList() {
delete[]Element; }
virtual int Length() {
return CurrentSize; }
virtual int getKey(int i)const {
// 提取第i个元素值（从1开始）
assert(i > 0 || i <= CurrentSize);
return Element[i - 1].key;
}
virtual void setKey(int x, int i) {
// 修改第i个元素的值
assert(i > 0 || i <= CurrentSize);
Element[i - 1].key = x;
}
virtual int SeqSearch(const int x) const; // 搜索
virtual bool Insert(int& e1); // 插入
virtual bool Remove(const int x, int& e1); // 删除
friend ostream& operator<<(ostream& out, const dataList& OutList);
friend ostream& operator>>(istream in, dataList& InList);
protected:
dataNode* Element;
int ArraySize;
int CurrentSize;
};
class searchList :public dataList {
public:
searchList(int sz = defaultSize) :dataList(sz){
}
virtual int SeqSearch(const int x)const;
};
int main()
{
std::cout << "Hello World!\n";
}
bool dataList::Insert(int& e1)
{
if (CurrentSize == ArraySize) return false; // 表满，无法插入
Element[CurrentSize] = e1;
CurrentSize++;
return true;
}
bool dataList::Remove(const int x, int& e1)
{
if (CurrentSize == 0)return false;
int i;
for (i = 0; i < CurrentSize && Element[i].key != x; i++);
if (i == CurrentSize) return false;
e1 = Element[i].data;
Element[i] = Element[CurrentSize - 1];
CurrentSize--; return true;
}
ostream& operator<<(ostream& out, const dataList& OutList)
{
cout << "Array Contents:\n";
for (int i = 1; i < OutList.CurrentSize; i++) {
cout << OutList.CurrentSize;
i++;
}
cout << endl;
cout << "Array Current Size:" << OutList.CurrentSize << endl;
return out;
}
ostream& operator>>(istream in, dataList& InList)
{
cout << "Enter array Current Size:" << endl;
in >> InList.CurrentSize;
cout << "Enter array Elements:\n";
for (int i = 1; i <= InList.CurrentSize; i++) {
cout << "Element" << i << ":";
in >> InList.Element[i - 1];
}
return in;
}
编译不过，因为Elements中没有设置接触到数据的函数，可以自行添加
3.2 顺序搜索表
int searchList::SeqSearch1(const int x, int loc) const
{
if (loc > CurrentSize) return 0;
else if (Element[loc - 1].key == x) return loc;
else return SeqSearch1(x, loc + 1);
}
3.2.1 基于有序顺序表和顺序搜索和折半搜索
①顺序搜索
class SortedList : public searchList {
public:
SortedList(int sz=100):searchList(sz){
}
~SortedList(){
}
int SequentSearch(const int x)const; // 顺序搜索
int BinarySearch(const int x)const; // 折半搜索
bool Insert(const int& e1); // 插入
int Begin() {
return (CurrentSize == 0) ? 0 : 1; } // 定位第一个
int Next(int i) {
return(i >= 1 && i <= CurrentSize) ? i + 1 : 0; } // 定位下一个
};
int SortedList::SequentSearch(const int x) const
{
for (int i = 1; i <= CurrentSize; i++)
if (Element[i - 1].key == x) return i; // 成功，停止搜索
else if (Element[i - 1].key > x)break; // 不成功，停止搜索
return 0;
}
②折半搜索
折半搜索又称二分搜索法
非递归算法
int SortedList::BinarySearch(const int x) const
{
// 非递归算法
int high = CurrentSize - 1;
int low = 0;
int mid;
while (low <=high) // 如果没有，最后搜索的一次是low<=high
{
mid = (low + high) / 2;
if (x > Element[mid].key) low = mid + 1; // 把中间的元素的后一位变成low
else if (x < Element[mid].key) high = mid - 1; // 把中间元素的前一位变成high
else return mid + 1;
}
return 0;
}
递归算法
int SortedList::BinarySearch1(const int x, int low, int high) const
{
int mid = 0;
if (low <= high) {
mid = (low + high) / 2;
if (x > Element[mid - 1].key)
mid = BinarySearch1(x, mid + 1, high);
else if (x < Element[mid - 1].key)
mid = BinarySearch1(x, low, mid - 1);
}
return mid;
}
③插入算法
void SortedList::Insert(const dataNode& e1)
{
assert(CurrentSize == ArraySize);
int i = 1;
while (i <= CurrentSize && Element[i - 1].key <= e1.key)i++; // 找到小于插入的结点的最大的结点
for (int j = CurrentSize; j >= i; j--) Element[j] = Element[j - 1]; // 前面的赋值给另一个
Element[i - 1] = e1;
CurrentSize ++;
}
4 二叉搜索树
简单来说,就是如果找到二叉树的中序遍历,他的中序遍历一定是从小到大排序的
如上图,其中序遍历均位123
4.1 搜索二叉树的类定义
struct BSTNode
{
int data; // 二叉树节点类
BSTNode* left, * right; // 左右子女
BSTNode():left(NULL),right(NULL){
}
BSTNode(const int d, BSTNode* L = NULL, BSTNode*R =NULL):data(d),left(L),right(R){
}
~BSTNode(){
}
void SetData(int d) {
data = d; }
int getData() {
return data; }
};
class BST {
public:
BST() :root(NULL) {
}
BST(int Value);
~BST() {
};
bool Search(const int x) {
return (search(x, root) != NULL) ? true : false;
}
BST& oprator = (const BST & R); // 赋值
void makeEmpty() {
makeEmpty(root); root = NULL; }
void PrintTree()const {
PrintTree(root); }
int Min() {
return Min(root)->data; }
int Max() {
return Max(root)->data; }
bool Insert(const int& e1) {
return Insert(e1, root); }
bool Remove(const int x) {
return Remove(x, root); }
private:
BSTNode* root;
int RefValue; // 停止标志
BSTNode* search(const int x, BSTNode* ptr); // 搜索
void makeEmpty(BSTNode*& ptr); // 置空
void PrintTree(BSTNode* ptr)const; // 打印
BSTNode* Copy(const BSTNode* ptr); // 复制
BSTNode* Min(BSTNode* ptr)const; // 求最小
BSTNode* Max(BSTNode* ptr)const; // 求最大
bool Insert(const int& e1, BSTNode*& ptr); // 递归插入
bool Remove(const int x, BSTNode*& ptr); // 删除
};
4.2 搜索二叉树的搜索
超级好理解
BSTNode* BST::search(const int x, BSTNode* ptr)
{
if (ptr == NULL) return NULL;
else if (x < ptr->data) return search(x, ptr->left);
else if (x > ptr->data) return search(x, ptr->right);
else return ptr;
}
4.3 搜索二叉树的插入
bool BST::Insert(const int& e1, BSTNode*& ptr)
{
if (ptr == NULL) {
ptr = new BSTNode(e1);
if (ptr = NULL) {
cout << "out of space" << endl; exit(1); }
}
else if (e1 < ptr->data) Insert(e1, ptr->left); // 比结点小存左边
else if (e1 > ptr->data)Insert(e1, ptr->right); // 比节点小存右边
else return false;
}
4.4 搜索二叉树的删除
bool BST::Remove(const int x, BSTNode*& ptr)
{
BSTNode* temp;
if (ptr != NULL) {
if (x < ptr->data) Remove(x, ptr->left); // 左子树执行删除
else if (x > ptr->data) Remove(x, ptr->right); // 在右子树执行删除
else if (ptr->left != NULL && ptr->right != NULL) {
// 有两个子女节点
temp = ptr->right; // 右子树搜寻中序的第一个结点
while (temp->left != NULL) temp = temp->left;
ptr->data = temp->data; // 用该节点数据代替根节点数据
Remove(ptr->data, ptr->right);
}
else {
// 只有一个子女结点（左子结点或右子结点） 这部分是为了链接删除部分缺掉的那条线
temp = ptr;
if (ptr->left == NULL) ptr = ptr->right;
else ptr = ptr->left;
delete temp;
return true;
}
}
return false;
}
5 AVL树
任一结点的右子树的高度减去左子树的高度差只能为-1，0，1
5.1 平衡化旋转
使不平衡的二叉搜索树变得平衡
先说插入
这里有四种情况
5.1.1 右旋：LL型状态
就是插入根节点的子结点的左子结点，
右旋相当于把树往顺时针旋转以下，把B点做成根结点，再把B结点的右子结点变成原根节点的左子节点，
旋转后变成：
5.1.2 左旋：RR型状态
左旋和右旋差不多，就是插入了根节点的右子结点的右子树中。
左旋相当于将整个树逆时针旋转了一下，将C点置为根结点，然后将A点作为C点的左子树，把原来的左子树3作为原根节点的右子树
5.1.3 右旋(LL)的例子
本次是插入0到原来的平衡树中，如图，属于LL情况，所以进行右旋操作。
找到不平衡的根结点4。所以我们要调整的树就是
将原有的左子树，以2为根节点的树往上提，作为这棵树的新根节点，并把原有根节点4作为2的右子树，把2的原右子变为原根节点4的左子树
再把2作为原来根节点4，进行连接
5.1.4 先左旋再右旋(LR)的操作
元素落到56都是一样的处理，把
D转换成新的根结点，把原有不平衡树的根节点A的左子女结点作为D的左子女结点，根节点A作为D的右子女结点。并把D的左子树当作B的右子树，把D的右子树当作A的左子树。
5.1.5 先右旋再左旋(RL)的操作
插入56所作的操作都一样，原理与LR差不多，把D作为新的根节点，把不平衡树的根节点A作为D的左子树，A的右子女结点C作为D的右子树。并把D的左子树转换成A的右子树，D的右子树转换为C的左子树。
5.1.6 RL操作的例子
把4当作新父结点，将不平衡树的根节点2作为4的左子树，根节点的右结点5作为4的右子树。把4的左子树赋给2作为其右子女结点。
结果
5.1.7 代码实现
void AVLTree::RotateL(AVLNode*& ptr)
{
// 右子树高RR型状态
AVLNode* subL = ptr; // 要旋转的结点，即不平衡的树的根结点
ptr = subL->right; // 原根节点的右结点
subL->right = ptr->left; // 原根子树的右子女转化成其右结点的左子树
ptr->left = subL; // 把原根节点作为原根节点右结点的左子树，此时ptr为新根节点
ptr->bf = subL->bf = 0;
}
void AVLTree::RotateR(AVLNode*& ptr)
{
// 左子树高LL型状态
AVLNode* subR = ptr;
ptr = subR->left;
subR->left = ptr->right;
ptr->right = subR;
ptr->bf = subR->bf = 0;
}
void AVLTree::RotateRL(AVLNode*& ptr)
{
AVLNode* subL = ptr; // 最后根节点的左子树
AVLNode* subR = subL->right; // 最后根节点的右子树
ptr = subR->left;
subR->left = ptr->right; // subR的左子树变为其左子女节点的左子女节点
ptr->right = subR; // 新根节点的右子女结点变为最终右子女结点
if (ptr->bf >= 0) subR->bf = 0;
else subR->bf = 1;
subL->right = ptr->left; // subL的右子女变为新根节点的左子女结点
ptr->left = subL; // 新根结点的变为最终的左子女结点
if (ptr->bf == 1) subL->bf = -1;
else subL->bf = 0;
ptr->bf = 0;
}
void AVLTree::RotateLR(AVLNode*& ptr)
{
AVLNode* subR = ptr;
AVLNode* subL = subR->left;
ptr = subL->right;
subL->right = ptr->left;
ptr->left = subL;
if (ptr->bf <= 0) subL->bf = 0;
else subL->bf = -1;
subR->left = ptr->right;
ptr->right = subR;
if (ptr->bf = -1) subR->bf = 1;
else subR->bf = 0;
ptr->bf = 0;
}
5.2 AVL树的插入
沿着其插入路线查各结点的平衡度
各结点会有三种情况
①bf = 0，不需要处理，结束平衡化
②bf = 1，不需要处理，继续回溯
③bf = 2，bf = 2，右子树高，需要结合右子女q的bf做处理
1）q的bf = 1，执行左单旋转，插入位置为RR
2）q的bf=-1，执行先右后左旋转，插入位置为RL
bf=-2，左子树高，需要结合左子女q的bf做处理
1）q的bf=1，执行右单旋转，插入位置为LL
2) q的bf=-1，执行先右旋后左旋，插入位置为LR
bool AVLTree::Insert(AVLNode*& ptr, int& e1)
{
AVLNode* pr = NULL;
AVLNode* p = ptr;
AVLNode* q;
int d;
Stack st;
while (p!=NULL)
{
if (e1 == p->data) return false; // 找到了e1的结点，不插入
pr = p;
st.push(pr); // 用栈记录查找路径，并找到插入的父结点pr
if (e1 < p->data) p = p->left;
else p = p->right;
}
p = new AVLNode(e1);
if (p == NULL) {
cout << "error when allocate memory!"; exit(1); }
if (pr == NULL) {
ptr = p; return true; }
if (e1 < pr->data) pr->left = p;
else pr->right = p; // 新结点插入
while (st.Isempty() == false) {
// 重新平衡化
st.Pop(pr); // 调查父结点的平衡因子
if (p == pr->left) pr->bf--; // 如果插入左边，则平衡因子-1
else pr->bf++; // 插入右边则+1，平衡因子高度右边-左边
if (pr->bf == 0) break; // 第一种情况，平衡退出
if (pr->bf == 1 || pr->bf == -1)
p = pr; // 第二种情况，继续向上搜寻
else {
// 第三种情况，|bf| =2;
d = (pr->bf < 0) ? -1 : 1; // 区别单双旋
if (p->bf == d) {
// 两节点的平衡因子同号，单旋转
if (d == -1) RotateR(pr); // bf ==-1
else RotateL(pr); // bf =1
}
else {
if (d == -1) RotateLR(pr);
else RotateRL(pr);
}
break;
}
if (st.IsEmpty() == true) ptr = pr; // 调整到树的根节点
else {
st.getTop(q);
if (q->data > pr->data) p->left = pr;
else q->right = pr;
}
}
return true;
}
这是>>和<<的重载：
istream& operator>>(istream in, AVLTree& Tree)
{
int item;
cout << "Construct AVL tree:\n";
cout << "Input Data(end with" << Tree.RefValue << "):";
in >> item;
while (item != Tree.RefValue) {
Tree.Insert(item);
cout << "Input Data(end with" << Tree.RefValue << "):";
in >> item;
}
return in;
}
ostream& operator<<(ostream& out, const AVLTree& Tree)
{
out << "Inorder Traversal of AVL tree.\n";
Tree.Traverse(Tree.root, out); // 以中序次序输出个各节点的数据
out << endl;
return out;
}
看懂这个基本就学会了插入了
5.3 AVL树的删除
AVL树的删除算法与二叉搜索树类似，删除后如果破坏平衡性质，还需要做旋转
（1）如果被删结点p有两个子女，p的中序次序下找到直接前驱q，把q的内容传给p，把结点q当作被删结点p，他是只有一个子女的结点，此时看第二种情况
（2）如果被删结点p最多只有一个子女q。可以当p的父结点pr中原来指向p的指针改到q，如果结点p没有子女，p父结点pr的相应指针置位NULL。将原来的结点pr为根的子树的高度-1，并沿pr通向根的路径考量一路上各个结点的影响。
考查结点q的父结点pr。如果q是pr的左子女，则因子bf+1,否则bf-1
此时有三种情况
【1】bf的原来的平衡因子为0，则不需要调整了，结束重新平衡
【2】bf不为0，需要考察结点pr的父结点的平衡状态，
【3】需要平衡化
考察父结点pr的更高的子树的根为q（未被缩短的树），根据q的平衡因子，有三种操作
①如果q的平衡因子为0，执行一个单旋（未被缩短的树，结束后可以结束平衡的过程
②如果q的平衡因子与pr的平衡因子正负号相同，则执行一个单旋来恢复，结束后需要沿上继续评估平衡状态，相当LL型和RR型
③如果pr与q的平衡因子正负号相反，则需要执行双旋q，相当于LR和RL型，同时继续向上评估
bool AVLTree::Remove(AVLNode*& ptr, int x, int& e1)
{
// 删除关键码为x的结点
AVLNode* pr = NULL;
AVLNode *p = ptr;
AVLNode* q;
AVLNode* ppr;
int d;
int dd = 0;
Stack* st;
while (p != NULL) {
// 寻找删除位置
if (x == p->data) break;
pr = p;
st.push(pr);
if (x < p->data) p = p->left;
else p = p->right;
}
if (p == NULL) return false; // 未找到，删除
if (p->left != NULL && p->right != NULL) {
// 有两各子女的情况
pr = p;
st.push(pr);
q = p->left; // 再p左子树找到中序遍历直接前驱
while (q->right != NULL) {
pr = q;
st.push(pr);
q = q->right;
}
p->data = q->data; // 用q的值填补p
p = q; // 被删结点转为q，此时是只有一个子女结点q的情况
}
if (p->left != NULL) q = p->left; // 被删结点只有一个子女
else q = p->right; // 找到这个子女
if (pr == NULL) ptr = q; // 被删结点为根节点
else {
// 被删结点不是根节点
if (pr->left == p) pr->left = q; // 把父结点连接到被删结点的子女结点
else pr->right = q;
while (st.IsEmpty()== false) // 重新平衡化
{
st.Pop(pr);
if (pr->right == q) pr->bf--; // 调整父结点的平衡因子
else pr->bf++;
if (st.IsEmpty() == false) {
st.getTop(ppr);
dd = (ppr->left == pr) ? -1 : 1; // 旋转后和上层连接方向
}
else dd = 0; // 旋转后不与上层连接
if (pr->bf == 1 || pr->bf == -1) break; // 不需要旋转，直接退出
if (pr->bf != 0) {
if (pr->bf < 0) {
d = -1; q = pr->left; }
else {
d = 1; q = pr->right; }
if (q->bf == 0) {
if (d == -1) {
RotateR(pr);
pr->bf = 1;
pr->left->bf = -1;
}
else {
RotateL(pr);
pr->bf = -1;
pr->right->bf = 1;
}
break;
}
if (q->bf == d) {
if (d == -1) RotateR(pr);
else RotateL(pr);
}
else {
if (d == -1) RotateLR(pr);
else RotateRL(pr);
}
if (dd == -1) ppr->left = pr;
else if (dd == 1) ppr->right = pr;
}
q = pr;
}
if (st.IsEmpty() == true) ptr = pr;
}
delete p;
return true;
}
不懂这段代码，真的很痛苦看的我
6 伸展树
每次插入结点，所有结点都要调整到根结点。
伸展树
6.1 插入
插入位置为根的左节点，右旋
插入位置为根的右结点，左旋
最左边LL情况，对中间结点进行右旋，在对结点进行右旋，直到变成根节点
最右边RR情况，对中间结点进行左旋，在对结点进行左旋，直到变成根节点
LR情况，中间结点先左旋后右旋，再对结点左旋右旋，直到变为根节点
RL情况，中间结点先右旋后左旋，再对结点右旋左旋，直到变为根节点
6.2 查找
插入和查找操作，查找后把查找到的结点变为根节点，情况跟插入类似
6.3 删除
和二叉搜索树相同，但需要把被删除结点的父结点展开到根节点。
7 红黑树
1）外部结点是黑色（空指针们
2）没有两个连续结点是红色，（可以两个连续结点是黑色
3）根到外部节点的路径上都有相同的黑色结点
也可以从指针看
7.1 红黑树搜索
和二叉搜索树完全相同
7.2 插入和删除
这个书上标**了，我这边先不学，看了下内容挺多的，后面再补
