数据结构——二叉搜索树

一、二叉搜索树概念

二叉搜索树又叫二叉排序树，它或是空树，或是具有以下性质的二叉树：

（1）若它的左子树不为空，则左子树上的所有节点的值都小于根节点的值；

（2）若它的右子树不为空，则右子树上的所有节点的值都大于根节点的值；

（3）它的左右子树也分别为二叉搜索树。

二、二叉搜索树操作

1.二叉搜索树的查找

（1）若根节点为空，则直接返回false，否则进行后续操作；

（2）如果根节点key==查找key，返回ture，否则进行后续操作；

（3）若根节点key>查找key，则在其左子树内进行查找，否则在其右子树内进行查找；

（4）递归上述过程。

2.二叉搜索树的插入

（1）若树为空，则直接插入；

（2）若树不为空，则按二叉搜索树性质查找插入位置，然后插入。

3.二叉搜索树的删除

        首先查找待删除元素是否在二叉搜索树中，没有则直接返回，否则要删除的节点可分为以下四种情况：

（1）待删除节点无孩子节点；

（2）待删除节点只有左孩子；

（3）待删除节点只有右孩子；

（4）待删除节点左右孩子都有。

删除方法：

情况（1）：删除方法与情况（2）和（3）相同；

情况（2）：删除该节点，并使被删除节点的双亲节点指向被删除节点的左孩子节点；

情况（3）：删除该节点，并使被删除节点的双亲节点指向被删除节点的右孩子；

情况（4）：在它的右子树中寻找中序下的第一个节点（值最小的节点），用它的值覆盖掉被删除节点，在处理该节点的删除问题。或找它左子树中最大的节点。

三、二叉搜索的实现

1.代码实现

template<class T>
struct BSTNode {BSTNode(const T& value = T()): _left(nullptr), _right(nullptr), _value(value){}BSTNode<T>* _left;BSTNode<T>* _right;T _value;
};//约定value唯一
template<class T>
class BinarySearchTree {typedef BSTNode<T> Node;
public:BinarySearchTree(): _root(nullptr){}~BinarySearchTree() {Destroy(_root);}//插入bool Insert(const T& value) {//空树if (_root == nullptr) {_root = new Node(value);return true;}//非空Node* cur = _root;Node* parent = nullptr;//保存cur双亲节点//查找插入位置while (cur) {parent = cur;if (value < cur->_value) {cur = cur->_left;}else if (value > cur->_value) {cur = cur->_right;}else {//待插入节点已存在return false;}}//插入新节点cur = new Node(value);if (value > parent->_value) {parent->_right = cur;}else {parent->_left = cur;}return true;}//查找Node* Find(const T& value) {Node* cur = _root;while (cur) {if (value == cur->_value) {return cur;}else if (value < cur->_value) {cur = cur->_left;}else {cur = cur->_right;}}return cur;}//删除bool Erase(const T& value) {if (_root == nullptr) return false;Node* cur = _root;Node* parent = nullptr;//查找待删除节点while (cur) {//parent = cur;不能在这里记录双亲节点，因为有可能cur已经是待删除节点，会直接breakif (value == cur->_value) {break;}else if (value < cur->_value) {parent = cur;cur = cur->_left;}else {parent = cur;cur = cur->_right;}}if (cur == nullptr) return false;//没有待删除节点//删除节点if (cur->_left == nullptr) {//情况1和2if (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) {//情况1和3if (parent == nullptr) {//是根节点且右孩子为空_root = cur->_left;}else {//不是根节点if (cur == parent->_left) parent->_left = cur->_left;else parent->_right = cur->_left;}delete cur;}else {//情况4//查找该节点右子树最小值(或左子树的最大值)Node* prev = cur;Node* node = cur->_right;while (node->_left) {prev = node;node = node->_left;}//覆盖节点值cur->_value = node->_value;//删除节点，该节点的左孩子肯定为空if (node == prev->_left) prev->_left = node->_right;else prev->_right = node->_right;delete node;}return true;}//中序遍历void InOrder() {_InOrder(_root);std::cout << std::endl;}private://中序遍历void _InOrder(Node* root) {if (root == nullptr) return;_InOrder(root->_left);std::cout << root->_value << " ";_InOrder(root->_right);}//销毁void Destroy(Node*& root) {//利用后续遍历销毁if (root == nullptr) return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}private:Node* _root;
};

2.性能分析

        二叉搜索树的插入、删除操作都必须先进行查找，查找效率代表了二叉搜索树的各个操作的性能。而二叉树的结构，取决于给定的序列：

（1）最优情况下：二叉搜索树为完全二叉树，其平均比较次数为；

（2）最坏情况下：二叉搜索树退化为单支树，其平均比较次数为N/2；

所以二叉搜索树的查找、插入、删除时间复杂度都是O(N)。