jsp购物网站开发环境,辽宁好的百度seo公司,网站建设构成技术要求,成都个人网站制作公司什么是搜索树
搜索树是一种树形数据结构#xff0c;用于高效地存储和检索数据。其核心特点是每个节点包含一个键#xff08;Key#xff09;#xff0c;并遵循特定的排序规则。常见的搜索树有二叉搜索树、自平衡二叉树、多叉搜索树等。AVL树、红黑树、Splay树都属于自平衡二…什么是搜索树
搜索树是一种树形数据结构用于高效地存储和检索数据。其核心特点是每个节点包含一个键Key并遵循特定的排序规则。常见的搜索树有二叉搜索树、自平衡二叉树、多叉搜索树等。AVL树、红黑树、Splay树都属于自平衡二叉树。
二叉搜索树
什么是二叉搜索树
1、是一棵二叉树
2、左子树所有节点值的大小 当前节点值的大小
3、右子树所有节点值的大小 当前节点值的大小
4、子树也满足上述条件
下图就是一棵二叉搜索树根据二叉搜索树的性质当我们中序遍历这棵树的时候发现它是按照顺序进行排序的。上面中序排序为10、20、30、40、50、60、70、80
二叉搜索树的基本操作
查找
根据二叉搜索树的性质“左边的值”都比节点的值小“右边的值”都比节点的值大。这样我们查找的时候就可以直接排除了一边子树。
代码展示
public TreeNode search(int key) {if(root null) {return null;}TreeNode cur root;while (cur ! null) {if(cur.value key) {return cur;}else if(cur.value key) {//说明key在左树cur cur.left;}else {//说明key在右树cur cur.right;}}return null;//当整棵树都没有找到key返回null
}代码分析
时间复杂度最好情况下根节点就是要找的O(1)平均情况下O(logN) — 每次比较可以排除一半的节点类似二分查找最坏情况下树是一棵单边树也看成链表O(N) ----- 需要遍历每个节点。为了解决二叉搜索树存在的问题就有了AVL树、红黑树插入
插入数据后还是要满足二叉搜索树的性质的。插入操作一般都是在叶子节点位置进行的。这是为了保证插入后树依然保持二叉搜索树的性质并且不需要对已有的其他节点结构进行调整。
代码展示
public boolean insert(int val) {TreeNode node new TreeNode(val);//当二叉树为空直接插入if(root null) {root node;return true;}TreeNode cur root;//用来找到遍历二叉树TreeNode prev null;//用来找到cur父亲节点while (cur ! null) {if(cur.value val) {return false;}else if(cur.value val) {prev cur;cur cur.left;//根据性质需要在左子树进行插入cur向左子树移动。}else {prev cur;cur cur.right;//根据性质需要在右子树进行插入cur向右子树移动。}}//此时cur为nullprev指向cur父亲节点//根据prev的值决定将新节点插入左子树还是右子树if(prev.value val) {prev.left node;}else {prev.right node;}return true;
}代码分析
时间复杂度平均情况下O(logN)最坏情况下树是一棵单边树也看成链表O(N)。
删除
代码展示
public void remove(int val) {if(root null) {return;}TreeNode cur root;TreeNode parent null;if(cur.val val) {parent cur;cur cur.left;}else if(cur.val val) {parent cur;cur cur.right;}else {parent cur;removeNode(cur,parent);//通过上述代码找到要删除的节点再通过removeNode(cur,parent)方法删除节点}
}
//删除节点的方法
private void removeNode(TreeNode cur, TreeNode parent) {//1、cur.left null要删除的节点只有右节点if(cur.left null) {if(cur root) { //1.1、cur为root则root cur.rightroot cur.right;//要删除的为根节点根节点往后移}else {if(cur parent.right) {//1.2、cur不为rootcur为父亲节点(parent)的右结点parent.right cur.right;//让parent的右节点指向cur的右节点跳过cur}else {//1.3、cur不为rootcur为父亲节点(parent)的左结点parent.left cur.right;//让parent的左节点指向cur的右节点跳过cur}}}else if(cur.right null) {//2、cur.right nullif(cur root) { //2.1、cur为root则root cur.leftroot cur.left;//要删除的为根节点根节点往后移}else {if(cur parent.right) {//2.2、cur不为rootcur为父亲节点(parent)的右结点parent.right cur.left;//让parent的右节点指向cur的左节点跳过cur}else {//2.3、cur不为rootcur为父亲节点(parent)的左结点parent.left cur.left;//让parent的左节点指向cur的左节点跳过cur}}}else {//3、cur.left ! null cur.right ! null//这里的删除相当于替换删除。在以cur为root的树中在右树找到最左边的节点或者在左树找到最右边的节点TreeNode target cur.right;TreeNode targetParent cur;while (target.left ! null) {//在右树找到最左边的节点targettargetParent target;target target.left;}cur.val target.val;//target在targetParent的左右子树位置不一样删除方式不一样if(target targetParent.left) {targetParent.left target.right;}else {targetParent.right target.right;}}
}代码分析
