二叉搜索树

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

上述条件反之亦可

查找

接近二分查找，最大查找次数为树的高度，平均查找次数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的节点：

找到此节点中，左子树的最右节点或者右子树的最左节点要删除的节点val替换为最左节点或者最右节点真正要删除的是最左或者最右节点此时问题转换为删除度为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; } }