汕头企业网站建设价格,网站栏目划分,做网站的旅行社,网络服务公司有哪些二叉查找树
二叉树的一个重要应用就是他在查询中的使用#xff0c;假设书中每个节点存储一项数据。在我们的案例中#xff0c;任意复杂的项在java中都容易处理#xff0c;但为了简单还是假设都是整数。还假设他们都是不重复的整数#xff0c;使二叉树称为二叉查找树的性质…二叉查找树
二叉树的一个重要应用就是他在查询中的使用假设书中每个节点存储一项数据。在我们的案例中任意复杂的项在java中都容易处理但为了简单还是假设都是整数。还假设他们都是不重复的整数使二叉树称为二叉查找树的性质是 对于树中每个节点X左子树中所有项小于X中的项而右子树中的所有元素都大于X中的项目 依据以上规则意味着改树中所有元素都可以用某种一致的方式排序。 如上图中图一中的树是二叉查找树但是图二中的树不是图二中树在其项是3 的节点的右子树 上 有一个节点项是1 1 3右子节点中数据有小于该节点数据的项目违反的二叉树的两个规则之一。
二叉查找树的实现
二叉查找树要求所有项都能够排序那么必定在树中任意两个节点之间都可以进行比较所以我们必须对树节点实现Comparable接口。节点定义如下和上篇中定义有一点不同
/*** 二叉树节点对象定义** author liaojiamin* Date:Created in 15:24 2020/12/11*/
public class BinaryNode implements Comparable {private Object element;private BinaryNode left;private BinaryNode right;private int count;public BinaryNode(Object element, BinaryNode left, BinaryNode right) {this.element element;this.left left;this.right right;this.count 1;}public Object getElement() {return element;}public void setElement(Object element) {this.element element;}public BinaryNode getLeft() {return left;}public void setLeft(BinaryNode left) {this.left left;}public BinaryNode getRight() {return right;}public void setRight(BinaryNode right) {this.right right;}public int getCount() {return count;}public void setCount(int count) {this.count count;}Overridepublic int compareTo(Object o) {if(o null){return 1;}int flag this.element.toString().compareTo(o.toString());if(flag 0){return 0;}else if (flag 0){return 1;}else {return -1;}}
}
二叉查找树对应相关方法实现
/*** 二叉查找树实现** author liaojiamin* Date:Created in 15:42 2020/12/15*/
public class BinarySearchTree {public void makeEmpty(BinaryNode root) {root null;}public boolean isEmpty(BinaryNode root) {return root null;}/*** 节点元素是否存在** author: liaojiamin* date: 15:48 2020/12/15*/private boolean contains(Object x, BinaryNode t) {if (x null) {return false;}if (t null) {return false;}int flag t.compareTo(x);if (flag 0) {return contains(x, t.getLeft());} else if (flag 0) {return contains(x, t.getRight());} else {return true;}}/*** 查找最小元素节点** author: liaojiamin* date: 15:48 2020/12/15*/private BinaryNode findMin(BinaryNode t) {if (t null) {return null;}if (t.getLeft() ! null) {return findMin(t.getLeft());}return t;}/*** 查找最大元素节点** author: liaojiamin* date: 15:48 2020/12/15*/private BinaryNode findMax(BinaryNode t) {if (t null) {return null;}if (t.getRight() ! null) {return findMax(t.getRight());}return t;}/*** 插入节点** author: liaojiamin* date: 15:48 2020/12/15*/private BinaryNode insert(Object x, BinaryNode t) {if (x null) {return t;}if (t null || t.getElement() null) {t new BinaryNode(x, null, null);return t;}int flag t.compareTo(x);if (flag 0) {t.setLeft(insert(x, t.getLeft()));} else if (flag 0) {t.setRight(insert(x, t.getRight()));} else {t.setCount(t.getCount() 1);}return t;}/*** 删除节点** author: liaojiamin* date: 15:48 2020/12/15*/private BinaryNode remove(Object x, BinaryNode t) {if (x null) {return t;}int flag t.compareTo(x);if (flag 0) {return remove(x, t.getLeft());} else if (flag 0) {return remove(x, t.getRight());} else if (t.getLeft() ! null t.getRight() ! null) {//找到对应节点将节点右子树下面最小的值替换当前值BinaryNode min findMin(t.getRight());t.setElement(min.getElement());//递归删除右子树下最小值remove(min.getElement(), t.getRight());} else {//找到对应节点但是当前节点只有一个子节点// 递归思想只考虑最简单情况当只有当前节点与其左子节点删除当前节点返回当节点左子节点右节点同理t t.getLeft() ! null ? t.getLeft() : t.getRight();}return t;}/*** 按顺序打印节点信息左中右** author: liaojiamin* date: 15:48 2020/12/15*/public void printTree(BinaryNode t) {if (t null || t.getElement() null) {return;}printTree(t.getLeft());for (int i 0; i t.getCount(); i) {System.out.print(t.getElement() );}printTree(t.getRight());}public static void main(String[] args) {BinaryNode node new BinaryNode(null, null, null);BinarySearchTree searchTree new BinarySearchTree();Random random new Random();for (int i 0; i 20; i) {node searchTree.insert(random.nextInt(1000), node);}System.out.println(searchTree.findMax(node).getElement());System.out.println(searchTree.findMin(node).getElement());searchTree.printTree(node);if(!searchTree.contains(13, node)){node searchTree.insert(13, node);}System.out.println(searchTree.contains(13, node));node searchTree.remove(13, node);System.out.println(searchTree.contains(13, node));}
}方法解析
containes方法
如果在树T中包含有项目X的节点你们这个需要返回True否则放回false。我们用两个递归调用来实现这个方法其实也可以用while循环来替代递归调用。但是这里用递归也是合理的因为算法表达式的简单性是以降低速度为代价的而这里所使用的栈空间的量也不过是O(logN)而已
findMinfindMax方法
同样递归依据二叉查找树的规则左子树永远小于本节点所以一直向左节点递归 可以得到最小值同样一直向右节点递归可以得到最大值
insert方法
插入操作概念是简单的。为了将X插入到树T中可以用contains方法那样沿着树查找。如果找到X则更新数量。否则将X插入到变量的路径上的最后一个点上。如下图显示为了插入4 我们遍历改树就好像在运行contains。在具有关键字的1节点处我们需要向右边行进但是右边不存在子树因此4不在这棵树上从而这个位置就是我们要插入的位置将4节点的引用交给 1 节点的right重复插入可以在节点距离中保留一个附加字段频率来处理就想我们定义的count remove方法 在集合相关API中医院最困难的是remove删除操作。因为我们发现要删除的对应节点需要考虑多种情况 如果节点是叶子节点那么可以立刻删除如果节点有一个儿子节点则该节点卡伊在其父节点调整自己的链从而绕过改节点后逻辑上被删除最复杂情况处理具有两个儿子节点一般的删除策略是用其右子树的最小数据代替该节点的数据并递归的删除那个最小的数据相当于将右子树最小数据和需要删除数据做替换因为右子树的最小节点不可能有左节点所以第二次remove要容易。下面分别图示一个子节点和两个子节点的情况 一个节点情况 两个子节点情况删除5 节点将右子树中最小节点6 和 5 替换再删除 右子树最小节点6
平均时间复杂度分析
二叉树我们期望的平均时间复杂度是O(logN)时间但是一颗二叉查找树在不断的insert和remove的过程中由于上面我们所采用的的删除策略有助于使得左子树的深度比右子树更深因为我们总是用右子树中最小的节点去替换需要删除的节点。这种方案的准确性是已经在业界证明可行就避免不了最终不平衡的可能。我们在删除过程中可以通过随机选取右子树的最小元素 和 左子树的最大元素来代替删除元素的策略来消除这种不平衡问题但是这种做法还没有人能证明可行性。好像不能完全解决平衡问题出发我们增加一个平衡balance的附加条件任何节点深度不得过深那就是AVL树。
上一篇数据结构与算法–重建二叉树 下一篇数据结构与算法–AVL树原理及实现
