java 二叉树记录

深碍√TFBOYSˉ_ 2024-04-17 06:27 15阅读 0赞

二叉树 演示的网站：

[https://www.cs.usfca.edu/~galles/visualization/AVLtree.html][https_www.cs.usfca.edu_galles_visualization_AVLtree.html]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhbmdfamlhbl9kb25n_size_16_color_FFFFFF_t_70][]

二叉查找： 效率高， 缺点： 必须有序

二叉搜索：没有平衡值， 容易形成链表， 导致时间复杂度 0(n)

二叉平衡: 有平衡值，

红黑树 是 二叉平衡的一直实现， 红红不相连， 有红必有黑。

时间复杂度：

o(1) ; 最快的查找， 一次查到， 不管容量多大. （index冲突则会从 o(1) 升级为 o(n)）

o (n): 最慢的查找， 容量越大， 耗时越久

o(log n): 折半查找，查一次排除一半。 以2为底数。

JDK8 hashmap没有死循环的bug, 以数组+链表+红黑树进行存储。 当链表中元素大于8时，后面的元素使用红黑树进行存储。

代码：

/** 
     * Project Name:service-tree 
     * File Name:AVLTree.java 
     * Package Name: 
     * Date:2019年8月26日 下午9:30:53 
     * Copyright (c) 2019, 航天长峰湖南分公司  All Rights Reserved. 
     * 
     */
    
    /** 
     * ClassName: AVLTree
     * Function: TODO ADD FUNCTION. 
     * date: 2019年8月26日 下午9:30:53
     * 
     * @author tangjiandong
     */
    public class Tree {
    
    	 //二叉搜索树的特征： 第一个节点作为平衡值，也就是根节点
    	int root; //根节点
    	
    	Tree left;  //左子树
    	
    	Tree  right; //右子树
    	
    	public Tree(int root)
    	{
    		this.root = root;
    	}
    	//左边比右边小
    	public void insert(Tree tree , int root)
    	{
    		 //右子树， 插入的数据大于根节点
    		  if(root > tree.root)
    		  {
    			  //如果当前的根节点右边为空，第一次添加右子树
    			   if(null == tree.right)
    			   {
    				   tree.right = new Tree(root);
    			   }else {
    				   //如果右边有值时，递归查找插入
    			   		insert(tree.right,root);
    			   }
    		  }else { //左子树， 插入的数据小于根节点
    			  //如果当前的根节点右边为空，第一次添加右子树
    			   if(null == tree.left)
    			   {
    				   tree.left = new Tree(root);
    			   }else {
    				   //如果右边有值时，递归查找插入
    			   		insert(tree.left,root);
    			   }
    		  }
    	}
    	
    	//查询
    	public void sreach(Tree tree)
    	{
    		if(null != tree)
    		{
    			sreach(tree.left);
    			System.out.println(tree.root);
    			sreach(tree.right);
    		}
    	}
    	
    	public static void main(String[] args) {
    		int [] a = new int[] {3,6,5,1,2,4};
    		Tree tree = new Tree(a[0]);
    		for (int i = 1; i < a.length; i++) 
    		{
    			tree.insert(tree, a[i]);
    		}
    		tree.sreach(tree);
    	}
    	
    }

[https_www.cs.usfca.edu_galles_visualization_AVLtree.html]: https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhbmdfamlhbl9kb25n_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/0746501743e14f2ebfd5412971888c23.png