完成目标
二叉查找树框架
1 | template <typename Comparable> |
contains
如果树T中有项为X 的结点,那么contains操作就返回true,没有就返回false。如果T为空,返回false;
如果存储在T中的项为X,就返回true。若两种情况都不成立,就对T的一个子树进行递归调用
1 | //public成员调用private递归成员的函数(保证安全性) |
1 | //private函数contains操作 |
findMin 和 findMax
1 | //递归式findMin |
insert
1 | void insert(const Comparable &x,BinaryNode t){ |
remove
删除一个叶结点其实很简单,拥有一个子结点的删除也很简单。复杂的是拥有两个子结点的结点删除。一般删除策略是找到删除节点右子树中最小的一个数据,最小数据的特征就是没有左子结点了
1 | void remove(const Comparable &x, BinaryNode t){ |
但是如果删除的次数并不多,我们可以使用懒惰删除策略,当一个元素要被删除时,它仍留在树种,而只是做一个被删除的记号。这种做法在有重复项时相当流行。
makeEmpty和析构函数
1 | ~BinarySearchTree(){ |
operator=和clone
1 | const BinarySearchTree & operator= (const BinarySearchTree &rhs){ |
补充
你再去读一读insert
和remove
的代码,你会发现,在某些情况下,这些代码所花费的时间可能会达到O(N^2)的程度。比如插入一个从小到大排好序的数据插入树中,链表实现代价会非常巨大。因为所有结点没有左子节点。
解决办法一般有两个:使用平衡树,任何结点的深度均不可过深。或者放弃平衡条件,使用一种自调整类结构,伸展树。
- 本文作者: TangZ
- 本文链接: http://wstzj.github.io/2020/07/29/学习笔记-二叉查找树的代码实现/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!