C++ 二叉搜索树详解
一、二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
- 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值
- 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值
- 它的左右子树也分别为二叉搜索树
- 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义。后续我们学习 map/set/multimap/multiset 系列容器底层就是二叉搜索树，其中 map/set 不支持插入相等值，multimap/multiset 支持插入相等值。
二、二叉搜索树的性能分析
最优情况下，二叉搜索树为完全二叉树 (或者接近完全二叉树)，其高度为：log2 N
最差情况下，二叉搜索树退化为单支树 (或者类似单支)，其高度为：N
所以综合而言二叉搜索树增删查改时间复杂度为：O(N)
那么这样的效率显然是无法满足我们需求的，我们后续需要继续讲解二叉搜索树的变形，平衡二叉搜索树 AVL 树和红黑树，才能适用于我们在内存中存储和搜索数据。
另外需要说明的是，二分查找也可以实现 O(log2 N) 级别的查找效率，但是二分查找有两大缺陷：
- 需要存储在支持下标随机访问的结构中，并且有序。
- 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。
这里也就体现出了平衡二叉搜索树的价值。
三、二叉搜索树的插入
插入的具体过程如下：
- 树为空，则直接新增结点，赋值给 root 指针
- 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。
- 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）
SearchBinaryTree.h
#pragma once
#include<iostream>
using namespace std;
template<class K>
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
( K& key) :_key(key), _left(), _right() { }
};
< >
{
BSTNode<K> Node;
:
{
(_root == ) {
_root = (key);
;
}
Node* parent = ;
Node* cur = _root;
(cur) {
(cur->_key < key) {
parent = cur;
cur = cur->_right;
} (cur->_key > key) {
parent = cur;
cur = cur->_left;
} {
;
}
}
cur = (key);
(parent->_key < key) {
parent->_right = cur;
} {
parent->_left = cur;
}
;
}
{
_InOrder(_root);
cout << endl;
}
:
_InOrder(Node * root) {
(root == ) {
;
}
_InOrder(root->_left);
cout << root->_key << ;
_InOrder(root->_right);
}
Node* _root = ;
};
