最具价值的网站建设,宝塔面板 wordpress,菜谱网站手机源码,咸阳网站建设电话一、二叉搜索树概念
二叉搜索树又叫二叉排序树#xff0c;它或是空树#xff0c;或是具有以下性质的二叉树#xff1a;
#xff08;1#xff09;若它的左子树不为空#xff0c;则左子树上的所有节点的值都小于根节点的值#xff1b;
#xff08;2#xff09;若它的…一、二叉搜索树概念
二叉搜索树又叫二叉排序树它或是空树或是具有以下性质的二叉树
1若它的左子树不为空则左子树上的所有节点的值都小于根节点的值
2若它的右子树不为空则右子树上的所有节点的值都大于根节点的值
3它的左右子树也分别为二叉搜索树。
二、二叉搜索树操作
1.二叉搜索树的查找
1若根节点为空则直接返回false否则进行后续操作
2如果根节点key查找key返回ture否则进行后续操作
3若根节点key查找key则在其左子树内进行查找否则在其右子树内进行查找
4递归上述过程。
2.二叉搜索树的插入
1若树为空则直接插入
2若树不为空则按二叉搜索树性质查找插入位置然后插入。
3.二叉搜索树的删除 首先查找待删除元素是否在二叉搜索树中没有则直接返回否则要删除的节点可分为以下四种情况
1待删除节点无孩子节点
2待删除节点只有左孩子
3待删除节点只有右孩子
4待删除节点左右孩子都有。
删除方法
情况1删除方法与情况2和3相同
情况2删除该节点并使被删除节点的双亲节点指向被删除节点的左孩子节点
情况3删除该节点并使被删除节点的双亲节点指向被删除节点的右孩子
情况4在它的右子树中寻找中序下的第一个节点值最小的节点用它的值覆盖掉被删除节点在处理该节点的删除问题。或找它左子树中最大的节点。
三、二叉搜索的实现
1.代码实现
templateclass T
struct BSTNode {BSTNode(const T value T()): _left(nullptr), _right(nullptr), _value(value){}BSTNodeT* _left;BSTNodeT* _right;T _value;
};//约定value唯一
templateclass T
class BinarySearchTree {typedef BSTNodeT Node;
public:BinarySearchTree(): _root(nullptr){}~BinarySearchTree() {Destroy(_root);}//插入bool Insert(const T value) {//空树if (_root nullptr) {_root new Node(value);return true;}//非空Node* cur _root;Node* parent nullptr;//保存cur双亲节点//查找插入位置while (cur) {parent cur;if (value cur-_value) {cur cur-_left;}else if (value cur-_value) {cur cur-_right;}else {//待插入节点已存在return false;}}//插入新节点cur new Node(value);if (value parent-_value) {parent-_right cur;}else {parent-_left cur;}return true;}//查找Node* Find(const T value) {Node* cur _root;while (cur) {if (value cur-_value) {return cur;}else if (value cur-_value) {cur cur-_left;}else {cur cur-_right;}}return cur;}//删除bool Erase(const T value) {if (_root nullptr) return false;Node* cur _root;Node* parent nullptr;//查找待删除节点while (cur) {//parent cur;不能在这里记录双亲节点因为有可能cur已经是待删除节点会直接breakif (value cur-_value) {break;}else if (value cur-_value) {parent cur;cur cur-_left;}else {parent cur;cur cur-_right;}}if (cur nullptr) return false;//没有待删除节点//删除节点if (cur-_left nullptr) {//情况1和2if (parent nullptr) {//是根节点且左孩子为空_root cur-_right;}else {//不是根节点if (cur parent-_left) parent-_left cur-_right;else parent-_right cur-_right;}delete cur;}else if (cur-_right nullptr) {//情况1和3if (parent nullptr) {//是根节点且右孩子为空_root cur-_left;}else {//不是根节点if (cur parent-_left) parent-_left cur-_left;else parent-_right cur-_left;}delete cur;}else {//情况4//查找该节点右子树最小值(或左子树的最大值)Node* prev cur;Node* node cur-_right;while (node-_left) {prev node;node node-_left;}//覆盖节点值cur-_value node-_value;//删除节点该节点的左孩子肯定为空if (node prev-_left) prev-_left node-_right;else prev-_right node-_right;delete node;}return true;}//中序遍历void InOrder() {_InOrder(_root);std::cout std::endl;}private://中序遍历void _InOrder(Node* root) {if (root nullptr) return;_InOrder(root-_left);std::cout root-_value ;_InOrder(root-_right);}//销毁void Destroy(Node* root) {//利用后续遍历销毁if (root nullptr) return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}private:Node* _root;
};
2.性能分析 二叉搜索树的插入、删除操作都必须先进行查找查找效率代表了二叉搜索树的各个操作的性能。而二叉树的结构取决于给定的序列
1最优情况下二叉搜索树为完全二叉树其平均比较次数为
2最坏情况下二叉搜索树退化为单支树其平均比较次数为N/2
所以二叉搜索树的查找、插入、删除时间复杂度都是O(N)。
