目录
二叉搜索树
概念：
二叉搜索树又称二叉排序树，它或者是一颗空树，或者是具有以下性质的二叉树：
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
- 它的左右子树也分别为二叉搜索树。
二叉搜索树的操作：
1、二叉搜索树的查找
2、二叉搜索的插入
1、树为空，直接插入
2、树不为空
①按照二叉搜索树的性质查找插入的位置（要标记当前访问的节点的双亲，否则找到了插入位置，却无法访问节点的双亲结点）
②插入新节点（判断新插入节点（node）的值与parent标记的节点值的大小关系）
3、二叉搜索树的删除：
1、找到待删除节点，并标记其双亲。
2、删除该节点。
①待删除的节点是叶子节点
? ? ? ? 可以直接删除
②待删除的节点只有左孩子
- ?双亲存在
- 双亲不存在
③待删除节点只有右孩子
④待删除节点左右孩子均存在，该情况无法直接删除，需要在其子树中寻找替代节点(替代节点可以是左子树的最大值或者右子树的最小值)。具体步骤：
- 找替代节点：在待删节点的右子树找最左侧的节点并保存其双亲。
- 将替代节点中的值域赋值给待删除节点。
- 将替代节点删除掉。
4、代码实现
#include<iostream>
using namespace std;
template<class T>
struct BSNode {
BSNode* _left;
BSNode* _right;
T _value;
BSNode(const T& val)
:_left(nullptr)
,_right(nullptr)
,_value(val){}
};
template<class T>
class BSTree {
typedef BSNode<T> node;
public:
BSTree()
:_root(nullptr){}
~BSTree() {
destory(_root);
}
node* insert(const T& val) {
//1、空树
if (_root == nullptr) {
_root = new node(val);
return _root;
}
//2、非空
/*
*1、寻找合法的插入位置，并且保存其双亲
*2、将新节点插入该位置
*/
node* cur = _root;
node* parent = nullptr;
while (cur) {
parent = cur;
if (val > cur->_value) {
cur = cur->_right;
}
else if(val < cur->_value){
cur = cur->_left;
}
else {
return cur; //默认二叉树中没有值相同的节点
}
}
cur = new node(val);
if (val > parent->_value) {
parent->_right = cur;
}
else {
parent->_left = cur;
}
return cur;
}
node* find(const T& value) {
if (_root) {
node* cur = _root;
while (cur) {
if (value < cur->_value) {
cur = cur->_left;
}
else if (value > cur->_value) {
cur = cur->_right;
}
else {
return cur;
}
}
}
return nullptr;
}
bool erase(const T& value) {
if (_root == nullptr) return false;
//1、找待删除节点在搜索树中的位置，并标记其双亲
node* delNode = _root;
node* parent = nullptr;
while (delNode) {
if (value < delNode->_value) {
parent = delNode;
delNode = delNode->_left;
}
else if (value > delNode->_value) {
parent = delNode;
delNode = delNode->_right;
}
else {
break;
}
}
if (delNode == nullptr) return false; //待删除节点不存在
//2、分情况删除
if (delNode->_right == nullptr) {
//此时存在两种情况：①只有左子树 ②为叶子节点
//该节点为根节点
if (parent == nullptr) {
_root = delNode->_left;
}
else {
//不为根节点
if (delNode == parent->_left) {
parent->_left = delNode->_left;
}
else {
parent->_right = delNode->_left;
}
}
}
else if (delNode->_left == nullptr) {
//此时待删除节点只有右子树
if (parent == nullptr) {
_root = delNode->_right;
}
else {
if (delNode == parent->_left) {
parent->_left = delNode->_right;
}
else {
parent->_right = delNode->_right;
}
}
}
else {
//此时待删除的节点左右子树存在
/*
1、找到替代的节点，并记录其双亲（替代节点可以是左子树中的最大值，也可以是右子树最小值）
2、将替代节点的值赋给待删除节点
3、删除替代节点
*/
node* ReplaceNode = delNode->_right; //找右子树的最小值(此时替代节点可能是一个叶子节点，也可能是一个只有右子树的节点)
parent = delNode;
while (ReplaceNode->_left) {
parent = ReplaceNode;
ReplaceNode = ReplaceNode->_left;
}
delNode->_value = ReplaceNode->_value;
if (parent->_left == ReplaceNode) {
parent->_left = ReplaceNode->_right;
}
else {
parent->_right = ReplaceNode->_right;
}
delNode = ReplaceNode;
}
delete delNode;
delNode = nullptr;
return true;
}
void Inorder() {
inorder(_root);
cout << endl;
}
private:
void destory(node* root) {
if (root) {
destory(root->_left);
destory(root->_right);
delete root;
root = nullptr;
}
}
void inorder(node* _root) {
if (_root == nullptr) return;
inorder(_root->_left);
cout << _root->_value << ' ';
inorder(_root->_right);
}
private:
node* _root;
};
AVL树
什么是AVL树？
1、AVL树可以是一颗空树
2、AVL树也可以是一颗具有如下性质的二叉搜索树：
- 它的左右子树都是一颗AVL树
- 左右子树高度之差（平衡因子）的绝对值不能超过1
模拟实现：
1、节点定义：
AVL树本质上时一颗二叉搜索树，只不过加上了平衡因子这一限制条件。
也就是说，在插入一个新节点时，我们不仅要考虑节点的插入位置，还需要考虑插入该节点后对于树中其他节点来说平衡因子时候需要更新。
插入节点的父节点，它的平衡因子一定需要改变。这就要求我们需要能够快速定位到插入节点的父节点。因此，我们对于AVL树节点的结构应定义为孩子双亲表示法。
template<class T>
struct AVLTreeNode {
typedef AVLTreeNode<T> Node;
Node* _left;
Node* _right;
Node* _parent;
T _value;
int _bf; //平衡因子
AVLTreeNode(const T& value)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_value(value)
._bf(0){}
};?2、插入
AVL树的插入可以分为两大步骤：
一、按照二叉搜索树的方式插入新节点
二、调整节点的平衡因子
? ? ? ? 首先，新节点插入之后，其双亲节点的平衡因子一定需要更新，因为插入一个节点，则该节点一定会影响其双亲的左右子树高度。因此，我们首先将双亲节点的平衡因子进行更新：如果插入到parent的左侧，对parent--；如果插入到parent的右侧，对平衡因子++。对parent更新完毕后，parent的平衡因子可能取的值为：?0、正负1、正负2
1、parent的平衡因子为0
该情况说明插入之前parent的平衡因子为正负1，插入之后被调整为0，此时满足AVL树的性质，插入成功。
2、parent的平衡因子为正负1
该情况说明插入之前parent的平衡因子一定是0（也就是说以parent为根的二叉树左右子树高度是一样的），插入后被更新为正负1，此时以parent为根的树高度增加了，势必会影响到parent上面节点的平衡因子，因此需要继续向上更新。
3、parent的平衡因子为正负2
这种情况较为复杂。首先，我们知道此时parent的平衡因子违反了AVL树的特性，因此需要对其进行旋转处理。至于如何旋转，有以下四种场景：
场景一：新节点插入在较高左子树的左侧------>右单旋
如图：
①节点30的左孩子一定存在，右孩子可能存在，也可能不存在
②节点60可能是根节点，也可能不是
? ? ? ? 如果是，那么旋转完毕后需要更新根节点
? ? ? ? 如果不是，那它有可能是双亲节点的左孩子或者右孩子。
场景二：新节点插入在较高右子树的右侧------>左单旋?
如图：
场景三：新节点插入在较高左子树的右侧---->左右双旋?
如图：
场景四：新节点插入在较高右子树的左侧------>右左双旋
?
3、验证：
①验证是否是一颗二叉搜索树：查看中序遍历结果，若有序，则为二叉搜索树
②验证他是否是一颗平衡树：每个节点的高度差不超过1
代码?
#include<iostream>
using namespace std;
#if 1
template<class T>
struct AVLTreeNode {
typedef AVLTreeNode<T> Node;
Node* _left;
Node* _right;
Node* _parent;
T _value;
int _bf; //平衡因子
AVLTreeNode(const T& value)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_value(value)
,_bf(0){}
};
template<class T>
class AVLTree {
typedef AVLTreeNode<T> Node;
public:
AVLTree() {
_root = nullptr;
}
bool insert(const T& value) {
#if 1
if (_root == nullptr) {
_root = new Node(value);
return true;
}
//1.按照二叉搜索树的方式查找节点的插入位置，和二叉搜索树的操作相同
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
parent = cur;
if (value < cur->_value) {
cur = cur->_left;
}
else if (value > cur->_value) {
cur = cur->_right;
}
else {
return false;
}
}
cur = new Node(value);
if (value < parent->_value) {
parent->_left = cur;
}
else {
parent->_right = cur;
}
cur->_parent = parent;
//2、调整平衡因子
while (parent) {
if (cur == parent->_left) {
parent->_bf--;
}
else {
parent->_bf++;
}
if (parent->_bf == 0) {
//以parent为根的二叉树高度没有发生变化，不影响到上层的其他节点
break;
}
else if (parent->_bf == 1 || parent->_bf == -1) {
//此时以parent为根的二叉树的高度增加了，需要继续向上更新
cur = parent;
parent = cur->_parent;
}
else {
//parent的平衡因子可能是2或者-2，违反了AVL树的性质，需要旋转处理
if (parent->_bf == 2) {
//parent的右子树高，需要左旋转
if (cur->_bf == 1) {
RolateLeft(parent);
}
else {
RolateRL(parent);
}
}
else {
//parnet的左子树高，最终需要右旋
if (cur->_bf == -1) {
RolateRight(parent);
}
else {
RolateLR(parent);
}
}
break;
}
}
return true;
#endif
}
~AVLTree() {
destory(_root);
}
void InOrder() {
InOrder(_root);
}
bool isAVLTree() {
return _isAVLTree(_root);
}
private:
//左单旋
void RolateLeft(Node* parent) {
#if 1
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) {
subRL->_parent = parent;
}
subR->_left = parent;
//更新subR和parent的双亲
Node* pparent = parent->_parent;
parent->_parent = subR;
if (pparent == nullptr) {
_root = subR;
}
else {
if (pparent->_left == parent) {
pparent->_left = subR;
}
else {
pparent->_right = subR;
}
}
//更新subR和parent的平衡因子
subR->_bf = parent->_bf = 0;
#endif
}
//右单旋
void RolateRight(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR) {
subLR->_parent = parent;
}
Node* pparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
subL->_parent = pparent;
if (pparent == nullptr) {
_root = subL;
}
else {
if (parent == pparent->_left) {
pparent->_left = subL;
}
else {
pparent->_right = subL;
}
}
parent->_bf = subL->_bf = 0;
}
//左右双旋
void RolateLR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RolateLeft(parent->_left);
RolateRight(parent);
if (1 == bf) {
subL->_bf = -1;
}
else if (-1 == bf) {
parent->_bf = 1;
}
}
//右左双旋
void RolateRL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RolateRight(subR);
RolateLeft(parent);
if (bf == 1) {
parent->_bf = -1;
}
else if(bf == -1){
subR->_bf = 1;
}
}
void InOrder(Node* root) {
if (root == nullptr) {
return;
}
InOrder(root->_left);
cout << root->_value << ' ';
InOrder(root->_right);
}
void destory(Node*& root) { //注意：需要传引用
if (root == nullptr) {
return;
}
destory(root->_left);
destory(root->_right);
delete(root);
root = nullptr;
}
//验证是否是一颗AVL树
int GetHigh(Node* root) {
if (root == nullptr) {
return 0;
}
int Llen = GetHigh(root->_left);
int Rlen = GetHigh(root->_right);
return Llen > Rlen ? Llen + 1 : Rlen + 1;
}
bool _isAVLTree(Node* root) {
if (root == nullptr) {
return true;
}
int Llen = GetHigh(root->_left);
int Rlen = GetHigh(root->_right);
if (Rlen - Llen != root->_bf || abs(root->_bf) > 1) {
cout << "Node:" << root->_value << endl;
cout << Rlen - Llen << " " << root->_bf << endl;
return false;
}
return _isAVLTree(root->_left) && _isAVLTree(root->_right);
}
private:
Node* _root;
};
#endif