二叉搜索树
定义
一棵二叉搜索树需要满足以下条件：
- 是一棵二叉树
- 对于树中任意节点，所有左子树元素都小于该节点，所有右子树元素都大于等于该节点
bst.png
上图就是一棵，二叉搜索树。每个二叉搜索树的节点还包含属性left、right、parent，分别指向它的左、右孩子和父节点。
性质
中序遍历
对二叉搜索树进行一次中序遍历，可以按顺序输出每个元素值。
二叉搜索树操作
二叉搜索树支持以下操作：
- search - 查找元素
- minimum - 查找最小元素值
- maximum - 查找最大元素值
- successor - 找指定元素的前驱元素
- predecessor - 找指定元素的后继元素
- insert - 插入元素
- delete - 删除元素
查找
查找指定元素
由于二叉搜索树的性质，可以在O(h) (h为树的高度)时间内找到元素。
树的节点结构和树表示如下：
typedef int Tp;
typedef struct TNode {
Tp data;
TNode* parent;
TNode* left;
TNode* right;
}TNode;
class BinSearchTree {
private:
typedef TNode* Root_ ;
Root_ root_ = nullptr;
...
};
对元素进行搜索，若目标元素大于当前元素，则搜索当前节点的右子树，否则搜索左子树：
TNode* BinSearchTree::TreeSearch(Tp key) {
TNode* p = root_;
while (p) {
if (p->data == key) {
return p;
}
else if (key < p->data) {
p = p->left;
}
else {
p = p->right;
}
}
return nullptr;
}
找最小、最大值
根据二叉搜索树的性质，最小值为最左节点。
/**
* @brief 寻找最小节点
*
*/
TNode* BinSearchTree::TreeMinimumHelper(Root_ t) {
while (t->left) {
t = t->left;
}
return t;
}
同理最大值为树的最右节点
前驱节点
寻找目标节点的前驱节点分为两种情况：
-
目标节点存在左子树，前驱为：该左子树的最大值。例如 ，15的前驱为13。
-
目标节点不存在左子树，前驱为：第一个使得
目标节点成为为右子树中元素的祖先节点.。例如，17的前驱为15，因为15是17的第一个祖先元素，使得17成为右子树元素。
search.png
/**
* @brief 寻找指定节点的前驱节点
*/
TNode* BinSearchTree::TreePredecessorHelper(TNode* p) {
if (p->left) {
return TreeMaximumHelper(p->left);
}
TNode* pre = p->parent;
while (pre && p == pre->left) {
p = pre;
pre = pre->parent;
}
return pre;
}
后继节点
后继节点的寻找，与前驱类似，为前驱的相反情况
/**
* @brief 寻找指定节点的后继节点
*/
TNode* BinSearchTree::TreeSuccessorHelper(TNode* p) {
if (p->right) {
return TreeMinimumHelper(p->right);
}
TNode* next = p->parent;
while (next && p == next->right) {
p = next;
next = next->parent;
}
return next;
}
插入、删除
插入
插入相对删除比较简单
步骤：
- 根据要插入数据的值，找到插入的位置。
- 插入元素
void BinSearchTree::TreeInsert(Tp key) {
TNode* node = new TNode;
node->data = key;
node->parent = nullptr;
node->left = nullptr;
node->right = nullptr;
TNode* pre = nullptr;
TNode* cur = root_;
while (cur) {
/// 找到插入位置，与该位置的父节点
pre = cur;
if (key < cur->data) {
cur = cur->left;
}
else {
cur = cur->right;
}
}
node->parent = pre;
/// 插入元素
if (!pre) {
root_ = node;
}
else if (key < pre->data) {
pre->left = node;
}
else {
pre->right = node;
}
}
删除
删除分为3中情况
-
目标节点，左孩子为空
这时候用右孩子节点
r，替换目标节点z
delete1.png
-
目标节点，右孩子为空
这时候用左孩子节点
l，替换目标节点z
delete2.png
-
目标节点，左右孩子都存在
这时需要用目标节点的后继节点
y，替换目标节点z。该后继节点y = minimum(target->right)，所以没有左孩子。
- 当
y的父节点，是z时：
delete31.png
- 当
直接用`y`替换目标节点`z`即可
- 当
y的父节点，不是z时：
delete32.png
1）需要先将`x`替换`y`，设置`y`的右孩子设为`r`，`r`的父节点为`y`
2）用`y`替换`z`
代码实现：
- 替换函数：
/**
* @brief 子树替换，用于辅助节点删除
* @param target 被替换子树的根节点
* @param source 源子树
*/
void BinSearchTree::Transplant(TNode* target, TNode* source) {
if (!target->parent) {
root_ = source;
}
else if (target->parent->left == target) {
target->parent->left = source;
}
else {
target->parent->right = source;
}
if (source) {
source->parent = target->parent;
}
}
- 删除节点操作
/**
* @brief 删除指定数据
*
*/
void BinSearchTree::TreeDelete(Tp key) {
TNode* p = TreeSearch(key);
if (p) {
if (!p->left) {
Transplant(p, p->right);
}
else if (!p->right) {
Transplant(p, p->left);
}
else {
TNode* next = TreeMinimumHelper(p->right); /// 找到p节点的后继节点
if (next->parent != p) {
Transplant(next, next->right);
next->right = p->right;
p->right->parent = next;
}
Transplant(p, next);
next->left = p->left;
next->left->parent = next;
}
delete p;
}
else {
std::cout << key << " is not in the tree!" << std::endl;
}
}
完整代码
/**
* @file bst.h
* @author tanghf
* @date 2021-01-17
* @version V1.0
* @copyright Copyright (c) 2021
*
*/
#ifndef BST_H_
#include <vector>
typedef int Tp;
typedef struct TNode {
Tp data;
TNode* parent;
TNode* left;
TNode* right;
}TNode;
/**
* @brief 二叉搜索树
*
*/
class BinSearchTree {
private:
typedef TNode* Root_ ;
Root_ root_ = nullptr;
private:
enum { kNInfinity = -65535};
void TreeVistHelper(TNode* p);
void Transplant(TNode* target, TNode* source);
TNode* TreeMinimumHelper(Root_ t);
TNode* TreeMaximumHelper(Root_ t);
TNode* TreeSuccessorHelper(TNode* p);
TNode* TreePredecessorHelper(TNode* p);
public:
BinSearchTree(){}
BinSearchTree(std::vector<Tp> tree);
~BinSearchTree();
void TreeVist();
TNode* TreeSearch(Tp key);
void TreeInsert(Tp key);
void TreeDelete(Tp key);
Tp TreeMinimum() {
if (!root_)
return kNInfinity;
return TreeMinimumHelper(root_)->data;
}
Tp TreeMaximum(){
if (!root_)
return kNInfinity;
return TreeMaximumHelper(root_)->data;
}
Tp TreeSuccessor(Tp key);
Tp TreePredecessor(Tp key);
};
#endif // !BST_H_
#include <iostream>
#include "bst.h"
/*
* @brief 将数组转化为二叉搜索树
*
*/
BinSearchTree::BinSearchTree(std::vector<Tp> tree) {
for (const auto& key : tree) {
TreeInsert(key);
}
}
BinSearchTree::~BinSearchTree() {
while (root_) {
TreeDelete(root_->data);
}
}
/**
* @brief 按顺序遍历搜索树
*
*/
void BinSearchTree::TreeVist() {
TreeVistHelper(root_);
std::cout << std::endl;
}
/**
* @brief 在树中搜索目标值
* @return 若存在返回值为目标值的节点的，否则范围空指针
*/
TNode* BinSearchTree::TreeSearch(Tp key) {
TNode* p = root_;
while (p) {
if (p->data == key) {
return p;
}
else if (key < p->data) {
p = p->left;
}
else {
p = p->right;
}
}
return nullptr;
}
/**
* @brief 在搜索树中插入元素
*
*/
void BinSearchTree::TreeInsert(Tp key) {
TNode* node = new TNode;
node->data = key;
node->parent = nullptr;
node->left = nullptr;
node->right = nullptr;
TNode* pre = nullptr;
TNode* cur = root_;
while (cur) {
/// 找到插入位置，与该位置的父节点
pre = cur;
if (key < cur->data) {
cur = cur->left;
}
else {
cur = cur->right;
}
}
node->parent = pre;
/// 插入元素
if (!pre) {
root_ = node;
}
else if (key < pre->data) {
pre->left = node;
}
else {
pre->right = node;
}
}
/**
* @brief 删除指定数据
*
*/
void BinSearchTree::TreeDelete(Tp key) {
TNode* p = TreeSearch(key);
if (p) {
if (!p->left) {
Transplant(p, p->right);
}
else if (!p->right) {
Transplant(p, p->left);
}
else {
TNode* next = TreeMinimumHelper(p->right); /// 找到p节点的后继节点
if (next->parent != p) {
Transplant(next, next->right);
next->right = p->right;
p->right->parent = next;
}
Transplant(p, next);
next->left = p->left;
next->left->parent = next;
}
delete p;
}
else {
std::cout << key << " is not in the tree!" << std::endl;
}
}
/**
* @brief 寻找目标值的下一个元素
*
*/
Tp BinSearchTree::TreeSuccessor(Tp key) {
TNode* p = TreeSearch(key);
if (p) {
TNode* next = TreeSuccessorHelper(p);
if (next) {
return next->data;
}
else {
return kNInfinity;
}
}
else {
return kNInfinity;
}
}
/**
* @brief 寻找目标值的前一个元素
*
*/
Tp BinSearchTree::TreePredecessor(Tp key) {
TNode* p = TreeSearch(key);
if (p) {
TNode* next = TreePredecessorHelper(p);
if (next) {
return next->data;
}
else {
return kNInfinity;
}
}
else {
return kNInfinity;
}
}
/***********************辅助函数******************/
/**
* @brief 寻找最小节点
*
*/
TNode* BinSearchTree::TreeMinimumHelper(Root_ t) {
while (t->left) {
t = t->left;
}
return t;
}
/**
* @brief 寻找最大节点
*
*/
TNode* BinSearchTree::TreeMaximumHelper(Root_ t) {
while (t->right) {
t = t->right;
}
return t;
}
/**
* @brief 中序遍历
*
*/
void BinSearchTree::TreeVistHelper(TNode* p) {
if (p) {
TreeVistHelper(p->left);
std::cout << p->data << " ";
TreeVistHelper(p->right);
}
}
/**
* @brief 子树替换，用于辅助节点删除
* @param target 被替换子树的根节点
* @param source 源子树
*/
void BinSearchTree::Transplant(TNode* target, TNode* source) {
if (!target->parent) {
root_ = source;
}
else if (target->parent->left == target) {
target->parent->left = source;
}
else {
target->parent->right = source;
}
if (source) {
source->parent = target->parent;
}
}
/**
* @brief 寻找指定节点的后继节点
*/
TNode* BinSearchTree::TreeSuccessorHelper(TNode* p) {
if (p->right) {
return TreeMinimumHelper(p->right);
}
TNode* next = p->parent;
while (next && p == next->right) {
p = next;
next = next->parent;
}
return next;
}
/**
* @brief 寻找指定节点的前驱节点
*/
TNode* BinSearchTree::TreePredecessorHelper(TNode* p) {
if (p->left) {
return TreeMaximumHelper(p->left);
}
TNode* pre = p->parent;
while (pre && p == pre->left) {
p = pre;
pre = pre->parent;
}
return pre;
}
网友评论