什么网站免费做推广,电子商务网站建设有什么意义,软件开发流程八个步骤模板,广告公关公司文章目录1.二叉查找树概念2.二叉查找树操作2.1 查找2.2 插入2.3 删除2.4 其他3. 支持重复数据的二叉查找树4 有散列表了#xff0c;还需要二叉查找树#xff1f;5 代码实现1.二叉查找树概念
二叉查找树要求#xff0c;在树中的任意一个节点#xff0c;其左子树中的每个节点…
文章目录1.二叉查找树概念2.二叉查找树操作2.1 查找2.2 插入2.3 删除2.4 其他3. 支持重复数据的二叉查找树4 有散列表了还需要二叉查找树5 代码实现1.二叉查找树概念
二叉查找树要求在树中的任意一个节点其左子树中的每个节点的值都要小于这个节点的值而右子树节点的值都大于这个节点的值。
2.二叉查找树操作
2.1 查找 2.2 插入 2.3 删除 2.4 其他
支持快速地查找最大节点和最小节点、前驱节点和后继节点。中序遍历二又查找树可以输出有序的数据序列时间复杂度是 O(n) 非常高效。因此二叉查找树也叫作二叉排序树。
3. 支持重复数据的二叉查找树
通过链表和支持动态扩容的数组等数据结构把值相同的数据都存储在同一个节点上。每个节点仍然只存储一个数据。在查找插入位置的过程中如果碰到一个节点的值与要插入数据的值相同我们就将这个要插入的数据放到这个节点的右子树也就是说把这个新插入的数据当作大于这个节点的值来处理。 在二叉查找树中查找、插入、删除等很多操作的时间复杂度都跟树的高度成正比。两个极端情况的时间复杂度分别是 O(n) 和 O(logn) 分别对应二叉树退化成链表的情况和完全二叉树。为了避免时间复杂度的退化针对二又查找树我们又设计了一种更加复杂的树平衡二叉查找树时间复杂度可以做到稳定的 O(logn)
4 有散列表了还需要二叉查找树
散列表时间复杂度可以做到常量级的O(1), 而二叉查找树在比较平衡的情况下, 时间复杂度才是 O(logn), 相对散列表,好像并没有什么优势,那我们为什么还要用二叉查找树呢? 几个原因:第一, 散列表中的数据是无序存储的, 如果要输出有序的数据,需要先进行排序.而对于二叉查找树来说,我们只需要中序遍历,就可以在O(n)的时间复杂度内,输出有序的数据序列.第二, 散列表扩容耗时很多,而且当遇到散列冲突时,性能不稳定,尽管二叉查找树的性能不稳定,但是在工程中,我们最常用的平衡二叉查找树的性能非常稳定,时间复杂度稳定在O(logn).第三, 尽管散列表的查找等操作的时间复杂度是常量级的,但因为哈希冲突的存在,这个常量不一定比 logn 小,所以实际的查找速度可能不一定比 O(logn) 快. 加上哈希函数的耗时,也不一定就比平衡二又查找树的效率高.第四, 散列表的构造比二又查找树要复杂,需要考虑的东西很多. 比如散列函数的设计、冲突解决办法、扩容、缩容等.平衡二又查找树只需要考虑平衡性这一个问题,而且这个问题的解决方案比较成熟、固定.最后,为了避免过多的散列冲突,散列表装载因子不能太大,特别是基于开放寻址法解决冲突的散列表,不然会浪费一定的存储空间.综合这几点, 平衡二又查找树在某些方面还是优于散列表的, 所以,这两者的存在并不冲突. 我们在实际的开发过程中,需要结合具体的需求来选择使用哪一个.
5 代码实现
/*** description: 二叉查找树* author: michael ming* date: 2019/5/16 23:48* modified by: */
#include iostream
#include random
#include time.h
using namespace std;
template class T
class BSTNode
{
public:T data;BSTNodeT *left, *right;BSTNode():left(NULL), right(NULL){}BSTNode(const T d, BSTNodeT *l NULL, BSTNodeT *r NULL){data d; left l; right r;}
};
template class T
class BST
{
private:BSTNodeT* root;int nodeLen;
public:BST():root(NULL){}~BST(){clear(root);root NULL;}void clear(BSTNodeT* nodeP){if(nodeP NULL)return;if (nodeP NULL)return;clear(nodeP-left);clear(nodeP-right);delete nodeP;}BSTNodeT* get_root() const { return root; }bool isEmpty() const { return root NULL; }T* search(const T d) const{return search(d, root);}T* search(const T d, BSTNodeT* p) const{while(p ! NULL){if(d p-data)return (p-data);else if(d p-data)p p-left;elsep p-right;}return 0;}T* get_max_data(){if(root NULL)return NULL;BSTNodeT* temp root;while(temp-right ! NULL)temp temp-right;return temp-data;}T* get_min_data(){if(root NULL)return NULL;BSTNodeT* temp root;while(temp-left ! NULL)temp temp-left;return temp-data;}void insert(const T d){BSTNodeT *p root, *prev NULL;while(p ! NULL){prev p;if(d p-data)p p-left;elsep p-right;}if(root NULL)root new BSTNodeT(d);else if(d prev-data)prev-left new BSTNodeT(d);elseprev-right new BSTNodeT(d);}void del(T d){if(root NULL)return;BSTNodeT *p root, *pfather NULL;while(p ! NULL p-data ! d){pfather p;if(d p-data)p p-right;elsep p-left;}if(p NULL) //没找到dreturn;if(p-left ! NULL p-right ! NULL)//要删除的节点有2个子节点{BSTNodeT *minP p-right, *minPFather p;//找到右子树最小的跟要删的交换while(minP-left ! NULL) //右子树最小的肯定在左节点{minPFather minP;minP minP-left;}p-data minP-data; //把右子树最小的数付给要删除的节点datap minP; //minP付给p删除ppfather minPFather;}//要删除的是叶节点或者只有1个节点BSTNodeT* child;if(p-left ! NULL)child p-left;else if(p-right ! NULL)child p-right;elsechild NULL;if(pfather NULL)//p是根节点root child;else if(p pfather-left)pfather-left child;elsepfather-right child;delete p;p NULL;}int get_height(BSTNodeT* nodep) //递归法, 求左右子树高度较大的1{if(nodep NULL)return 0;int leftheight get_height(nodep-left);int rightheight get_height(nodep-right);return max(leftheight, rightheight) 1;}void inOrderPrint(BSTNodeT* nodep) //二叉查找树用中序打印是有序的{if (nodep NULL)return;inOrderPrint(nodep-left);cout nodep-data ;inOrderPrint(nodep-right);}
};int main()
{BSTint intBST;srand(time(0));for(int i 0; i 6; i){intBST.insert(rand());}intBST.insert(7);if(intBST.search(7))cout *(intBST.search(7)) endl;cout BST height: intBST.get_height(intBST.get_root()) endl;intBST.inOrderPrint(intBST.get_root());cout max : *(intBST.get_max_data()) , min : *(intBST.get_min_data()) endl;intBST.del(7);intBST.inOrderPrint(intBST.get_root());return 0;
}
