目录1. 什么是二叉搜索树2. 二叉搜索树的特点时间复杂度分析最优情况最坏情况3.二叉搜索树的中序遍历中序遍历代码4. 二叉搜索树 的插入插入规则插入过程示例Insert 实现5. 二叉搜索树的查找查找思想Find 实现6. 二叉搜索树的删除情况1删除叶子节点情况2只有右孩子情况3只有左孩子情况4左右孩子都存在替换法删除方法删除代码7.二叉搜索树类型key 型 二叉搜索树1. 车牌识别2. 拼写检查key/value 型 二叉搜索树key/value 应用场景8. 二叉搜索树与二分查找的区别1. 什么是二叉搜索树二叉搜索树Binary Search Tree简称 BST又叫二叉排序树是一种特殊的二叉树。它满足以下性质左子树所有节点的值都小于根节点右子树所有节点的值都大于根节点左右子树也分别是二叉搜索树例如8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13这棵树中3 8所以在左边10 8所以在右边6 3所以在 3 的右边4 6所以在 6 的左边2. 二叉搜索树的特点BST 最大的优势查找快插入快删除快因为每次比较都能排除一半区域思想类似二分查找。时间复杂度分析最优情况如果树接近完全二叉树高度log N查找效率O(log N)最坏情况如果插入数据有序1 2 3 4 5BST 会退化成链表1 \ 2 \ 3 \ 4 \ 5高度变成N时间复杂度退化O(N)所以普通 BST 并不稳定。后面会引出AVL树红黑树它们属于平衡二叉搜索树。3.二叉搜索树的中序遍历BST 有一个非常重要的性质中序遍历结果一定有序中序遍历代码void _InOrder(Node* root) { if (root nullptr) return; _InOrder(root-_left); cout root-_key ; _InOrder(root-_right); }4. 二叉搜索树 的插入插入规则从根开始比当前节点小 → 往左走比当前节点大 → 往右走找到空位置后插入插入过程示例插入int a[] {8,3,1,10,6,4,7,14,13};形成8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13Insert 实现bool Insert(const K key) { 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; }这里二叉搜索树可以分为冗余树和非冗余的冗余树就是允许数据可重复我们可以默认相等的数据插入左边测试用例int main() { BSTreeint t; int a[] { 8, 3, 1, 10, 1, 6, 4, 7, 14, 13}; for (auto e : a) { t.Insert(e); } t.InOrder(); t.Insert(16); t.Insert(3); t.InOrder(); return 0; }5. 二叉搜索树的查找查找思想从根开始key 大 → 右走key 小 → 左走相等 → 找到Find 实现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; }6. 二叉搜索树的删除删除是 BST 最复杂的操作。情况1删除叶子节点例如删除1直接删除即可。情况2只有右孩子3 \ 5删除 35父亲直接指向右孩子。情况3只有左孩子5 / 3删除 53父亲直接指向左孩子。情况4左右孩子都存在例如删除8 / \ 3 10不能直接删。因为左子树没地方放右子树也没地方放替换法删除方法找到左子树最大值或者右子树最小值替换当前节点。因为左子树最大值一定小于当前节点且大于左子树其他节点右子树最小值一定大于当前节点且小于右子树其他节点所以替换后 BST 仍成立。删除代码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 { // 0-1个孩⼦的情况 if (cur-_left nullptr) { if (cur _root) { _root cur-_right; } else { if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } delete cur; return true; } else if (cur-_right nullptr) { if (cur _root) { _root cur-_left; } else { if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } delete cur; return true; } else { // 2个孩⼦的情况 Node* rightMinP cur; Node* rightMin cur-_right; while (rightMin-_left)//找到右子树最小值 { rightMinP rightMin; rightMin rightMin-_left; } cur-_key rightMin-_key;//交换值 if (rightMinP-_left rightMin) { rightMinP-_left rightMin-_right; } else { rightMinP-_right rightMin-_right; } delete rightMin; return true; } } } return false; }假设初始树长这样这里我们可以把删除叶子节点和只有一个孩子的节点归为一类因为他们都是属于把父亲节点指向该节点的子树这里删除只需要注意被删除节点是父亲的左节点还是右节点然后分类讨论一下即可t.Erase(1); t.Erase(10); t.InOrder();如果有2个孩子找到右子树最小节点然后交换2个节点的值后删除该节点即可因为这个右子树最小节点的左子树一定是空所以删除它的逻辑跟前面一样让它的父亲指向它的右子树即可所以我们还得有父亲节点在初始化是不要赋值为空因为赋值为空如果被删除节点的右节点刚好是最小节点那么就不会进入循环给父亲节点重新赋值就比如改图中8这个节点它的右节点10刚好就是右子树的最小节点这会引发空指针解引用问题所以初始化赋值为cur即可t.Erase(6); t.Erase(8); t.InOrder();7.二叉搜索树类型key 型 二叉搜索树特点只存 keyBSTint本质setint应用场景1. 车牌识别判断车辆是否属于本小区。2. 拼写检查检查单词是否存在。key/value 型 二叉搜索树节点结构templateclass K, class V struct BSTNode { K _key; V _value; BSTNodeK,V* _left; BSTNodeK,V* _right; };特点通过 key 查找 value。类似mapstring, intset和map底层都是红黑树key/value 应用场景1. 英汉词典left - 左边 right - 右边2. 停车场计费车牌号 - 入场时间3. 统计单词次数例如苹果 苹果 香蕉 苹果统计苹果 - 3 香蕉 - 18. 二叉搜索树与二分查找的区别对比二叉搜索树二分查找数据结构树数组查找效率O(logN)O(logN)插入效率较高较低删除效率较高较低是否需要连续空间不需要需要
