![[数据结构C++实现]二叉搜索树](http://www.mshxw.com/aiimages/31/1035049.png "[数据结构C++实现]二叉搜索树")
- 一、二叉搜索树
- 二、二叉搜索树基本框架
- 三、二叉搜索树实现
- 3.1 非递归版本
- 3.2 递归版本
- 四、二叉搜索树的应用
- 4.1 K(key)搜索模型
- 4.2 KV(key value)搜索模型
- 4.3 排序+去重
- 五、二叉搜索树性能分析
一、二叉搜索树
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
最多查找高度次（前提：树要均衡）O(logN)
最坏O（N）
O(N / 2)还是O(N) —— 所以还是有些问题，解决方案——平衡搜索二叉树：AVLTree，RBTree
二、二叉搜索树基本框架
template// key关键字：比较数据大小 struct BSTreeNode // BinarySearchTreeNode { BSTreeNode * _left; BSTreeNode * _right; K _key; }; template struct BSTree { typedef BSTreeNode Node; public: BSTree() :_root(nullptr) {} private: Node* _root; };
三、二叉搜索树实现 3.1 非递归版本
插入
bool Insert(const K& key) // 非线性一般不叫push
{
// 返回值意义：一般来说搜索树是不允许有重复元素了，有重复元素不让重复插入
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 找到空位置进行插入
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
// 走到空，就可以链接了
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return ture;
}
删除
没有孩子的节点
只有一个孩子的节点
有两个孩子的节点
并且最右节点(一定右为空)或者最左节点(一定左为空)
删除只有一个孩子节点的情况：
父亲会不会为空？——会，只有根节点父亲会为空
让root指向cur的孩子
有两个孩子的节点：要么找右子树最左节点或者是左子树最右节点
若删除5：
若删除7：不要给空：Node* minParent = nullptr;，不然min父节点为空，之后又会出错
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
// 找到了，准备开始删除
// 画图理解
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
// 左右都不为空
// 找右树最左节点
// 不要给空：Node* minParent = nullptr;
Node* minParent = cur;
Node* min = cur->_right;
while (min->_left)
{
minParent = min;
min = min->_left;
}
cur->_key = min->_key;
if (minParent->_left == min)
{
minParent->_left = min->_left;
}
else
{
minParent->_right = min->_right;
}
delete min;
}
return true;
}
}
return false;
}
3.2 递归版本
递归可能会爆栈
插入
bool _InsertR(Node*& root, const K& key) // root必须加引用
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
{
return _InsertR(root->_right, key); // 如这里，下一层的root就是这一层root->_right的别名，是要进行修改的
}
else if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
删除
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
return _EraseR(root->_right, key);
}
else if (root->_key > key)
{
return _EraseR(root->_left, key);
}
else
{
Node* del = root;
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
// 左右都不为空
Node* min = root->_right;
while (min->_left)
{
min = min->_left;
}
swap(min->_key, root->_key);
// 递归到右子树去删除
return _EraseR(root->_right, key); // 这里就已经删除了，防止和下面在删除一次，所以要直接return
}
delete del;
return true;
}
}
并且也不怕parent为空的情况
四、二叉搜索树的应用 4.1 K(key)搜索模型
通俗来说就是判断在不在
上述代码我们实现的就是K模型，只存一个值
namespace K
{
template // key关键字：比较数据大小
struct BSTreeNode // BinarySearchTreeNode
{
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
// new需要他的构造函数
BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
template
struct BSTree
{
typedef BSTreeNode Node;
public:
BSTree()
:_root(nullptr)
{}
bool Insert(const K& key) // 非线性一般不叫push
{
// 返回值意义：一般来说搜索树是不允许有重复元素了，有重复元素不让重复插入
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 找到空位置进行插入
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
// 走到空，就可以链接了
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
// 找到了，准备开始删除
// 画图理解
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
// 左右都不为空
// 找右树最左节点
// 不要给空：Node* minParent = nullptr;
Node* minParent = cur;
Node* min = cur->_right;
while (min->_left)
{
minParent = min;
min = min->_left;
}
cur->_key = min->_key;
if (minParent->_left == min)
{
minParent->_left = min->_left;
}
else
{
minParent->_right = min->_right;
}
delete min;
}
return true;
}
}
return false;
}
Node* _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return nullptr;
}
if (root->_key < key)
{
return _FindR(root->_right, key);
}
else if (root->_key > key)
{
return _FindR(root->_left, key);
}
else
{
return root;
}
}
Node* FindR(const K& key)
{
return _FindR(_root, key);
}
bool _InsertR(Node*& root, const K& key) // root必须加引用
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
{
return _InsertR(root->_right, key);
}
else if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
return _EraseR(root->_right, key);
}
else if (root->_key > key)
{
return _EraseR(root->_left, key);
}
else
{
Node* del = root;
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
// 左右都不为空
Node* min = root->_right;
while (min->_left)
{
min = min->_left;
}
swap(min->_key, root->_key);
// 递归到右子树去删除
return _EraseR(root->_right, key); // 这里就已经删除了，防止和下面在删除一次，所以要直接return
}
delete del;
return true;
}
}
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
void InOrder() // 为了外部测试函数可以直接调用，如果直接写下面的，root是私有，调用不到
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
private:
Node* _root;
};
}
4.2 KV(key value)搜索模型
通过一个值查找另外一个值
中英字典——中英互译
身份证，往卡里面写入数据
namespace KV
{
template // key关键字：比较数据大小,value表示值
struct BSTreeNode // BinarySearchTreeNode
{
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
V _value;
// new需要他的构造函数
BSTreeNode(const K& key, const V& value)
:_left(nullptr)
, _right(nullptr)
, _key(key)
,_value(value)
{}
};
template
struct BSTree
{
typedef BSTreeNode Node;
public:
BSTree()
:_root(nullptr)
{}
bool Insert(const K& key, const V& value) // 非线性一般不叫push
{
// 返回值意义：一般来说搜索树是不允许有重复元素了，有重复元素不让重复插入
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 找到空位置进行插入
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
// 走到空，就可以链接了
cur = new Node(key, value);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
// 找到了，准备开始删除
// 画图理解
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (parent == nullptr)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
// 左右都不为空
// 找右树最左节点
// 不要给空：Node* minParent = nullptr;
Node* minParent = cur;
Node* min = cur->_right;
while (min->_left)
{
minParent = min;
min = min->_left;
}
cur->_key = min->_key;
cur->_value = min->_value;
if (minParent->_left == min)
{
minParent->_left = min->_left;
}
else
{
minParent->_right = min->_right;
}
delete min;
}
return true;
}
}
return false;
}
void InOrder() // 为了外部测试函数可以直接调用，如果直接写下面的，root是私有，调用不到
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " " << root->_value << " ";
_InOrder(root->_right);
}
private:
Node* _root;
};
void TestBSTree1()
{
// 字典中英互译
BSTree dict; // value可以是容器
dict.Insert("sort", "排序");
dict.Insert("left", "左边");
dict.Insert("right", "右边");
dict.Insert("map", "地图、映射");
string str;
while (cin >> str)
{
BSTreeNode* ret = dict.Find(str);
if (ret)
{
cout << "对应中文解释:" << ret->_value << endl;
}
else
{
cout << "没有对应解释" << endl;
}
}
}
void TestBSTree2()
{
// 统计水果出现从次数
string arr[] = { "苹果", "西瓜","草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
BSTree countTree;
for (auto& str : arr)
{
BSTreeNode* ret = countTree.Find(str);
if (ret != nullptr)
{
ret->_value++;
}
else
{
countTree.Insert(str, 1);
}
}
// 按key排序
countTree.InOrder();
}
}
从底层来看 set —— key模型的搜索树 map —— KV模型的搜索树（插入的pair，可以理解为是一个结构体）4.3 排序+去重
实现中已经提到过
五、二叉搜索树性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树
若二叉搜索树是有序，则退化为单支，性能和链表就没什么区别了
这样子就没什么用了，因此需要弄出两个树才能解决——AVL、红黑树
2^30 ≈ 10亿
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：logN
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2
