神之右手——二叉搜索树的实现-阿里云开发者社区

前言

为什么要说是神之右手呢？因为它的实现通过引用&，来使代码变得优雅，优雅永不过时~

在实现二叉搜索树之前，我们先回顾一下二叉树的基本概念

二叉搜索树基本概念

二叉查找（搜索）树又称二叉排序树（简称BST），其定义为：二叉排序树或者是空树，或者是满足如下性质（BST性质）的二叉树：

 若它的左子树非空，则左子树上所有结点值（指关键字值）均小于根结点值；

 若它的右子树非空，则右子树上所有结点值均大于根结点值；

 左、右子树本身又各是一棵二叉排序树。

注意：二叉排序树中没有相同关键字的结点。

下面是几个例子，不妨试着判断一下

二叉树的操作

在实现代码之前，我们还要知道它需要哪些功能以及实现的思路是什么？

假设有这么一颗二叉搜索树

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

1. 二叉搜索树的查找

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

b、最多查找高度次，走到到空，还没找到，这个值不存在。

代码：

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;
  }

2. 二叉搜索树的插入

插入的具体过程如下：

a. 树为空，则直接新增节点，赋值给root指针

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

譬如：

非常简单是不是？只需要按节点判断大小就可以了~

代码：

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;
}

3. 二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情

况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程

如下：

情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除

看下图，假设要删除14，那么就要将10的右节点指向13，所以我们还需要设置一个父节点变量存储要删除对象的父节点。下同

情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除

看下图，假设要删除4，就要将6的左节点指向4的右节点5

情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除

以下图为例，假如删除3，就要去3的右子树找最小值（或者3的左子树的最大值），将他们的值交换，再删除原本4所在的节点

不优雅的版本：

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
        {
            // 一个孩子--左为空 or 右为空
            // 两个孩子 -- 替换法
            if (cur->_left == nullptr)
            {
                //if (parent == nullptr)
                if (cur == _root)
                {
                    _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)
                if (cur == _root)
                {
                    _root = cur->_left;
                }
                else
                {
                    if (cur == parent->_left)
                    {
                        parent->_left = cur->_left;
                    }
                    else
                    {
                        parent->_right = cur->_left;
                    }
                }
                delete cur;
            }
            else // 两个孩子都不为空
            {
                // 右子树的最小节点替代
                Node* minParent = cur;
                Node* minRight = cur->_right;
                while (minRight->_left)
                {
                    minParent = minRight;
                    minRight = minRight->_left;
                }
                swap(minRight->_key, cur->_key);
                //cur->_key = minRight->_key;
                //防止删除节点是根节点
                if (minParent->_left == minRight)
                {
                    minParent->_left = minRight->_right;
                }
                else
                {
                    minParent->_right = minRight->_right;
                }
                delete minRight;
            }
            return true;
        }
    }
    return false;
}

是不是感觉很复杂？那么更优雅的是怎么写呢？

神之一手就是利用递归和引用，往下传的时候，传递的是root->right的别名，可以这么理解，它传的不是值而是原来一整颗树的地址，它可以使被删除的节点的父节点指向被删除的节点的子节点，root->right=root->right->right,应该很好理解，不用再单独设置一个变量存储父节点了。你就说优雅不优雅~

bool _EraseR(Node*& root, const K& key)
{
    if (root == nullptr)
        return false;
    if (root->_key < key)
    {
        return _EraseR(root->_right, key);
    }
    else if (root->_key > key)
    {
        return _EraseR(root->_left, key);
    }
    else
    {
        Node* del = root;
        // 删除
        if (root->_left == nullptr)
        {
            root = root->_right;
        }
        else if (root->_right == nullptr)
        {
            root = root->_left;
        }
        else
        {
            Node* minRight = root->_right;
            while (minRight->_left)
            {
                minRight = minRight->_left;
            }
            swap(root->_key, minRight->_key);
            return _EraseR(root->_right, key);
        }
        delete del;
        return true;
    }
}

当然查找和插入也能这样写

bool _InsertR(Node*& root, const K& key)
{
    if (root == nullptr)
    {
        root = new Node(key);
        return true;
    }
    if (root->_key < key)
        return _InsertR(root->_right, key);
    else if (root->_key > key)
        return _InsertR(root->_left, key);
    else
        return false;
}
bool _FindR(Node* root, const K& key)
{
    if (root == nullptr)
        return false;
    if (root->_key < key)
    {
        return _FindR(root->_right, key);
    }
    else if (root->_key > key)
    {
        return _FindR(root->_left, key);
    }
    else
    {
        return true;
    }
}

二叉搜索树的实现

namespace key
{
  template<class K>
  //struct BinarySearchTreeNode
    //设计节点    
  struct BSTreeNode
  {
    BSTreeNode<K>* _left;
    BSTreeNode<K>* _right;
    K _key;
    BSTreeNode(const K& key)
      :_left(nullptr)
      , _right(nullptr)
      , _key(key)
    {}
  };
  template<class K>
  class BSTree
  {
    typedef BSTreeNode<K> Node;
  private:
        //利用递归销毁所有节点
    void DestroyTree(Node* root)
    {
      if (root == nullptr)
        return;
      DestroyTree(root->_left);
      DestroyTree(root->_right);
      delete root;
    }
    //拷贝函数
    Node* CopyTree(Node* root)
    {
      if (root == nullptr)
        return nullptr;
      Node* copyNode = new Node(root->_key);
      copyNode->_left = CopyTree(root->_left);
      copyNode->_right = CopyTree(root->_right);
      return copyNode;
    }
  public:
    // 强制编译器自己生成构造
    // C++11
    BSTree() = default;
    BSTree(const BSTree<K>& t)
    {
      _root = CopyTree(t._root);
    }
    // t1 = t2
        //自定义操作符“=”的功能
    BSTree<K>& operator=(BSTree<K> t)
    {
      swap(_root, t._root);
      return *this;
    }
    //重写析构函数，利用DestroyTree函数
    ~BSTree()
    {
      DestroyTree(_root);
      _root = nullptr;
    }
    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;
    }
    //const Node* Find(const K& key)
    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
        {
          // 一个孩子--左为空 or 右为空
          // 两个孩子 -- 替换法
          if (cur->_left == nullptr)
          {
            //if (parent == nullptr)
            if (cur == _root)
            {
              _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)
            if (cur == _root)
            {
              _root = cur->_left;
            }
            else
            {
              if (cur == parent->_left)
              {
                parent->_left = cur->_left;
              }
              else
              {
                parent->_right = cur->_left;
              }
            }
            delete cur;
          }
          else // 两个孩子都不为空
          {
            // 右子树的最小节点替代
            Node* minParent = cur;
            Node* minRight = cur->_right;
            while (minRight->_left)
            {
              minParent = minRight;
              minRight = minRight->_left;
            }
            swap(minRight->_key, cur->_key);
            //cur->_key = minRight->_key;
            if (minParent->_left == minRight)
            {
              minParent->_left = minRight->_right;
            }
            else
            {
              minParent->_right = minRight->_right;
            }
            delete minRight;
          }
          return true;
        }
      }
      return false;
    }
///下面函数均调用私有成员，使得与外界隔绝，相当于黑盒
    void InOrder()
    {
      _InOrder(_root);
      cout << endl;
    }
    bool FindR(const K& key)
    {
      return _FindR(_root, key);
    }
    bool InsertR(const K& key)
    {
      return _InsertR(_root, key);
    }
    bool EraseR(const K& key)
    {
      return _EraseR(_root, key);
    }
  private:
        /优雅永不过时
    bool _EraseR(Node*& root, const K& key)
    {
      if (root == nullptr)
        return false;
      if (root->_key < key)
      {
        return _EraseR(root->_right, key);
      }
      else if (root->_key > key)
      {
        return _EraseR(root->_left, key);
      }
      else
      {
        Node* del = root;
        // 删除
        if (root->_left == nullptr)
        {
          root = root->_right;
        }
        else if (root->_right == nullptr)
        {
          root = root->_left;
        }
        else
        {
          Node* minRight = root->_right;
          while (minRight->_left)
          {
            minRight = minRight->_left;
          }
          swap(root->_key, minRight->_key);
          return _EraseR(root->_right, key);
        }
        delete del;
        return true;
      }
    }
    bool _InsertR(Node*& root, const K& key)
    {
      if (root == nullptr)
      {
        root = new Node(key);
        return true;
      }
      if (root->_key < key)
        return _InsertR(root->_right, key);
      else if (root->_key > key)
        return _InsertR(root->_left, key);
      else
        return false;
    }
    bool _FindR(Node* root, const K& key)
    {
      if (root == nullptr)
        return false;
      if (root->_key < key)
      {
        return _FindR(root->_right, key);
      }
      else if (root->_key > key)
      {
        return _FindR(root->_left, key);
      }
      else
      {
        return true;
      }
    }
    void _InOrder(Node* root)
    {
      if (root == nullptr)
        return;
      _InOrder(root->_left);
      cout << root->_key << " ";
      _InOrder(root->_right);
    }
  private:
    Node* _root = nullptr;
  };
}

二叉搜索树的应用

讲了这么多怎么实现，现在讲讲它有哪些应用

K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树

在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。

该种方式在现实生活中非常常见：

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；

再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对

namespace key_value
{
    #pragma once
  template<class K, class V>
  struct BSTreeNode
  {
    BSTreeNode<K, V>* _left;
    BSTreeNode<K, V>* _right;
    const K _key;
    V _value;
    BSTreeNode(const K& key, const V& value)
      :_left(nullptr)
      , _right(nullptr)
      , _key(key)
      , _value(value)
    {}
  };
  template<class K, class V>
  class BSTree
  {
    typedef BSTreeNode<K, V> Node;
  public:
    void InOrder()
    {
      _InOrder(_root);
      cout << endl;
    }
    ///
    Node* FindR(const K& key)
    {
      return _FindR(_root, key);
    }
    bool InsertR(const K& key, const V& value)
    {
      return _InsertR(_root, key, value);
    }
    bool EraseR(const K& key)
    {
      return _EraseR(_root, key);
    }
  private:
    bool _EraseR(Node*& root, const K& key)
    {
      if (root == nullptr)
        return false;
      if (root->_key < key)
      {
        return _EraseR(root->_right, key);
      }
      else if (root->_key > key)
      {
        return _EraseR(root->_left, key);
      }
      else
      {
        Node* del = root;
        // 删除
        if (root->_left == nullptr)
        {
          root = root->_right;
        }
        else if (root->_right == nullptr)
        {
          root = root->_left;
        }
        else
        {
          Node* minRight = root->_right;
          while (minRight->_left)
          {
            minRight = minRight->_left;
          }
          swap(root->_key, minRight->_key);
          return _EraseR(root->_right, key);
        }
        delete del;
        return true;
      }
    }
    bool _InsertR(Node*& root, const K& key, const V& value)
    {
      if (root == nullptr)
      {
        root = new Node(key, value);
        return true;
      }
      if (root->_key < key)
        return _InsertR(root->_right, key, value);
      else if (root->_key > key)
        return _InsertR(root->_left, key, value);
      else
        return false;
    }
    Node* _FindR(Node* root, const K& key)
    {
      if (root == nullptr)
        return nullptr;
      if (root->_key < key)
      {
        return _FindR(root->_right, key);
      }
      else if (root->_key > key)
      {
        return _FindR(root->_left, key);
      }
      else
      {
        return root;
      }
    }
    void _InOrder(Node* root)
    {
      if (root == nullptr)
        return;
      _InOrder(root->_left);
      cout << root->_key << ":" << root->_value << endl;
      _InOrder(root->_right);
    }
  private:
    Node* _root = nullptr;
  };
  void TestBSTree1()
  {
    BSTree<string, string> ECDict;
    ECDict.InsertR("root", "根");
    ECDict.InsertR("string", "字符串");
    ECDict.InsertR("left", "左边");
    ECDict.InsertR("insert", "插入");
    //...
    string str;
    while (cin >> str)  //while (scanf() != EOF)
    {
      //BSTreeNode<string, string>* ret = ECDict.FindR(str);
      auto ret = ECDict.FindR(str);
      if (ret != nullptr)
      {
        cout << "对应的中文:" << ret->_value << endl;
        //ret->_key = "";
        ret->_value = "";
      }
      else
      {
        cout << "无此单词，请重新输入" << endl;
      }
    }
  }
  void TestBSTree2()
  {
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    // 水果出现的次数
    BSTree<string, int> countTree;
    for (const auto& str : arr)
    {
      auto ret = countTree.FindR(str);
      if (ret == nullptr)
      {
        countTree.InsertR(str, 1);
      }
      else
      {
        ret->_value++;  // 修改value
      }
    }
    countTree.InOrder();
  }
}

二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：log2n

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：n

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？

这就是我们后面要讲的AVL树和红黑树了

📍后记

本篇讲述了二叉搜索树的基本概念及相关操作的实现，以及实现的凡人版和优雅版，使用神之一手的递归和引用简化代码，最后讲述了它的应用和性能分析，希望大家不吝点赞啊~

神之右手——二叉搜索树的实现

热门文章

最新文章

相关电子书