数据结构与算法-动态查找表

在这里插入图片描述

查找

🎈3动态查找表
- 🔭3.1二叉排序树
- - 🏆3.1.1二叉排序树的类定义
  - 🏆3.1.2二叉排序树的插入和生成
  - 🏆3.1.3二叉树的查找
  - 🏆3.1.4二叉排序树的删除
- 🔭3.2平衡二叉树
- - 🏆3.2.1平衡二叉树的调整方法
  - - 🎠RR型调整
    - 🎠LL型调整
    - 🎠RL型调整
    - 🎠LR型调整
  - 🏆3.2.2平衡二叉树的查找分析

🎈3动态查找表

🔭3.1二叉排序树

🔎二叉排序树，又称二叉查找树，其或者是一棵空树，或者是满足下列性质的二叉树：

若它的左子树不空，则左子树上所有元素的值均小于根结点元素的值。
若它的右子树不空，则右子树所有元素的值均大于根结点元素的值。
左右子树分别为二叉排序树。

上述定义要求查找表中没有相同关键字的数据元素。
📖根据二叉排序树的定义可知，对二叉排序树进行中序遍历可以得到一个有序序列。因此对于任意一个关键字序列构造一棵二叉排序树，其实质是对此关键字序列进行排序，使其变成有序序列。

🏆3.1.1二叉排序树的类定义

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
typedef int KeyType;
typedef int InfoType;
typedef struct
{KeyType key;//KeyType为关键字数据类型InfoType otherinfo;//其他域
}DElemType;
typedef struct BstNode
{DElemType data;BstNode* lchild, * rchild;
}BstNode;
class BsTree
{
private:BstNode* bst;void Insert(BstNode*& t, DElemType e);//二叉排序树中递归插入一个结点BstNode* Search(BstNode* t, KeyType key);//递归查找关键字key
public:BsTree()//构造函数，创建空的二叉排序树{bst = NULL;}BstNode* SearchBST(KeyType key);//查找关键字等于key的结点void InsertBST(DElemType e);//递归创建的二叉树传递给私有成员void CreatBiTree(DElemType d[], int n);//生成二叉排序树，n个数据在数组d中void DeleteBst(BstNode*& t, DElemType e);//删除二叉排序树中的一个结点void Deletep(BstNode*& p);/从二叉排序树中删除结点p,并重接它的左子树或右子树
};

🏆3.1.2二叉排序树的插入和生成

📖二叉排序树的插入操作应保证插入后仍满足二叉排序树的定义，新插入的结点总是叶子结点。其插入过程如下：

若二叉树t为空，则生成一个根结点。
将key于根结点的关键字比较，若keydata,则将key插入到根结点的左子树中，否则插入到根结点的右子树中。

void BsTree::Insert(BstNode*& t, DElemType e)
{if (t == NULL){t = new BstNode;t->lchild = t->rchild = NULL;t->data = e;return;}if (e.key < t->data.key)Insert(t->lchild, e);//在左子树插入结点eelseInsert(t->rchild, e);//在右子树插入结点e
}
void BsTree::InsertBST(DElemType e)
{BstNode* t = bst;Insert(t, e);bst = t;
}
void BsTree::CreatBiTree(DElemType d[], int n)
{for (int i = 0; i < n; i++){InsertBST(d[i]);}
}

🏆3.1.3二叉树的查找

📖由于二叉排序树按中序遍历可得有序序列，所以在二叉排序树中进行查找，与二分查找类似，也是一个逐步缩小查找范围的过程，查找的步骤如下：

若二叉树t为空，或key==t->data.key,则返回t。
否则将key与根结点的关键字比较，若key<t->datda.key,则递归查找左子树，否则递归查找右子树。

BstNode* BsTree::Search(BstNode* t, KeyType key)
{if (t == NULL || key == t->data.key)return t;else if (key < t->data.key)return Search(t->lchild, key);//查找左子树elsereturn Search(t->rchild, key);//查找右子树
}
BstNode* BsTree::SearchBST(KeyType key)
{BstNode* t = bst;return Search(t, key);
}

🏆3.1.4二叉排序树的删除

二叉排序树中删除结点的原则是：删除结点后仍是二叉排序树。
🔎设在二叉排序树被删除结点是p,其双亲结点是f.不失一般性，设p的左孩子或p为根结点。分三种情况讨论：

若p为叶子结点，则直接删除。如图a所示。
若p只有左子树pl或只有右子树pr，则令pl或pr直接成为双亲结点f的子树。如图b或c所示。

在这里插入图片描述

若被删除结点p既有左子树pl又有右子树pr,则在pl中选值最大的代替p,该数据按二叉排序树的性质应在左子树的最右下结点。

void BsTree::DeleteBst(BstNode*& t, DElemType e)
{if (!t)return;else{if (e.key == t->data.key)Deletep(t);else if (e.key < t->data.key)DeleteBst(t->lchild, e);elseDeleteBst(t->rchild, e);}
}
void BsTree::Deletep(BstNode*& p)
{if (!p)return;BstNode* s, * q;if (p->rchild == NULL){q = p;p = p->lchild;delete q;}else if (p->lchild == NULL){q = p;p = p->rchild;delete q;}else {q = p;s = p->lchild;while (s->rchild != NULL){q = s;s = s->rchild;}p->data = s->data;if (q != p)q->rchild = s->lchild;elseq->lchild = s->rchild;delete s;}
}