二叉搜索树的简单实现

二叉搜索树

• 若左子树非空，则左子树上所有节点的值都小于根节点的值
• 若右子树非空，则右子树上所有节点的值都小根节点的值
• 左右子树也是二叉搜索树

上述条件反之亦可

查找

接近二分查找，最大查找次数为树的高度，平均查找次数Log₂ N

template <class T>
struct BSTNode
{
  T _val;
  BSTNode<T>* _left;
  BSTNode<T>* _right;
  
  BSTNode(const T& val = T())
    :	_val(val)
    , _left(nullptr)
    , _right(nullptr)
    {	}
};

template <class T>
class BSTree
{
public:
  typedef BSTNode<T> Node;
  
  Node* find(const T& val)
  {
    Node* cur = _root;
    while(cur)
    {
      if(cur->_val == val){
        return cur;        
      }else if(cur->_val < val){
        cur = cur->right;
      }else if(cur->_val > val){
        cur = cur->left;
      }
    }
    return nullptr;
  }
private:
  Node* _root = nullptr;
};

插入

如果树中已存在需要插入的数据，则不重复插入

插入位置为：叶子，子树不完全的非叶子结点，即度为0或者1的节点位置

bool insert(const T& val)
{
  if(_root == nullptr)
  {
    _root = new Node(val);
    return true;
  }
  Node* cur = _root;
  Node* parent = nullptr;
  while(cur)
  {
    parent = ur;
    if(cur->_val == val)
      return false;
    else if(cur->_val < val)
      cur = cur->_right;
    else
      cur = cur->_left;
  }
  cur = new Node(val);
  if(parent->_val < val)
    parent->_right = Node;
  else
    parent->_left = cur;
  return true;
}

删除

有以下四种情况

a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点

• 左子树：左子树的最右节点是所有左子树中最大的节点

• 右子树：右子树的最左节点是所有右子树中最小的节点

删除度为2的节点：

1. 找到此节点中，左子树的最右节点或者右子树的最左节点
2. 要删除的节点val替换为最左节点或者最右节点
3. 真正要删除的是最左或者最右节点
4. 此时问题转换为删除度为0或者度为1的节点

bool erase(const T& val)
 {
  //查找
  Node* cur = _root;
  Node* parent = nullptr;
  while (cur)
  {
	  if (cur->_val == val) {
		  break;
	  }
	  else if(cur->_val < val){
		  parent = cur;
		  cur = cur->_right;
	  }
	  else {
		  parent = cur;
		  cur = cur->_left;
	  }
  }
  //判断是否找到需要删除的节点
  if (cur == nullptr)
	  return false;
  //删除操作
  //1. 叶子
  if (cur->_left == nullptr && cur->_right == nullptr)
  {
	  if (cur == _root)
	  {
		  _root = nullptr;
	  }
	  else
	  {
		if (parent->_left == cur)
			parent->_left = nullptr;
		else
			parent->_right = nullptr;
	  }
	  delete cur;
  }
  //2.左孩子为空
  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;
  }
  //3.右孩子为空
  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;
  }
  //4.左右孩子都存在
  else
  {
	  //a.照最左或最右节点
	  //找右子树的最左节点
	  Node* leftMostChild = cur->_right;
	  Node* parent = cur;
	  while (leftMostChild->_left)
	  {
		  parent = leftMostChild;
		  leftMostChild = leftMostChild->_left;
	  }
	  //b.值替换
	  cur->_val = leftMostChild->_val;
	  //c.删除最左或最右节点
	  if (parent->_left == leftMostChild)
		  parent->_left = leftMostChild->_right;
	  else
		  parent->_right = leftMostChild->_right;

	  delete leftMostChild;
  }
 }