C++ - 二叉搜索树讲解

二叉搜索树概念和定义

二叉搜索树是一个二叉树，其中每个节点的值都满足以下条件：

• 节点的左子树只包含小于当前节点值的节点。
• 节点的右子树只包含大于当前节点值的节点。
• 左右子树也必须是二叉搜索树。

二叉树搜索树性质

从上面的二叉搜索树定义中可以了解到, 二叉搜索树是有序的.

通过中序遍历, 会发现这是个有序的序列, 升序或降序 (自己决定)

二叉搜索树只支持增删查, 不支持该.
因为如果随意修改二叉搜索树节点的值, 那么就有可能会导致, 这棵树不再满足二叉搜索树的条件.

二叉搜索树的查找的时间复杂度: 
最好情况: O(log n)
最坏情况: O(N)

当二叉搜索树是以上的情况时, 就变成了链表, 那么时间复杂度就是 O(N).

二叉搜索树中是不能出现相同元素的.

二叉搜索树模拟实现

创建一个二叉搜索树节点类

template<class T>
struct SearchTreeNode
{T _data; // 存储数据SearchTreeNode<T>* _leftchile; // 指向左孩子SearchTreeNode<T>* _rightchild; // 指向右孩子SearchTreeNode(const T& data):_data(data),_leftchile(nullptr),_rightchild(nullptr){}
};

二叉搜索树类创建

template<class T>
class SearchTree
{typedef SearchTreeNode<T> SearchTreeNode;
public:bool insert(const T& data){}bool erase(const T& data){}bool find(const T& data){}
private:SearchTreeNode* _root;
};

二叉搜索树的插入

二叉搜索树的插入非常简单.
从根节点开始, 如果插入的值小于节点值, 那么向左走,
如果插入的值大于节点值, 那么向右走,
如果值已存在, 那么直接返回 false.

bool insert(const T& data)
{SearchTreeNode* node = new SearchTreeNode(data);if (_root == nullptr) // 如果 _root 为空, 那么也就需要更新 _root 节点{_root = node;return true;}else{SearchTreeNode* prev = nullptr; // 记录插入位置的父节点SearchTreeNode* cur = _root; // 查找插入位置while (cur != nullptr){if (cur->_data == data) // 如果要插入的数据已存在, 直接返回{return false;}if (data < cur->_data) // 要插入的数据小于节点数据, 向左走{prev = cur;cur = cur->_leftchile;}else // 要插入的数据大于节点数据, 向右走{prev = cur;cur = cur->_rightchild;}}if (data < prev->_data) // 判断要插入的位置是左边还是右边{prev->_leftchile = node;}else{prev->_rightchild = node;}return true;}
}

二叉搜索树的删除

1. 被删除的节点最多只有一个孩子

1) 被删除的节点是叶子节点, 没有孩子

这种情况下, 直接将这个节点删除即可

2) 被删除的节点只有左孩子

将本节点删除后, 将节点的左孩子连接到本节点的父节点上

3) 被删除的节点只有右孩子

和只有左孩子相同, 删除本节点, 右孩子连接到本节点的父节点上

void erase(const T& data)
{SearchTreeNode* prev = nullptr;SearchTreeNode* cur = _root;while (cur != nullptr) // 先查找是否存在这个值{if (data == cur->_data){break;}prev = cur;if (data < cur->_data){cur = cur->_leftchile;}else{cur = cur->_rightchild;}}if (cur == nullptr) // 不存在这个值, 直接返回{return;}if (cur->_leftchile == nullptr || cur->_rightchild == nullptr) // 存在这个节点, 这个节点没有孩子, 或者只有一个孩子{if (cur->_leftchile == nullptr) // 只有右孩子{if (_root == cur) // 如果要删除的节点就是 _root, 更新 _root{_root = cur->_rightchild;}else{if (prev->_leftchile = cur) // 判断要连接再父节点的哪边{prev->_leftchile = cur->_rightchild;}else{prev->_rightchild = cur->_rightchild;}}}else{if (_root == cur){_root = cur->_leftchile;}else{if (prev->_leftchile = cur){prev->_leftchile = cur->_leftchile;}else{prev->_rightchild = cur->_leftchile;}}}delete cur;}
}

2. 被删除的节点有两个孩子

我们不直接删除这个节点, 使用和 堆 删除节点差不多的方法.

我们将要删除的这个节点和一个最多只有一个孩子的节点进行交换

然后删除那个交换后的值.

那么这个交换的节点怎么选择.

1. 本节点右子树中的最小值的那个节点 (即右子树的最左节点)

2. 本节点左子树中的最大值的那个节点 (左子树的最右节点)

这两个选择方法, 选择出来的要交换的节点的值, 都是最接近 本节点值的 节点.

 找到这个节点之后, 交换 cur 和 child 的值, 然后删除 child 节点即可.

void erase(const T& data)
{SearchTreeNode* prev = nullptr;SearchTreeNode* cur = _root;while (cur != nullptr) // 先查找是否存在这个值{if (data == cur->_data){break;}prev = cur;if (data < cur->_data){cur = cur->_leftchile;}else{cur = cur->_rightchild;}}if (cur == nullptr) // 不存在这个值, 直接返回{return;}if (cur->_leftchile == nullptr || cur->_rightchild == nullptr) // 存在这个节点, 这个节点没有孩子, 或者只有一个孩子{if (cur->_leftchile == nullptr){if (_root == cur){_root = cur->_rightchild;}else{if (prev->_leftchile = cur){prev->_leftchile = cur->_rightchild;}else{prev->_rightchild = cur->_rightchild;}}}else{if (_root == cur){_root = cur->_leftchile;}else{if (prev->_leftchile = cur){prev->_leftchile = cur->_leftchile;}else{prev->_rightchild = cur->_leftchile;}}}delete cur;}else // 这个节点有两个孩子, 上半部分代码 和 文章上面的代码是一样的{prev = cur;SearchTreeNode* child = cur->_rightchild; // 要删除的节点while (child->_leftchile != nullptr) // 查找符合要求的节点{prev = child;child = child->_leftchile;}cur->_data = child->_data; // 交换数据if (child->_rightchild == nullptr) // child 是叶子节点{if (prev == cur) // 可以看下图演示{prev->_rightchild = nullptr;}else{prev->_leftchile = nullptr;}}else // child 有右子树, 这不可能有左子树, 因为这里找的就是最左节点{if (prev == cur){prev->_rightchild = cur->_rightchild;}else{prev->_leftchile = child->_rightchild;}}delete child;}
}

那么另一种方法, 和这种方法差不多, 会一种就会另一种. 
去本节点左子树中, 查找最右的节点.

至于查找功能, 无论是再插入还是删除中, 都有这部分操作.