Java知識【紅黑樹】

目錄

​​1，紅黑樹​​

​​1.1：概述【了解】​​

​​1.2：成績排序案例【應用】​​

1，紅黑樹

1.1：概述【了解】

• 紅黑樹的特點

• 平衡二叉B樹
• 每一個節點可以是紅或者黑
• 紅黑樹不是高度平衡的,它的平衡是通過"自己的紅黑規則"進行實作的

• 紅黑樹的紅黑規則有哪些

1. 每一個節點或是紅色的,或者是黑色的
2. 根節點必須是黑色
3. 如果一個節點沒有子節點或者父節點,則該節點相應的指針屬性值為Nil,這些Nil視為葉節點,每個葉節點(Nil)是黑色的
4. 如果某一個節點是紅色,那麼它的子節點必須是黑色(不能出現兩個紅色節點相連 的情況)
5. 對每一個節點,從該節點到其所有後代葉節點的簡單路徑上,均包含相同數目的黑色節點

紅黑樹添加節點的預設顔色

• 添加節點時,預設為紅色,效率高

• 紅黑樹添加節點後如何保持紅黑規則

• 根節點位置

• 直接變為黑色

• 非根節點位置

• 父節點為黑色

• 不需要任何操作,預設紅色即可

• 父節點為紅色

• 叔叔節點為紅色

1. 将"父節點"設為黑色,将"叔叔節點"設為黑色
2. 将"祖父節點"設為紅色
3. 如果"祖父節點"為根節點,則将根節點再次變成黑色

• 叔叔節點為黑色

1. 将"父節點"設為黑色
2. 将"祖父節點"設為紅色
3. 以"祖父節點"為支點進行旋轉

1.2：成績排序案例【應用】

• 案例需求

• 用TreeSet集合存儲多個學生資訊(姓名,國文成績,數學成績,英語成績),并周遊該集合
• 要求: 按照總分從高到低出現

• 代碼實作

  學生類

public class Student implements Comparable<Student> {
    private String name;
    private int chinese;
    private int math;
    private int english;

    public Student() {
    }

    public Student(String name, int chinese, int math, int english) {
        this.name = name;
        this.chinese = chinese;
        this.math = math;
        this.english = english;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getChinese() {
        return chinese;
    }

    public void setChinese(int chinese) {
        this.chinese = chinese;
    }

    public int getMath() {
        return math;
    }

    public void setMath(int math) {
        this.math = math;
    }

    public int getEnglish() {
        return english;
    }

    public void setEnglish(int english) {
        this.english = english;
    }

    public int getSum() {
        return this.chinese + this.math + this.english;
    }

    @Override
    public int compareTo(Student o) {
        // 主要條件: 按照總分進行排序
        int result = o.getSum() - this.getSum();
        // 次要條件: 如果總分一樣,就按照國文成績排序
        result = result == 0 ? o.getChinese() - this.getChinese() : result;
        // 如果國文成績也一樣,就按照數學成績排序
        result = result == 0 ? o.getMath() - this.getMath() : result;
        // 如果總分一樣,各科成績也都一樣,就按照姓名排序
        result = result == 0 ? o.getName().compareTo(this.getName()) : result;
        return result;
    }
}      

public class TreeSetDemo {
    public static void main(String[] args) {
        //建立TreeSet集合對象，通過比較器排序進行排序
        TreeSet<Student> ts = new TreeSet<Student>();
        //建立學生對象
        Student s1 = new Student("jack", 98, 100, 95);
        Student s2 = new Student("rose", 95, 95, 95);
        Student s3 = new Student("sam", 100, 93, 98);
        //把學生對象添加到集合
        ts.add(s1);
        ts.add(s2);
        ts.add(s3);

        //周遊集合
        for (Student s : ts) {
            System.out.println(s.getName() + "," + s.getChinese() + "," + s.getMath() + "," + s.getEnglish() + "," + s.getSum());
        }
    }
}