二叉搜索树(BST)的概念及实现与分析
目录
二叉搜索树
概念
BST树的插入
BST树的查找
BST的删除(重要)
应用
性能分析
二叉搜索树
概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
int ar[]={5,3,2,4,8,9,1};
BST树的插入
- 如果树为空则直接插入;
- 如果不为空,则按照二叉搜索树的规则插入.
bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);return true;}Node* cur = _root;Node* parent = nullptr;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, value);if (cur->_key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;}BST树的查找
如果根节点_root->_key==要查找的key 返回查找的结点
如果根节点_root->_key>要查找的key 在其左子树上找
如果根节点_root->_key<要查找的key 在其右子树上找
如果根节点不存在,则返回空指针
Node* 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 cur;}}return nullptr;}BST的删除(重要)
首先根据key查找结点,没有找到返回false;
删除分三种情况
1.要删除的结点左子树为空
- 要删除的是根节点,让根等于右孩子结点
- 要删除的是普通结点并且是其双亲结点的左孩子结点则parent->_left = cur->_right
- 要删除的是普通结点并且是其双亲结点的右孩子结点则parent->_right= cur->_right
2.要删除的结点右子树为空
- 要删除的是根节点,让根等于左孩子结点
- 要删除的是普通结点并且是其双亲结点的左孩子结点则parent->_left = cur->_left;
- 要删除的是普通结点并且是其双亲结点的左孩子结点则parent->_right = cur->_left;
3.删除的结点左右孩子结点都不为空:
我们这里采用替换法完成
找到左子树的最大结点(最右)或者右子树的最小结点
代码如下:
bool Erase(const K& key){//1.寻找结点Node* cur = _root;Node* parent = nullptr;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 (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){if (parent == nullptr){_root = cur->_left;}else{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 替换法删除 左树的最大节点(最右节点) 或者是右树的最小节点(最左节点)Node* Parent = cur; // 这里要注意不能初始化给空Node* minNode = cur->_right;while (minNode->_left){Parent = minNode;minNode = minNode->_left;}swap(cur->_key, minNode->_key);// 转换成删除minNode// 因为minNode是作为空的节点，可以直接删除if (Parent->_right == minNode)Parent->_right = minNode->_right;elseParent->_left = minNode->_right;delete minNode;}return true;}}return false;}应用
根据BST树的特点我们可以实现
1. K模型： K 模型即只有 key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到的值。 比如：给一个单词 word ，判断该单词是否拼写正确，具体方式如下： 以单词集合中的每个单词作为key，构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。 2. KV 模型：每一个关键码 key ，都有与之对应的值 Value ，即性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。 对有 n 个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的 深度的函数，即结点越深，则比较次数越多。 但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树 因此二叉搜索树最好的效率就是像完全二叉树一样其平均比较次数为:本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！