C++【二叉搜索树】

1、二叉搜索树的概念二叉搜索树又称二叉排序树它或者是一颗空树或者是具有一下性质的二叉树若它的左子树不为空则左子树上的所有结点的值都小于等于根结点的值。若它的右子树不为空则右子树上的所有结点的值都大于等于根结点的值。它的左右子树也分别为二叉搜索树二叉搜索树中可以支持插入相等的值也可以不支持插入相等的值具体看使用场景定义例如map/set/multimap/multiset系列容器底层就是二叉搜索树其中map/set不支持插入相等值multimap/multiset支持插入相等值。2、二叉搜索树的性能分析最优情况下二叉搜索树为完全二叉树或者接近完全二叉树其高度为log2 N最差情况下二叉搜索树退化为单支树或者类似单支其高度为N所以综合而言二叉搜索树增删查改时间复杂度为O(N)那么这样的效率显然是无法满足我们需求的实际上平衡二叉搜索树AVL树和红黑树才能适用于我们在内存中存储和搜索数据另外需要说明的是二分查找也可以实现O(1og2N)级别的查找效率但是二分查找有两大缺陷。这里也就体现出了平衡二叉搜索树的价值。3、二叉树的插入插入的具体过程如下1.树为空则直接新增结点赋值给root指针2.树为空按二叉树搜索树性质插入值比当前结点大往右走插入值比当前结点小往左走找到空位置插入新结点。3.如果支持插入相等的值插入值跟当前结点相等的值可以往右走也可以往左走找到空位置插入新结点。(要注意的是要保持逻辑一致性插入相等的值不要一会往右走一会往左走)。inta[] {8,3,1,10,6,4,7,14,13};4、二叉搜索树的查找从根开始比较查找xx比根的值大则往右边走查找x比根值小则往左边走查找。最多查找高度次走到到空还没找到这个值不存在。如果不支持插入相等的值找到x即可返回。如果支持插入相等的值意味着有多个x存在一般要求查找中序的第一个x。如下图查找3要找到1的右孩子的那个3返回。5、二叉搜索树的删除首先查找元素是否在二叉搜索树中如果不存在则返回false。如果查找元素存在则分以下四种情况分别处理:(假设要删除的结点为N)1.要删除结点N左右孩子均为空2.要删除的结点N左孩子位空右孩子结点不为空3.要删除的结点N右孩子位空左孩子结点不为空4.要删除的结点N左右孩子结点均不为空对应以上四种情况的解决方案:1.把N结点的父亲对应孩子指针指向空直接删除N结点(情况1可以当成2或者3处理效果是一样的)2.把N结点的父亲对应孩子指针指向N的右孩子直接删除N结点3.把N结点的父亲对应孩子指针指向N的左孩子直接删除N结点4.无法直接删除N结点因为N的两个孩子无处安放只能用替换法删除。找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N因为这两个结点中任意一个放到N的位置都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换转而变成删除R结点R结点符合情况2或情况3可以直接删除。6、二叉搜索树的实现代码头文件实现// BinarySearch.h#pragma once #include iostream using namespace std; // BinarySearch.h namespace key { templateclass K struct BSTNode { K _key; BSTNodeK* _left; BSTNodeK* _right; BSTNode(const K key) :_key(key) ,_left(nullptr) ,_right(nullptr) { } }; templateclass K class BSTree { using Node BSTNodeK; public: // 插入 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; } // 查找 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 (cur _root) { _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 (cur _root) { _root cur-_left; } else { if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } delete cur; } else { Node* replaceParent cur; Node* replace cur-_right; while (replace-_left) { replaceParent replace; replace replace-_left; } cur-_key replace-_key; if (replaceParent-_left replace) replaceParent-_left replace-_right; else replaceParent-_right replace-_right; delete replace; } return true; } } return false; } void InOrder() { _InOrder(_root); cout endl; } private: // 中序遍历打印 void _InOrder(Node* root) { if (root nullptr) { return; } _InOrder(root-_left); cout root-_key ; _InOrder(root-_right); } private: Node* _root nullptr; }; }主程序测试Test.cpp#include BinarySearch.h int main() { key::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(); t.Erase(3); t.InOrder(); t.Erase(8); t.InOrder(); for (auto e : a) { t.Erase(e); t.InOrder(); } return 0; }完。