【手撕STL】二叉搜索树

二叉搜索树

二叉搜索树

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树

注：

• 二叉搜索树查找一个值最多查找高度次
• 二叉搜索树按中序遍历，值可以从小到大打印出来

二叉搜索树操作

二叉搜索树的插入

a. 树为空，则直接插入

b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

思路：

• 根节点为空，直接插入
• 根节点不为空：
• 1. 如果该节点key==要插入的key ，返回false
• 1. 如果该节点key>要插入的key ，则向该节点的左子树查找（若该节点的左子树为空，则直接插入）
• 1. 如果该节点key<要插入的key ，则向该节点的右子树查找（若该节点的右子树为空，则直接插入）

二叉搜索树的查找

思路：
若根节点不为空：

• 如果根节点key==查找key，返回true
• 如果根节点key>查找key，在其左子树查找
• 如果根节点key<查找key，在其右子树查找 否则返回false

若根节点为空，返回false

二叉搜索树的删除

只有一个孩子节点：
1.

2.

3.

叶子：

有两个孩子节点：
1.

2.

注：有两个孩子节点的，找一个能替代值替代删除（比删除节点的右边的值的要小比删除节点的左边的值的要大（找左树最大节点或者右树最小节点））

总结： 首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点
b.要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
情况d：在它的右子树中寻找最小结点（或者在它的左子树中寻找最大结点），用它的值填补到被删除节点中，再来处理该结点的删除问题

二叉搜索树的实现（递归及非递归）

#pragma once#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>usingnamespace std;template<classK>struct BSTreeNode
{BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}
    BSTreeNode<K>* _left;
    BSTreeNode<K>* _right;
    K _key;};template<classK>classBSTree{typedef BSTreeNode<K> Node;public:// BSTree() = default;  强制编译器自动生成默认构造函数BSTree():_root(nullptr){}//也可写成 BSTree(const BSTree& t)BSTree(const BSTree<K>& t){
        _root =_Copy(t._root);}//BSTree<K>& operator=(BSTree t)
    BSTree<K>&operator=(BSTree<K> t){swap(_root, t._root);return*this;}~BSTree(){_Destroy(_root);}boolInsert(const K& key){if(_root ==nullptr){
            _root =newNode(key);returntrue;}//找出要插入的位置
        Node* parent =nullptr;
        Node* cur = _root;while(cur){if(cur->_key > key){
                parent = cur;
                cur = cur->_left;}elseif(cur->_key < key){
                parent = cur;
                cur = cur->_right;}else{returnfalse;}}
        cur =newNode(key);if(parent->_key > key){
            parent->_left = cur;}else{
            parent->_right = cur;}returntrue;}voidInOrder(){_InOrder(_root);
        cout << endl;}
    Node*Find(const K& key){
        Node* cur = _root;while(cur){if(cur->_key > key){
                cur = cur->_left;}elseif(cur->_key < key){
                cur = cur->_right;}else{return cur;}}returnnullptr;}boolErase(const K& key){
        Node* cur = _root;
        Node* parent =nullptr;while(cur){if(cur->_key > key){
                parent = cur;
                cur = cur->_left;}elseif(cur->_key < key){
                parent = cur;
                cur = cur->_right;}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;}elseif(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* minrightparent = cur;
                    Node* minright = cur->_right;while(minright->_left){
                        minrightparent = minright;
                        minright = minright->_left;}
                    cur->_key = minright->_key;if(minrightparent->_left == minright){
                        minrightparent->_left = minright->_right;}else{
                        minrightparent->_right = minright->_right;}delete minright;}returntrue;}}returnfalse;}//递归版本boolInsertR(const K& key){return_InsertR(_root, key);}

    Node*FindR(const K& key){return_FindR(_root, key);}boolEraseR(const K& key){return_EraseR(_root, key);}private:
    Node*_Copy(Node* root){if(root ==nullptr)returnnullptr;
        Node* newnode =newNode(root->_key);
        newnode->_left =_Copy(root->_left);
        newnode->_right =_Copy(root->_right);return newnode;}void_Destroy(Node* root){if(root ==nullptr){return;}_Destroy(root->_left);_Destroy(root->_right);delete root;}bool_EraseR(Node*& root,const K& key){if(root ==nullptr){returnfalse;}else{if(root->_key > key){return_EraseR(root->_left, key);}elseif(root->_key < key){return_EraseR(root->_right, key);}else{
                Node* del = root;if(root->_left ==nullptr){
                    root = root->_right;}elseif(root->_right ==nullptr){
                    root = root->_left;}else{//替代法删除
                    Node* minright = root->_right;while(minright->_left){
                        minright = minright->_left;}
                    root->_key = minright->_key;//转换成递归在右子树中删除最小节点return_EraseR(root->_right, minright->_key);//注意：转换在递归删除右子树中minright如果右子树越大//付出的代价就越大相当于重新查找了一遍}delete del;returntrue;}}}

    Node*_FindR(Node* root,const K& key){if(root ==nullptr){returnnullptr;}else{if(root->_key > key){return_FindR(root->_left, key);}elseif(root->_key < key){return_FindR(root->_right, key);}else{return root;}}}bool_InsertR(Node*& root,const K& key){if(root ==nullptr){
            root =newNode(key);returntrue;}else{if(root->_key > key){return_InsertR(root->_left, key);}elseif(root->_key < key){return_InsertR(root->_right, key);}else{returnfalse;}}}void_InOrder(Node* root){if(root ==nullptr){return;}_InOrder(root->_left);
        cout << root->_key <<" ";_InOrder(root->_right);}
    Node* _root=nullptr;};

注：尽量使用循环来写，不要用递归。因为递归一方面每次调用函数都要建立栈帧，另一方面递归深度太深会导致栈溢出

二叉搜索树的应用

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

• 以单词集合中的每个单词作为key，构建一棵二叉搜索树
• 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

1. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。比如：实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文，具体实现方式如下：

• <单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较Key
• 查询英文单词时，只需给出英文单词，就可快速找到与其对应的key

K模型：

#pragma once#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>usingnamespace std;//确定一个只是不是在集合中namespace KEY
{template<classK>struct BSTreeNode
    {BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}
        BSTreeNode<K>* _left;
        BSTreeNode<K>* _right;
        K _key;};template<classK>classBSTree{typedef BSTreeNode<K> Node;public:// BSTree() = default;  强制编译器自动生成默认构造函数BSTree():_root(nullptr){}//也可写成 BSTree(const BSTree& t)BSTree(const BSTree<K>& t){
            _root =_Copy(t._root);}//BSTree<K>& operator=(BSTree t)
        BSTree<K>&operator=(BSTree<K> t){swap(_root, t._root);return*this;}~BSTree(){_Destroy(_root);}boolInsert(const K& key){if(_root ==nullptr){
                _root =newNode(key);returntrue;}//找出要插入的位置
            Node* parent =nullptr;
            Node* cur = _root;while(cur){if(cur->_key > key){
                    parent = cur;
                    cur = cur->_left;}elseif(cur->_key < key){
                    parent = cur;
                    cur = cur->_right;}else{returnfalse;}}
            cur =newNode(key);if(parent->_key > key){
                parent->_left = cur;}else{
                parent->_right = cur;}returntrue;}voidInOrder(){_InOrder(_root);
            cout << endl;}
        Node*Find(const K& key){
            Node* cur = _root;while(cur){if(cur->_key > key){
                    cur = cur->_left;}elseif(cur->_key < key){
                    cur = cur->_right;}else{return cur;}}returnnullptr;}boolErase(const K& key){
            Node* cur = _root;
            Node* parent =nullptr;while(cur){if(cur->_key > key){
                    parent = cur;
                    cur = cur->_left;}elseif(cur->_key < key){
                    parent = cur;
                    cur = cur->_right;}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;}elseif(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* minrightparent = cur;
                        Node* minright = cur->_right;while(minright->_left){
                            minrightparent = minright;
                            minright = minright->_left;}
                        cur->_key = minright->_key;if(minrightparent->_left == minright){
                            minrightparent->_left = minright->_right;}else{
                            minrightparent->_right = minright->_right;}delete minright;}returntrue;}}returnfalse;}private:
        Node*_Copy(Node* root){if(root ==nullptr)returnnullptr;
            Node* newnode =newNode(root->_key);
            newnode->_left =_Copy(root->_left);
            newnode->_right =_Copy(root->_right);return newnode;}void_Destroy(Node* root){if(root ==nullptr){return;}_Destroy(root->_left);_Destroy(root->_right);delete root;}void_InOrder(Node* root){if(root ==nullptr){return;}_InOrder(root->_left);
            cout << root->_key <<" ";_InOrder(root->_right);}
        Node* _root =nullptr;};}

KV模型：

#pragma once#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>usingnamespace std;namespace KEY_VALUE
{template<classK,classV>struct BSTreeNode
    {BSTreeNode(const K& key,const V& value):_left(nullptr),_right(nullptr),_key(key),_value(value){}
        BSTreeNode<K,V>* _left;
        BSTreeNode<K,V>* _right;
        K _key;
        V _value;};template<classK,classV>classBSTree{typedef BSTreeNode<K, V> Node;public:// BSTree() = default;  强制编译器自动生成默认构造函数BSTree():_root(nullptr){}BSTree(const BSTree<K, V>& t){
            _root =_Copy(t._root);}

        BSTree<K,V>&operator=(BSTree<K, V> t){swap(_root, t._root);return*this;}~BSTree(){_Destroy(_root);}boolInsert(const K& key,const V& value){if(_root ==nullptr){
                _root =newNode(key, value);returntrue;}//找出要插入的位置
            Node* parent =nullptr;
            Node* cur = _root;while(cur){if(cur->_key > key){
                    parent = cur;
                    cur = cur->_left;}elseif(cur->_key < key){
                    parent = cur;
                    cur = cur->_right;}else{returnfalse;}}
            cur =newNode(key, value);if(parent->_key > key){
                parent->_left = cur;}else{
                parent->_right = cur;}returntrue;}voidInOrder(){_InOrder(_root);
            cout << endl;}
        Node*Find(const K& key){
            Node* cur = _root;while(cur){if(cur->_key > key){
                    cur = cur->_left;}elseif(cur->_key < key){
                    cur = cur->_right;}else{return cur;}}returnnullptr;}boolErase(const K& key){
            Node* cur = _root;
            Node* parent =nullptr;while(cur){if(cur->_key > key){
                    parent = cur;
                    cur = cur->_left;}elseif(cur->_key < key){
                    parent = cur;
                    cur = cur->_right;}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;}elseif(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* minrightparent = cur;
                        Node* minright = cur->_right;while(minright->_left){
                            minrightparent = minright;
                            minright = minright->_left;}
                        cur->_key = minright->_key;if(minrightparent->_left == minright){
                            minrightparent->_left = minright->_right;}else{
                            minrightparent->_right = minright->_right;}delete minright;}returntrue;}}returnfalse;}private:
        Node*_Copy(Node* root){if(root ==nullptr)returnnullptr;
            Node* newnode =newNode(root->_key, root->_value);
            newnode->_left =_Copy(root->_left);
            newnode->_right =_Copy(root->_right);return newnode;}void_Destroy(Node* root){if(root ==nullptr){return;}_Destroy(root->_left);_Destroy(root->_right);delete root;}void_InOrder(Node* root){if(root ==nullptr){return;}_InOrder(root->_left);
            cout << root->_key <<":"<< root->_value << endl;_InOrder(root->_right);}
        Node* _root =nullptr;};}

二叉搜索树的性能分析

• 插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
• 对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
• 但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树查找次数是logN；最差情况下，二叉搜索树查找次数是N