JAVA进阶-set,Comparable排序,数据结构-树

day07-set,Comparable排序,数据结构-树

泛型

Set

• 概述和特点
  • 
• TreeSet集合概述和特点
  • 

Comparable排序

• 自然排序Comparable的使用

  • 使用空参构造创建TreeSet集合
  • 自定义Student类实现Comparable接口
  • 重写里面的comparaTo方法
  • 

• 自然排序简单原理图

  • 

• 比较器排序Comparator的使用

  • 
  • 

• 两种比较方式小结

  • 

  • 参数	Comparable	Commparator
    排序逻辑	排序逻辑必须在待排序对象的类中，故称之为自然排序	排序逻辑在另一个实现
    实现	实现Comparable接口	实现Comparator接口
    排序方法	int compareTo(Object o1)	int compare(Object o1,Object o2)
    触发排序	Collections.sort(List)	Collections.sort(List,Comparator)
    接口所在包	java.lang.Comparable	java.util.Comparator

数据结构-树

• 

• 二叉树

  • 
  • 

• 二叉查找树

  • 先序排序出来的结果是有序的

  • 

  • 二叉查找树添加结点

    • 小的存左边，大的存右边，一样的不存

  • 平衡二叉树

    • 二叉树左右两个子树的高度差不超过1
    • 任意结点的左右两个子树都是一颗平衡二叉树

  • 平衡二叉树-旋转

    • 左旋

      • 就是将根节点的右侧往左拉，原先的右子节点变成新的父节点，并把多余的左子节点让出来，给已经降级的根节点当当右子节点。

        • 
        • 

    • 右旋

      • 将根节点的左侧往右侧拉，左子节点变成了新的父节点，并把多余的右子节点出让，给已经降级根节点当左子节点。

      • 

      • 

    • 触发时机：当添加一个节点后，该树不再是一颗平衡二叉树

  • 平衡二叉树-左边

    • 左左：当根节点左子树有节点插入，导致二叉树不平衡。左子树上的左子树上添加结点
      • 
      • 
    • 左右：当根节点左子树的右子树有节点插入，导致二叉树不平衡。
      • 旋转两次，先左旋然后右旋
      • 
      • 
      • 

  • 平衡二叉树-右边

    • 右右：当根节点右子树的右子树有节点插入，导致二叉树不平衡
    • 右左：当根节点右子树的左子树有节点插入，导致二叉树不平衡

• 红黑树

  • 
  • 红黑规则
    • 
  • 添加节点
    • 
    • 20到左边有两个黑色，到右边只有一个黑色
    • 
    • 添加三个节点只要调整两次，所以添加节点时默认为红色，效率更高
  • 如何保证红黑规则
    • 
    • 
    • 小结
      • 
      • 添加节点-非根节点位置-父节点为红色-叔叔节点为黑色
        • 
  • 红黑树小结
    • 
    •