二叉搜索树 (Binary Search Tree) 核心是解决问题。高效解决问题。
查找问题 Searching Problem：
查找问题是计算机中非常重要的基础问题
查找问题的基础：二分查找法 Binary Search
对于有序数列，才能使用二分查找法 （排序的作用）二分查找 中间元素。一分为二。整个的时间复杂度是logn级别的。
二分查找法的思想在1946年提出。实现一个正确的二分查找法
第一个没有bug的二分查找法在1962年才出现。
// 二分查找法,在有序数组arr中,查找target
// 如果找到target,返回相应的索引index
// 如果没有找到target,返回-1
template
int binarySearch(T arr[], int n, T target){// 在arr[l...r]之中查找target
//n-1因为右边界也是闭区间
int l = 0, r = n-1;
while( l <= r ){//int mid = (l + r)/2;
//解决溢出问题
int mid = l + (r-l)/2;
if( arr[mid] == target )
return mid;
// 在arr[l...mid-1]之中查找target.mid已经查找过了
if( arr[mid] > target )
r = mid - 1;
else
l = mid + 1;
}return -1;
}
使用递归地方式实现二分查找法。
- 递归实现通常思维上更容易。
- 子问题，想好递归关系
- 递归性能上略差。
- floor
- ceil
返回值为floor和ceil正在指的41/43
floor & ceil 二分搜索树优势：key-value 通过键查找值。字典。
如果key值是整数，可以用数组进行表示。不过如果key很稀疏，那么用数组会很浪费。key根本不是整数，那么数组就没法了。
二分搜素树的优势：插入&删除&更改时间复杂度 普通数组不管查找，插入还是删除都得从头到尾扫一遍。
顺序数组：二分查找（logn）、插入&删除 ：O(n)
二分搜索树：插入&删除&更改（logn）
优势:
- 高效：不仅可查找数据；还可以高效地插入，删除数据 - 动态维护数据
可以方便地回答很多数据之间的关系问题： - min, max, floor, ceil, rank（该数据时当前数据中的第几名）, select（第100名数据是谁）
每个节点的键值大于左孩子；每个节点的键值小于右孩子；以左右孩子为根的子树仍为二分搜索树天然包括递归结构。
堆的二叉树必须是一颗完全二叉树（数组）。对于二分搜索树，不一定是完全二叉树。
使用node节点（key，value） 使用指针表示节点之间的联系。
最基础的二分搜索树实现
class BST{private:
struct Node{
Key key;
Value value;
Node *left;
Node *right;
Node(Key key, Value value){
this->key = key;
this->value = https://www.it610.com/article/value;
this->left = this->right = NULL;
}
};
//根：指向node的指针
Node *root;
//共有多少个节点
int count;
public:
BST(){
root = NULL;
count = 0;
}
~BST(){
// TODO: ~BST()
//todo表明留空还需要完善。
}int size(){
return count;
}bool isEmpty(){
return count == 0;
}
};
插入新的节点（insert）
插入60
将60与41比较:60比41大。所以插入41右侧。
- 插入以58为根的二叉搜索树中。应该插到58右侧，58右侧为空。因此插入到60位置。
28比41小插入左边以22为根 28比22大。所以去右边。28比33小。去左边。
28插入完成，插入42 如果插入有相同的值之间覆盖掉。
42覆盖掉原42
void insert(Key key, Value value){
//返回值为插入该元素后的二叉树的根。
root = insert(root, key, value);
}private:
// 向以node为根的二叉搜索树中,插入节点(key, value)
// 返回插入新节点后的二叉搜索树的根
Node* insert(Node *node, Key key, Value value){//递归到底
if( node == NULL ){
count ++;
return new Node(key, value);
}if( key == node->key )
node->value = https://www.it610.com/article/value;
else if( key < node->key )
node->left = insert( node->left , key, value);
else// key > node->key
node->right = insert( node->right, key, value);
return node;
}
使用递归方式：我们是如何将向整棵二叉树中插入新元素转换为向子树中插入新元素。直到我们子树为空。我们新建节点这个新的节点就是一颗新的子树。练习：insert的非递归实现。
二叉搜索树中查找节点。 查找和插入其实差不多。不如要查找42
查找42 不断与根，子树根对比：大的放右边，小的放左边。查找成功。
查找失败
找到60节点，59比60小。应该在60左侧，但是没有。所以失败。二叉查找树包含contain 和 查找search 同质。
bool contain(Key key){
return contain(root, key);
}// 查看以node为根的二叉搜索树中是否包含键值为key的节点
bool contain(Node* node, Key key){//处理递归到底的基本情况
if( node == NULL )
return false;
if( key == node->key )
return true;
else if( key < node->key )
return contain( node->left , key );
else // key > node->key
return contain( node->right , key );
} //返回值为node：暴露了太多信息给外界
//返回值为value不能为空
//返回一个value的指针，没找到指向空。
Value* search(Key key){
return search( root , key );
}// 在以node为根的二叉搜索树中查找key所对应的value
Value* search(Node* node, Key key){if( node == NULL )
return NULL;
if( key == node->key )
return &(node->value);
else if( key < node->key )
return search( node->left , key );
else // key > node->key
return search( node->right, key );
}int main() {string filename = "bible.txt";
vector words;
//可以把圣经文本里的词存进数组里
if( FileOps::readFile(filename, words) ) {cout << "There are totally " << words.size() << " words in " << filename << endl;
cout << endl;
// test BST
//从头到尾访问每一个词，计算词出现的频次。
time_t startTime = clock();
BST bst = BST();
for (vector::iterator iter = words.begin();
iter != words.end();
iter++) {
int *res = bst.search(*iter);
if (res == NULL)
bst.insert(*iter, 1);
else
(*res)++;
}cout << "'god' : " << *bst.search("god") << endl;
time_t endTime = clock();
cout << "BST , time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " s." << endl;
cout << endl;
// test SST
startTime = clock();
SequenceST sst = SequenceST();
for (vector::iterator iter = words.begin();
iter != words.end();
iter++) {
int *res = sst.search(*iter);
if (res == NULL)
sst.insert(*iter, 1);
else
(*res)++;
}cout << "'god' : " << *sst.search("god") << endl;
endTime = clock();
cout << "SST , time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " s." << endl;
}return 0;
}//顺序查找使用的是链表实现顺序查找的方式。
运行结果：
运行结果 二分搜索树的前中后序遍历
- 前序遍历：先访问当前节点，再依次递归访问左右子树
- 中序遍历：先递归访问左子树，再访问自身，再递归访问右子树
- 后续遍历：先递归访问左右子树，再访问自身节点
前序遍历 前序遍历：访问到前序点左的时候干相应的事情。
访问每个节点：中间的时候才做事情 访问每个节点：中间的时候才做事情
中序遍历的实际应用：从小到大的排列后序遍历
特点:已经将当前节点左右两个子树都访问完成了才访问该节点。代码编写
应用:当我们释放二叉树的时候。释放两个子树才释放自身。
// 对以node为根的二叉搜索树进行前序遍历
void preOrder(Node* node){if( node != NULL ){
cout<key<left);
preOrder(node->right);
}
}// 对以node为根的二叉搜索树进行中序遍历
void inOrder(Node* node){if( node != NULL ){
inOrder(node->left);
cout<key<right);
}
}// 对以node为根的二叉搜索树进行后序遍历
void postOrder(Node* node){if( node != NULL ){
postOrder(node->left);
postOrder(node->right);
cout<key<left );
destroy( node->right );
delete node;
count --;
}
}
二叉树的层序遍历
- 深度优先
- 广度优先
无论是前面的先序后序中序中我们遍历所有元素的顺序是一致的。按层来看。广度。一层一层。引入队列的概念
28-16-13-22-30-29-40。只是我们遍历他们时打印语句的位置不同
尝试走到最深.走不通回溯
广度优先遍历
从28开始入队。执行完28的打印语句并将它的两个孩子入队。然后对于孩子16打印完并将它的两个孩子入队。执行完的出队。代码实现
// 层序遍历
void levelOrder(){queue q;
//入队根节点
q.push(root);
//队列为空结束
while( !q.empty() ){//取出队首元素。
Node *node = q.front();
q.pop();
cout<key<left )
q.push( node->left );
if( node->right )
q.push( node->right );
}
}
二分搜索树的遍历：O(n)
每个节点仅访问了常数次
归并排序，快速排序是一颗二叉树的深度优先遍历结合递归 & 结合队列。
删除一个节点 找到删除掉，重点问题是将相连部分删除掉。
最小值：13.一直找左边。
最大值：42.一直找右边
编写代码
// 寻找最小的键值
Key minimum(){
assert( count != 0 );
Node* minNode = minimum( root );
return minNode->key;
}// 在以node为根的二叉搜索树中,返回最小键值的节点
Node* minimum(Node* node){
if( node->left == NULL )
return node;
return minimum(node->left);
}
// 寻找最大的键值
Key maximum(){
assert( count != 0 );
Node* maxNode = maximum(root);
return maxNode->key;
}// 在以node为根的二叉搜索树中,返回最大键值的节点
Node* maximum(Node* node){
if( node->right == NULL )
return node;
return maximum(node->right);
}
删除二分搜索树的最小值。
直接删除 如果是删除13那么可以直接删除
子树上移 删除22，则因为此时剩下的一定介于22和父节点41之内。将33作为新的节点代替22位置。
删除58 删除58则，50代替58成为父节点的孩子
// 从二叉树中删除最小值所在节点
void removeMin(){
if( root )
root = removeMin( root );
}// 从二叉树中删除最大值所在节点
void removeMax(){
if( root )
root = removeMax( root );
}// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
Node* removeMin(Node* node){if( node->left == NULL ){Node* rightNode = node->right;
delete node;
count --;
return rightNode;
}node->left = removeMin(node->left);
return node;
}// 删除掉以node为根的二分搜索树中的最大节点
// 返回删除节点后新的二分搜索树的根
Node* removeMax(Node* node){if( node->right == NULL ){Node* leftNode = node->left;
delete node;
count --;
return leftNode;
}node->right = removeMax(node->right);
return node;
}
如何在二分搜索树中删除任意节点。 删除只有左右孩子节点。上一小节已经解决了。
而如果我们要删除的节点既有左孩子，又有右孩子。
删除两个孩子的父亲 1962年，Hibbard提出 - Hubbard Deletion
删除58
此时既不是左孩子也不是右孩子而是右子树中的最小值代替的节点 Hubbard删除法 代码
// 从二叉树中删除键值为key的节点
void remove(Key key){
root = remove(root, key);
}// 删除掉以node为根的二分搜索树中键值为key的节点
// 返回删除节点后新的二分搜索树的根
Node* remove(Node* node, Key key){if( node == NULL )
return NULL;
if( key < node->key ){
node->left = remove( node->left , key );
return node;
}
else if( key > node->key ){
node->right = remove( node->right, key );
return node;
}
else{// key == node->key//左右都为空也在这种情况里
if( node->left == NULL ){
Node *rightNode = node->right;
delete node;
count --;
return rightNode;
}if( node->right == NULL ){
Node *leftNode = node->left;
delete node;
count--;
return leftNode;
}// node->left != NULL && node->right != NULL
Node *successor = new Node(minimum(node->right));
/*
Node(Node *node){
this->key = node->key;
this->value = https://www.it610.com/article/node->value;
this->left = node->left;
this->right = node->right;
}
在构造函数中复制了一份。
*/count ++;
successor->right = removeMin(node->right);
successor->left = node->left;
delete node;
count --;
return successor;
}
}
不唯一的代替 删除二分搜索树的任意一个节点：时间复杂度为O(logn)
删除节点就是查找。指针交换是常数级的。
二分搜索树的顺序性 定位元素，还可以回答元素位置。
- minimum , maximum
- successor （前驱）, predecessor（后继） ：前提是元素真的存在。
- floor，ceil：最接近45的小值和大值。
11的floor。65的ceil。
- rank,select
添加一个值记录数
对于每个节点存一个以该节点为根的二叉搜索树有多少个节点。排名第十的元素是谁？
58比41大。在41右边找到58.58至少在41的左孩子数量+1也就是6名开外。
+自身的左孩子树有三个加上自己。排名第十。
select inserted & remove时也要同时维护这个域。
支持重复元素的二分搜索树。
我们的insert遇到重复值会直接覆盖。
- 把左孩子变成<=，右孩子继续大于
支持重复元素的 二分搜索树的局限性 二分查找树与顺序查找一起处理圣经，效率大概有100倍差距。
可是二分查找树永远这么高效么？
特殊情况：二分搜索树的局限性。
同样的数据可以对应不同的二分搜索树二分搜索树可能退化为链表 二分搜索树可能退化成链表
int main() {string filename = "communist.txt";
vector words;
if( FileOps::readFile(filename, words) ) {cout << "There are totally " << words.size() << " words in " << filename << endl;
cout << endl;
// test BST
time_t startTime = clock();
BST *bst = new BST();
for (vector::iterator iter = words.begin();
iter != words.end();
iter++) {
int *res = (*bst).search(*iter);
if (res == NULL)
(*bst).insert(*iter, 1);
else
(*res)++;
}cout << "'unite' : " << *(*bst).search("unite") << endl;
time_t endTime = clock();
cout << "BST , time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " s." << endl;
cout << endl;
delete bst;
// test SST
startTime = clock();
SequenceST *sst = new SequenceST();
for (vector::iterator iter = words.begin();
iter != words.end();
iter++) {
int *res = (*sst).search(*iter);
if (res == NULL)
(*sst).insert(*iter, 1);
else
(*res)++;
}cout << "'unite' : " << *(*sst).search("unite") << endl;
endTime = clock();
cout << "SST , time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " s." << endl;
cout << endl;
delete sst;
// test BST2
startTime = clock();
BST *bst2 = new BST();
//先排序后插入，导致二分查找树变成了链表
sort( words.begin() , words.end() );
for (vector::iterator iter = words.begin();
iter != words.end();
iter++) {
int *res = (*bst2).search(*iter);
if (res == NULL)
(*bst2).insert(*iter, 1);
else
(*res)++;
}cout << "'unite' : " << *(*bst2).search("unite") << endl;
endTime = clock();
cout << "BST2 , time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " s." << endl;
cout << endl;
delete bst2;
}return 0;
}
代码中BST2 先排序后插入，导致二分查找树变成了链表。
运行结果：
运行结果 比链表还慢：
- 每次还在判断左孩子
- 递归比迭代慢一些
- 像快速排序一样：一开始就随机。
- 一开始就将数据打乱。
平衡二叉树：红黑树
可以改造二叉树的实现，使得他无法退化成链表。左右两棵子树，左右两颗子树的高度差不会超过1.平衡二叉树的经典实现：红黑树
红黑树
将节点分为两类：红节点和黑节点。插入和删除中将考虑颜色来进行。其他平衡二叉树的实现：
- 2-3 tree
- AVL tree
- Splay tree
既保持了二叉树的性质，又能跟堆一样进行优先级操作字典的实现：
logn也有点慢
trie 他的查找一个单词的时间复杂度和单词本身长度有关与字典里有多少单词无关。找四个节点。
使用trie统计词频。没有构建树但是也是使用到了树。
树形问题
递归法天然的树形性质递归排序
求解就是一颗树的形状。快速排序：树形
归并&快速 很像前序遍历 后序遍历搜索问题
可能走的位置
决策树来选出最佳的决策。搜索树求解 八皇后：横竖对角线都不能碰面
八皇后 可以很容易使用树形搜索求得所有解。
数独 可以用树来解决。
自动求解搬运工。深度学习搜索人工智能。
【数据结构与算法|算法与数据结构（五）二叉搜索树】更多树：
- KD 树
- 区间树
- 哈夫曼树
推荐阅读
- 人工智能|tensorflow学习笔记（卷积神经网络最终笔记）
- Pytorch|PyTorch学习笔记（一）（PyTorch环境安装）
- Pytorch|PyTorch学习笔记（五）（模型定义、修改、保存）
- 深度学习|PyTorch学习笔记（四）（PyTorch基础实战）
- Pytorch|PyTorch学习笔记（二）（简介与基础知识）
- 深度学习|YOLOv1——v5学习笔记
- 神经网络|【机器学习基础】常用激活函数（激励函数）理解与总结
- 人工智能|pytorch中的激励函数（详细版）
- 高温电炉实时监控电炉实时监控窑炉实时监控真空炉实时监控电炉数据采集窑炉数据采集