二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。是数据结构中的一类。在一般情况下,查询效率比链表结构要高。
二叉排序树定义,一棵空树,或者是具有下列性质的二叉树:
- 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
- 若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
- 左、右子树也分别为二叉排序树;
- 没有键值相等的结点(可以使用链表)。
二叉树是每个节点最多有两个子树的树结构。它有五种基本形态:
二叉查找树结构图
先取根节点进行比较,如果该值小于存储值,则转向左子树;如果该值大于存储的值,则转向右子树。直到下一个节点为空时,那么就将新值插入, 如果发现新值和节点有重复情况,那么可以转换为链表.
普通插入方式:
节点有重复情况:
遍历先取根节点,如果根节点就等于我们要查找的数据,那就返回。如果要查找的数据比根节点要小,那么就在左子树中递归查找;如果要查找的数据比根节点的值大,那就在右子树中递归查找。
遍历树是根据一种特定的顺序访问树的每一个节点。比较常用的有前序遍历,中序遍历和后序遍历。而二叉搜索树最常用的是中序遍历(有序)。
①、中序遍历:左子树——》根节点——》右子树
先遍历左子树、然后访问根节点,最后遍历右子树;并且在遍历左右子树的时候。仍然是先遍历左子树,然后访问根节点,最后遍历右子树。
②、前序遍历:根节点——》左子树——》右子树
先访问根节点,再遍历左子树,最后遍历右子树;并且在遍历左右子树时,仍需先访问根节点,然后遍历左子树,最后遍历右子树。
③、后序遍历:左子树——》右子树——》根节点
先遍历左子树,然后遍历右子树,最后访问根节点;同样,在遍历左右子树的时候同样要先遍历左子树,然后遍历右子树,最后访问根节点。
以上遍历方式称为深度优先遍历,而我们其实还有种遍历.叫做广度优先遍历方式,其原理就是使用队列的机制.
广度优先遍历原理就是一次遍历一层节点,从左到右
- 先将根节点放入队列
- 然后循环每次d出队列中首个节点,添加到数组中
- 并且将当前节点的左右两个节点放入队列尾部中
相比查找和插入 *** 作,删除 *** 作要繁琐的多的多。下面分三种情况进行讨论,当然最一开始的是先找到要删除的节点:
- 如果要删除的节点没有子节点,我们只需要将父节点指向要删除节点的指针置为 null。
- 如果要删除的节点只有一个子节点(左或者右),我们就可以将它的子节点更新为父节点。
- 如果要删除的节点有两个子节点。那么需要找到这个节点的右子树中的最小左节点,把它替换到要删除的节点位置上。此时,还需要删掉最小节点在原来的位置置为 null,如果最小左节点还有右子节点那么需要将右子节点替换最小左节点
- 以上删除时候都要考虑根节点被删除情况
最复杂的删除情况(下图是两种删除情况,根节点和其他节点):
最大节点:
寻找方式就是,向右一直找直到最后一个节点就是最大的元素
最小节点:
寻找方式就是,向左一直找直到最后一个节点就是最小的元素
针对同一组数据,可以构造出不同形态的二叉查找树。
比如: 图中就根据同一组数据构造出了不同形态的二叉查找树。显然,查找、插入、删除的时间复杂度跟二叉树数据的形态有关系。 具体地说,时间复杂度跟树高度有关系。
比如: 在最左边的那棵二叉查找树中查找数据时,相当于在链表中查找数据,时间复杂度为 O(n);
比如: 在最右边的那棵二叉查找树查找时(完全二叉树的情况),时间复杂度是最小的,为 O(logn)。
★对于二叉查找树的时间复杂度为 O(logn) 理解方式,那就是二叉查找树查找的思想和二分查找的思想是类似的,都是每次查找之后取一半。因此,这两者的时间复杂度都是 O(logn)。
虽然二叉查找树的时间复杂度可以达到 O(logn),但是一旦出现不平衡的情况就会退出的特别严重,可能退化为 O(n)。显然,不平衡的二叉查找树是我们不希望遇到的,我们希望在任何时候,都能保持二叉查找树的平衡。因此有了平衡二叉查找树,平衡二叉查找树的高度接近 logn。所以查找、删除、插入 *** 作的时间复杂度也比较稳定,都是 O(logn)。
在平衡二叉查找树中,比较苛刻的有 AVL 树,不那么苛刻的有红黑树,而红黑树在生活中被用的更多(其他文章会讲这些内容的)。
注意: 以下部分工具类没有提供,但是看代码注解就知道啥意思了,核心代码都提供了,学数据结构,不是抄代码,因为数据结构会随着场景而改造的,不可能一套就能在很多地方通用的,而一般通用的都不会太好速度也不会太快的,有句叫物以稀为贵
接口package com.tree.binarytree; import java.util.List; public interface Tree节点{ //查找指定节点 public T find(T key); //查询全部 ,各种遍历方式 public List findAll(int type); //广度查询 List breadthFindAll(); //插入新节点 public boolean insert(T data); //查找最大值 public T findMax(); //查找最小值 public T findMin(); //删除节点 public boolean delete(T key); //修改节点 public boolean update(T key); //Other Method...... }
package com.tree.binarytree; import java.lang.reflect.Field; public class Node接口实现类{ private T data; //节点数据 private linked linked; //链表 private Node leftChild; //左子节点的引用 private Node rightChild; //右子节点的引用 public Node(T data) { this.data = data; } public Node() { } public linked getlinked() { return linked; } public void setlinked(linked linked) { this.linked = linked; } public T getData() { return data; } public void setData(T data) { this.data = data; } public Node getLeftChild() { return leftChild; } public void setLeftChild(Node leftChild) { this.leftChild = leftChild; } public Node getRightChild() { return rightChild; } public void setRightChild(Node rightChild) { this.rightChild = rightChild; } //通过反射拿到对象内的id值 ,(不允许字符串类型 ,只能是数值类型,或者对象类型里有id字段) public long getClassId() { if (this.getData() instanceof Number) { Number data = (Number) (this.getData()); return data.longValue(); } long l = 0L; try { Class> aClass = this.getData().getClass(); Field field = aClass.getDeclaredField("id"); field.setAccessible(true); l = (long) field.get(this.getData()); } catch (NoSuchFieldException | IllegalAccessException e) { e.printStackTrace(); } return l; } //当数据发生重复时候转换为链表 protected class linked { private T data; //当前 private linked linked; //下一个 public linked(T data, linked linked) { this.data = data; this.linked = linked; } public linked(T data) { this.data = data; } public T getData() { return data; } public void setData(T data) { this.data = data; } public linked getlinked() { return linked; } public void setlinked(linked linked) { this.linked = linked; } } public void delete(Node node) { this.setData(null); this.setlinked(null); this.setRightChild(null); this.setLeftChild(null); node=null; } @Override public String toString() { return "Node{" + "data=" + data + '}'; } }
package com.tree.binarytree; import com.objcopy.utils.ObjectCopyUtil; import java.util.*; public class BinaryTreeimplements Tree { //根节点 private Node root; public BinaryTree(List list) { for (T t : list) { this.insert(t); } } public BinaryTree() { } @Override public T find(T key) { Node node1 = new Node<>(key); return find(root,node1); } public T find( Node node, Node node1) { //0. 当前节点等于查找的值 if (node.getClassId()==node1.getClassId()) { return node.getData(); } //1 .如果查找值的小于当前节点那么就往左找 if (node.getClassId()>node1.getClassId()) { if (node.getLeftChild()!=null) { return find(node.getLeftChild(),node1); } } //2. 如果查找的值大于当前节点那么就往右找 if (node.getClassId() findAll(int type) { //1. 查找全部节点,遍历全部左树,和右树 ,以及链表(需要递归) List nodes = new ArrayList<>(); findAll(nodes, root,type); return nodes; } // 用递归的方法 private void findAll(List nodes, Node node,int type) { if (type==4) { //中序遍历(大到小) if (node.getRightChild() != null) { findAll(nodes, node.getRightChild(),type); } findAllAndlinked(nodes,node); if (node.getLeftChild() != null) { findAll(nodes, node.getLeftChild(),type); } return; } //保存当前节点值 if (type==1) { //前序遍历 findAllAndlinked(nodes,node); } //如果当前节点的子左节点不为空那么就往下递归 if (node.getLeftChild() != null) { findAll(nodes, node.getLeftChild(),type); } if (type==2) { //中序遍历(小到大) findAllAndlinked(nodes,node); } //如果当前节点的子右节点不为空那么就往下递归 if (node.getRightChild() != null) { findAll(nodes, node.getRightChild(),type); } if (type==3) {//后序遍历 findAllAndlinked(nodes,node); } } //广度优先遍历 @Override public ArrayList breadthFindAll() { ArrayList lists=new ArrayList (); if(root==null) return lists; Queue > queue=new linkedList >(); queue.offer(root); while(!queue.isEmpty()){ Node tree=queue.poll(); if (tree.getLeftChild() != null) { queue.offer(tree.getLeftChild()); } if (tree.getRightChild() != null) { queue.offer(tree.getRightChild()); } this.findAllAndlinked(lists,tree); } return lists; } private void findAllAndlinked(List nodes,Node node) { //如果节点被删除那么跳过 if (node.getData()==null) { return; } //保存当前节点值 nodes.add(node.getData()); //拿到链表的子链表 Node .linked linked = node.getlinked(); if (linked!=null) { //因为当前链表值就是当前节点的值,所以不需要添加 linked=linked.getlinked(); } //如果发现有链表那么,开启遍历链表 while (linked != null) { //将子链表的值添加 nodes.add(linked.getData()); //获取子链表是否为空 Node .linked linked1 = linked.getlinked(); if (linked1 == null) { break; } //将链表引用保存 linked = linked1; } } @Override public boolean insert(T data) { //1.先判断是否是空树,如果是那么当前插入的值作为树根 if (root == null) { root = new Node<>(data); return true; } // 将值放入node节点中 Node node = new Node<>(data); //2.拿当前节点和值进行比较(小的找左,大的找右),直到找到最后节点为null结束 ,然后插入 //记录当前查找的节点,默认都是从根节点开始找 Node current = root; while (true) { //1.1左树(比父节点小) if (current.getClassId() > node.getClassId()) { //获取左节点的值 Node leftChild = current.getLeftChild(); //如果为空那么就找到最深处了,那么就可以添加值到左节点 if (leftChild == null) { current.setLeftChild(node); return true; } else { current = leftChild; } } //1.2右树(比父节点大) if (current.getClassId() < node.getClassId()) { //获取右节点的值 Node rightChild = current.getRightChild(); //如果为空那么就找到最深处了,那么就可以添加值到右节点 if (rightChild == null) { current.setRightChild(node); return true; } else { current = rightChild; } } //1.3 节点相同 (转换链表) if (current.getClassId() == node.getClassId()) { if (current.getlinked() == null) { //将链表初始化,把当前节点的值和要添加的值都放入链表中 Node .linked linked1 = new Node ().new linked(node.getData()); Node .linked linked2 = new Node ().new linked(current.getData(), linked1); current.setlinked(linked2); return true; } else { //获取当节点的链表 Node .linked linked = current.getlinked(); while (true) { //拿到连表的子链 Node .linked linked1 = linked.getlinked(); //判断子链是否为空,如果为空那么将当前重复的值挂载到这里 if (linked1 == null) { Node .linked linked2 = new Node ().new linked(node.getData()); linked.setlinked(linked2); return true; } else { //如果不为空,继续往链表的子链表深入 linked = linked1; } } } } } } @Override public T findMax() { if (root == null) { return null; } return findMax(root); } public T findMax(Node node) { //1.原理就是查询所有节点的左子节点,最小的左子节点就是最小值 if (node.getRightChild()==null) { return node.getData(); } return findMin(node.getRightChild()); } @Override public T findMin() { if (root == null) { return null; } return findMin(root); } public T findMin(Node node) { //1.原理就是查询所有节点的左子节点,最小的左子节点就是最小值 if (node.getLeftChild()==null) { return node.getData(); } return findMin(node.getLeftChild()); } @Override public boolean delete(T key) { //0.先查询到这个节点,和这个节点的父节点 [0]父节点 ,[1]当前节点 Map map = this.deleteFind(key); //没有这个要删除的节点 if (map==null) { return false; } Node parent =(Node ) map.get("parent"); Node current =(Node ) map.get("current"); String direction =(String) map.get("direction"); //1.删除的元素没有子节点(左和右),那么直接删除当前节点 if (current.getLeftChild()==null&¤t.getRightChild()==null) { //将对象引用设置为空,加快垃圾收集器去回收这个空对象 current.delete(current);//清空数据 return true; } //2.1删除的元素有左子节点,就将这个左子节点代替当前节点 if (current.getLeftChild()!=null&¤t.getRightChild()==null) { //如果当前节点是在父节点的左边,那么就将当前节点的左子节点,覆盖当前节点的父节点的左子节点 if(direction.equals("centre")) { root = current.getLeftChild(); }else if (direction.equals("left")) { parent.setLeftChild(current.getLeftChild()); } else { parent.setRightChild(current.getLeftChild()); } return true; } //2.2删除的元素有右子节点,就将这个右子节点代替当前节点 if (current.getLeftChild()==null&¤t.getRightChild()!=null) { //如果当前节点是在父节点的右边,那么就将当前节点的右子节点,覆盖当前节点的父节点的右子节点 if(direction.equals("centre")) { root = current.getRightChild(); }else if (direction.equals("right")) { parent.setRightChild(current.getRightChild()); } else { parent.setLeftChild(current.getRightChild()); } return true; } //3.删除的元素有(左右)子节点 ,那么需要找到被删除节点的右子节点中的最小左子节点,然后替换删除的节点(注意:需要考虑最小节点有右节点的情况) if (current.getLeftChild()!=null&¤t.getRightChild()!=null) { //3.1删除的元素右节点没有左节点的情况,将删除元素的右节点覆盖删除的节点,然后在将删除元素的左节点放入到删除元素的右节的左节点中 Node rightChild = current.getRightChild(); if (rightChild.getLeftChild() == null&&direction.equals("centre")) { rightChild.setLeftChild(root.getLeftChild()); root=rightChild; return true; } else if (rightChild.getLeftChild() == null) { rightChild.setLeftChild(current.getLeftChild()); parent.setRightChild(rightChild); return true; } //删除元素右节点的最小左节点的父节点 Node minParentChild =current; //删除元素右节点的最小左节点 Node minChild =current.getRightChild(); //3.2删除的元素右节点有左节点的情况,查询当前被删除的节点的右子节点的最小左子节点 while (minChild.getLeftChild() != null) { minParentChild=minChild; //父节点 minChild= minChild.getLeftChild(); //子节点 } //3.3删除元素的右节点的最小左节点是否还存在右节点的情况 ,如果存在那么,就将右节点放入最小左节,然后将最小左节放入被删除的节点 //移动顺序(不要弄反了不然会有问题的): 最小左节点的右节点 -> 最小左节点 -> 被删除节点 if (minChild.getRightChild()!=null) { minParentChild.setLeftChild(minChild.getRightChild()); } //3.4节点不存在右节点情况,将找到的最小左节点覆盖删除的节点,并且删除原来节点的位置 if (minChild.getRightChild()==null) { minParentChild.setLeftChild(null); } //3.5(3.3和3.4)复用代码 if (direction.equals("left")) { parent.setLeftChild(minChild); return true; } else if (direction.equals("centre")) { minChild.setLeftChild(root.getLeftChild()); minChild.setRightChild(root.getRightChild()); root=minChild; return true; } else { parent.setRightChild(minChild); return true; } } return false; } @Override public boolean update(T key) { try { T t = this.find(key); if (t==null) { return false; } //方式1: 使用对象copy(反射方式), 如果出现问题那么就换成BeanCopier或者BeanUtils ObjectCopyUtil.copy(key,t); //方式2:获取到修改的父节点,然后将需要修改的节点给覆盖了就行 return true; } catch (Exception e) { e.printStackTrace(); } return false; } private Map deleteFind(T key) { Map nodes=new HashMap<>(); Node node1 = new Node<>(key); nodes.put("parent",root); nodes.put("direction","centre"); return deleteFind(nodes,root,node1); } private Map deleteFind(Map nodes, Node node, Node node1) { //0. 当前节点等于查找的值 if (node.getClassId()==node1.getClassId()) { nodes.put("current",node); //当前节点 return nodes; } //1 .如果查找值的小于当前节点那么就往左找 if (node.getClassId()>node1.getClassId()) { nodes.put("parent",node);//记录父节点 nodes.put("direction","left");//记录当前节点属于父节点哪一个方向 if (node.getLeftChild()!=null) { return deleteFind(nodes,node.getLeftChild(),node1); } } //2. 如果查找的值大于当前节点那么就往右找 if (node.getClassId() 部分测试 package com.tree.binarytree; import com.arithmetic.utils.CodeStartAndStopTimeUtil; import com.arithmetic.utils.datasource.entity.UserData; import org.junit.Test; import java.util.ArrayList; import java.util.List; import java.util.Random; import java.util.concurrent.atomic.AtomicReference; public class TestTree { @Test public void insertTree() { Listlist22 = new ArrayList (1000001); for (int i = 0; i < 1000001; i++) { Random random = new Random(); int i1 = random.nextInt(1000001); UserData build = UserData.builder().id(i1).age(i1).name("").build(); list22.add(build); } //执行时长:7506 毫秒. AtomicReference > userDataBlockList1 = new AtomicReference<>(); CodeStartAndStopTimeUtil.creator(() -> { userDataBlockList1.set(new BinaryTree (list22)); }); //执行时长:0 毫秒. CodeStartAndStopTimeUtil.creator(() -> { UserData build = UserData.builder().id(1000000).age(1000000).name("").build(); System.out.println(userDataBlockList1.get().find(build)); }); //执行时长:30 毫秒. CodeStartAndStopTimeUtil.creator(() -> { UserData build = UserData.builder().id(1000000).age(1000000).name("").build(); userDataBlockList1.get().findAll(3); //有序集合 }); } @Test public void updateTree() { BinaryTree bt = new BinaryTree (); UserData build2 = UserData.builder().id(4).age(4).name("").build(); bt.insert(build2); UserData build5 = UserData.builder().id(5).age(5).name("").build(); bt.insert(build5); UserData buildu = UserData.builder().id(4).age(6).name("6").build(); bt.update(buildu); System.out.println(bt.find(buildu)); } @Test public void breadthFindAll() { List list22 = new ArrayList (500); for (int i = 0; i <500; i++) { Random random = new Random(); int i1 = random.nextInt(500); UserData build = UserData.builder().id(i1).age(i1).name("").build(); // UserData build = UserData.builder().id(i).age(i).name("").build(); list22.add(build); ; //有序集合 } System.out.println(list22.size()); BinaryTree userDataBinaryTree = new BinaryTree<>(list22); System.out.println(userDataBinaryTree.breadthFindAll().size()); } @Test public void deleteTree1() { //1.删除的元素没有子节点(左和右),那么直接删除当前节点 BinaryTree bt = new BinaryTree (); UserData build2 = UserData.builder().id(4).age(4).name("").build(); bt.insert(build2); //[UserData(id=4, name=, age=4)] System.out.println(bt.findAll(2)); UserData build11 = UserData.builder().id(4).age(21).name("").build(); bt.delete(build11); //[] System.out.println(bt.findAll(2)); } @Test public void deleteTree2() { //2.删除的元素有左子节点,就将这个左子节点代替当前节点 BinaryTree bt = new BinaryTree (); UserData build2 = UserData.builder().id(4).age(4).name("").build(); bt.insert(build2); UserData build4 = UserData.builder().id(3).age(3).name("").build(); bt.insert(build4); //[UserData(id=3, name=, age=3), UserData(id=4, name=, age=4)] System.out.println(bt.findAll(2)); UserData build11 = UserData.builder().id(4).age(21).name("").build(); bt.delete(build11); //[UserData(id=3, name=, age=3)] System.out.println(bt.findAll(2)); } @Test public void deleteTree3() { //2.删除的元素有左子节点,就将这个左子节点代替当前节点 BinaryTree bt = new BinaryTree (); UserData build2 = UserData.builder().id(4).age(4).name("").build(); bt.insert(build2); UserData build4 = UserData.builder().id(5).age(5).name("").build(); bt.insert(build4); //[UserData(id=4, name=, age=4), UserData(id=5, name=, age=5)] System.out.println(bt.findAll(2)); UserData build11 = UserData.builder().id(4).age(21).name("").build(); bt.delete(build11); //[UserData(id=5, name=, age=5)] System.out.println(bt.findAll(2)); } @Test public void deleteTree4() { //3.删除的元素有(左右)子节点 ,那么需要找到被删除节点的右子节点中的最小左子节点,然后替换删除的节点(注意:需要考虑最小节点有右节点的情况) //3.1删除的元素右节点没有左节点的情况,将删除元素的右节点覆盖删除的节点,然后在将删除元素的左节点放入到删除元素的右节的左节点中 BinaryTree bt = new BinaryTree (); UserData build2 = UserData.builder().id(4).age(4).name("").build(); bt.insert(build2); UserData build4 = UserData.builder().id(5).age(5).name("").build(); bt.insert(build4); UserData build41 = UserData.builder().id(6).age(6).name("").build(); bt.insert(build41); UserData build3 = UserData.builder().id(3).age(3).name("").build(); bt.insert(build3); //[UserData(id=4, name=, age=4), UserData(id=5, name=, age=5)] System.out.println(bt.findAll(2)); UserData build11 = UserData.builder().id(4).age(21).name("").build(); bt.delete(build11); //[UserData(id=5, name=, age=5)] System.out.println(bt.findAll(2)); } @Test public void deleteTree5() { //3.删除的元素有(左右)子节点 ,那么需要找到被删除节点的右子节点中的最小左子节点,然后替换删除的节点(注意:需要考虑最小节点有右节点的情况) //3.3删除元素的右节点的最小左节点是否还存在右节点的情况 ,如果存在那么,就将右节点放入最小左节,然后将最小左节放入被删除的节点 BinaryTree bt = new BinaryTree (); UserData build2 = UserData.builder().id(4).age(4).name("").build(); bt.insert(build2); UserData build3 = UserData.builder().id(3).age(3).name("").build(); bt.insert(build3); UserData build8 = UserData.builder().id(8).age(8).name("").build(); bt.insert(build8); UserData build41 = UserData.builder().id(5).age(5).name("").build(); bt.insert(build41); UserData build6 = UserData.builder().id(6).age(6).name("").build(); bt.insert(build6); UserData build11 = UserData.builder().id(10).age(10).name("").build(); bt.insert(build11); UserData build22 = UserData.builder().id(13).age(13).name("").build(); bt.insert(build22); //[UserData(id=4, name=, age=4), UserData(id=5, name=, age=5)] System.out.println(bt.findAll(2)); UserData build1111 = UserData.builder().id(4).age(21).name("").build(); bt.delete(build1111); //[UserData(id=5, name=, age=5)] System.out.println(bt.findAll(2)); } @Test public void deleteTree6() { //3.删除的元素有(左右)子节点 ,那么需要找到被删除节点的右子节点中的最小左子节点,然后替换删除的节点(注意:需要考虑最小节点有右节点的情况) //3.4节点不存在右节点情况,将找到的最小左节点覆盖删除的节点,并且删除原来节点的位置 BinaryTree bt = new BinaryTree (); UserData build2 = UserData.builder().id(4).age(4).name("").build(); bt.insert(build2); UserData build4 = UserData.builder().id(8).age(8).name("").build(); bt.insert(build4); UserData build6 = UserData.builder().id(6).age(6).name("").build(); bt.insert(build6); UserData build11 = UserData.builder().id(10).age(10).name("").build(); bt.insert(build11); UserData build22 = UserData.builder().id(13).age(13).name("").build(); bt.insert(build22); UserData build3 = UserData.builder().id(3).age(3).name("").build(); bt.insert(build3); //[UserData(id=4, name=, age=4), UserData(id=5, name=, age=5)] System.out.println(bt.findAll(2)); UserData build1111 = UserData.builder().id(4).age(21).name("").build(); bt.delete(build1111); //[UserData(id=5, name=, age=5)] System.out.println(bt.findAll(2)); } } 点赞 -收藏-关注-便于以后复习和收到最新内容 有其他问题在评论区讨论-或者私信我-收到会在第一时间回复 如有侵权,请私信联系我 感谢,配合,希望我的努力对你有帮助^_^ 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)