二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
平均情况下插入查找删除元素是Onlgn，最差情况下是On的
为什么要实现二叉搜索树？
由二叉搜索树发展来的红黑树是set/map的底层容器，为了学习的梯度我们先基于二叉搜索树来完成set和map。
二叉搜索树的结点设计
template<typename T>
struct BSnode
{
BSnode():left(nullptr),parent(nullptr),right(nullptr){}
T data;
struct BSnode* parent;
struct BSnode* left;
struct BSnode* right;
};
二叉搜索树的迭代器设计
template<typename T>
class BStree_base_iterator : public bidirectional_iterator<T>
{
public:
typedef BSnode<T>* ptr;
ptr node;
BStree_base_iterator()
{
node = nullptr;
}
BStree_base_iterator(ptr p)
{
node = p;
}
void increment()
{
if (node->right == nullptr)
{
ptr pre = node->parent;
//回溯 在这里node==pre->right 等价于 node>pre
while (pre != nullptr&&node == pre->right)
{
node = pre;
pre = node->parent;
}
if (pre == nullptr)
node = nullptr;
else
node = pre;
}
else//下一个结点是比自己大的结点（右子树）中最小的（最左）
{
node = node->right;
while (node->left)
node = node->left;
}
}
void decrement()
{
if (node->left == nullptr)
{
ptr pre = node->parent;
while (pre != nullptr&&node == pre->left)
{
node = pre;
pre = node->parent;
}
if (pre == nullptr)
node = nullptr;
else
node = pre;
}
else
{
node = node->left;
while (node->right)
node = node->right;
//return node;
}
}
};
template<typename T>
class BStree_iterator //加一层封装
{
public:
typedef BSnode<T>* ptr;
typedef BStree_iterator<T> self;
BStree_base_iterator<T> p;
BStree_iterator()
{
p.node = nullptr;
}
BStree_iterator(ptr _p)
{
p.node = _p;
}
self& operator++(int)
{
p.increment();
return *this;
}
self& operator--(int)
{
p.decrement();
return *this;
}
bool operator!=(const BStree_iterator<T>& rhs)
{
return !(*this == rhs);
}
bool operator==(const BStree_iterator<T>& rhs)
{
return this->p.node == rhs.p.node;
}
T& operator*()
{
return p.node->data;
}
T& operator->()
{
return &(*this);
}
};
二叉搜索树源码
插入删除查找元素都可以利用和节点的值进行比较来递归查找，为了避免stackoverflow可以使用递归函数的非递归形式
template<typename T >
class BStree
{
public:
typedef T value_type;
typedef T* pointer;
typedef size_t size_type;
typedef BSnode<T>* node_ptr;
typedef BStree<T> self;
typedef BStree_iterator<T> iterator;
private:
// Compare comparator;
node_ptr node;
size_t data_cnt;//元素个数
std::allocator<BSnode<T>> data_allocator;
node_ptr new_node(const value_type& val,node_ptr pre)//建立新节点
{
node_ptr p = data_allocator.allocate(1);
new(&p->data) value_type(val);
p->left = nullptr;
p->right = nullptr;
p->parent = pre;
return p;
}
node_ptr insert_aux(node_ptr p, node_ptr pre,const value_type& val, node_ptr& ret)
{
while (p)
{
if (p->data == val) return p;
pre = p;
p = p->data > val ? p->left : p->right;
}
return new_node(val, pre);
/* 递归版本 数目太多会stackoverflow
if(!p)
{
return ret = new_node(val, pre);
}
if (p->data > val)
p->left = insert_aux(p->left, p, val, ret);
else if (p->data < val)
p->right = insert_aux(p->right, p, val, ret);
else
ret = p;
return p;*/
}
iterator find_aux(node_ptr p, const value_type& val)
{
while (p && p->data != val)
{
p = p->data > val ? p->left : p->right;
}
return iterator(p);
}
void del()
{
ministl::queue<node_ptr> q;
q.push(node);
while (!q.empty())
{
node_ptr p = q.front();
q.pop();
if (p->left)
{
q.push(p->left);
}
if (p->right)
{
q.push(p->right);
}
//删除之前保证左右子树入队 否则会有内存泄露
delete p;
}
node = nullptr;
}
//删除操作，分四种情况
//1. 左右子树为空，删除结点 并且将其父节点对应指针设置为空即可
//2. 左子树空 右不空 删除结点 并且将其父节点对应指针设置为右子树即可
//3. 左不空 右空 删除结点 并且将其父节点对应指针设置为左子树即可
//4. 左右不空 找到左子树中值最大的元素 和结点元素交换
void erase_aux(node_ptr p)
{
if (p->left == nullptr&&p->right == nullptr)
{
if (p->parent == nullptr)
{
node = nullptr;
}
else if (p->parent->left!=nullptr && p->parent->left->data == p->data)
p->parent->left = nullptr;
else if (p->parent->right!=nullptr && p->parent->right->data == p->data)
p->parent->right = nullptr;
delete(p);
}
else if (p->left == nullptr&&p->right != nullptr)
{
if (p->parent == nullptr)
{
node = p->right,node->parent = nullptr;
}
else if (p->parent->left!=nullptr && p->parent->left->data == p->data)
p->parent->left = p->right, p->right->parent = p->parent;
else if (p->parent->right!=nullptr && p->parent->right->data == p->data)
p->parent->right = p->right, p->right->parent = p->parent;
delete(p);
}
else if (p->left != nullptr&&p->right == nullptr)
{
if (p->parent == nullptr)
{
node = p->left, node->parent = nullptr;
}
else if (p->parent->left!=nullptr && p->parent->left->data == p->data)
p->parent->left = p->left, p->left->parent = p->parent;
else if (p->parent->right!=nullptr && p->parent->right->data == p->data)
p->parent->right = p->left, p->left->parent = p->parent;
delete(p);
}
else
{
node_ptr it = p->left;
node_ptr tmp = p;
while (it->right != nullptr)
{
tmp = it, it = it->right;
}
p->data = it->data;
if (tmp != p)
{
tmp->right = it->left;
}
else
{
tmp->left = it->left;
}
if (it->left != nullptr)
it->left->parent = tmp;
delete(it);
}
}
iterator lower_bound_aux(node_ptr p, const value_type& x)
{
if (!p)
return iterator(nullptr);
if (p->data >= x)
{
auto tmp = lower_bound_aux(p->left, x);
if (tmp.p.node != nullptr)
return tmp;
else
return iterator(p);
}
else
return lower_bound_aux(p->right, x);
}
iterator upper_bound_aux(node_ptr p, const value_type& x)
{
if (!p)
return iterator(nullptr);
if (p->data > x)
{
auto tmp = upper_bound_aux(p->left, x);
if (tmp.p.node != nullptr)
return tmp;
else
return iterator(p);
}
else
return upper_bound_aux(p->right, x);
}
void erase_val_aux(node_ptr p,const value_type& key)
{
if (p == nullptr)
return;
if (p->data == key)
erase_aux(p);
else if (p->data < key)
erase_val_aux(p->right, key);
else if (p->data > key)
erase_val_aux(p->left, key);
}
public:
BStree() :node(nullptr),data_cnt(0) {}
bool empty()
{
return node == nullptr;
}
size_type size()
{
return data_cnt;
}
iterator begin()
{
if (node == nullptr)
{
iterator t(nullptr);
return t;
}
iterator it(node);
while (it.p.node->left != nullptr)
it.p.node = it.p.node->left;
return it;
}
iterator end()
{
iterator it(nullptr);
return (it);
}
iterator find_max()
{
node_ptr p = node;
if (p == nullptr)
return iterator(nullptr);
while (p->right != nullptr)
p = p->right;
return iterator(p);
}
node_ptr root()
{
return node;
}
pair<iterator,bool> insert(const value_type& val)
{
node_ptr ret = nullptr;
node = insert_aux(node, nullptr, val, ret);
data_cnt++;
return make_pair<iterator, bool>(ret , ret == nullptr);
}
iterator find(const value_type& key)
{
return find_aux(node, key);
}
iterator lower_bound(const value_type& x)
{
return lower_bound_aux(node, x);
}
iterator upper_bound(const value_type& x)
{
return upper_bound_aux(node, x);
}
void erase(iterator pos)
{
erase_aux(pos.p.node);
data_cnt--;
}
void erase(const value_type& x)
{
erase_val_aux(node, x);
data_cnt--;
}
void clear()
{
del();
data_cnt = 0;
}
};