第13 章 ： 比较器
52 比较器问题引出
比较器：大小关系判断
示例：对象数组排序
Integer[] data = new Integer[]{1, 4, 5, 8, 6}; Arrays.sort(data); System.out.println(Arrays.toString(data)); // [1, 4, 5, 6, 8]
53 Comparable比较器
接口：Comparable
public interface Comparable<T> { public int compareTo(T o); }
大于返回正数
等于返回0
小于返回负数
示例：自定义类型数组排序
import java.util.Arrays; class Person implements Comparable<Person>{ private String name ; private int age ; public Person(String name, int age) { this.name = name; this.age = age; } @Override public int compareTo(Person other) { return this.age - other.age; } @Override public String toString() { return "Person{" + "name='" + name + '\'' + ", age=" + age + '}'; } } class Demo { public static void main(String[] args) { Person[] data = { new Person("小王", 23), new Person("小刘", 27), new Person("小张", 25), }; Arrays.sort(data); System.out.println(Arrays.toString(data)); // [ // Person{name='小王', age=23}, // Person{name='小张', age=25}, // Person{name='小刘', age=27} // ] } }
54 Comparator比较器
解决没有实现Comparable接口的对象比较
@FunctionalInterface public interface Comparator<T> { int compare(T o1, T o2); }
排序方法
import java.util.Arrays; public static void sort(Object[] a) public static <T> void sort(T[] a, Comparator<? super T> c)
使用示例
import java.util.Arrays; import java.util.Comparator; class Person{ private String name ; private int age ; public Person(String name, int age) { this.name = name; this.age = age; } public int getAge() { return age; } @Override public String toString() { return "Person{" + "name='" + name + '\'' + ", age=" + age + '}'; } } class PersonComparator implements Comparator<Person> { @Override public int compare(Person person1, Person person2) { return person1.getAge() - person2.getAge(); } } class Demo { public static void main(String[] args) { Person[] data = { new Person("小王", 23), new Person("小刘", 27), new Person("小张", 25), }; Arrays.sort(data, new PersonComparator()); System.out.println(Arrays.toString(data)); // [ // Person{name='小王', age=23}, // Person{name='小张', age=25}, // Person{name='小刘', age=27} // ] } }
Comparable优先使用
区别 Comparable Comparator
Comparable 定义类的时候实现父接口，定义排序规则
public int compareTo(T o)
Comparator 挽救的比较器操作，需要单独设置比较规则实现排序
int compare(T o1, T o2);
可以使用匿名类
Arrays.sort(data, new Comparator<Person>() { @Override public int compare(Person o1, Person o2) { return o1.getAge() - o2.getAge(); } });
也可以使用Lambda表达式
Comparator<Person> comparator = (Person o1, Person o2)->{ return o1.getAge() - o2.getAge(); }; Arrays.sort(data, comparator);
或者
Arrays.sort(data, (p1, p2)->{ return p1.getAge() - p2.getAge(); });
55 二叉树结构简介
链表的时间复杂度是O(n)
二叉树查找的时间复杂度是O(logn)
数据位置
父节点-中 左子树-小 右子树-大
遍历数据
1、前序遍历 根-左-右
2、中序遍历 左-根-右
3、后序遍历 左-右-根
56 二叉树基础实现
import java.util.Arrays; class Person implements Comparable<Person> { private String name; private int age; public Person(String name, int age) { this.name = name; this.age = age; } public int getAge() { return age; } @Override public String toString() { return "Person{" + "name='" + name + '\'' + ", age=" + age + '}'; } @Override public int compareTo(Person other) { return this.age - other.age; } } class BinaryTree<T extends Comparable<T>> { private class Node { private Comparable<T> data; private Node parent; private Node left; private Node right; public Node(Comparable<T> data) { this.data = data; } public void addNode(Node node) { // 数据比当前节点小，添加到左子树 if (node.data.compareTo((T) this.data) <= 0) { if (this.left == null) { this.left = node; node.parent = this; // 保存父节点 } else { this.left.addNode(node); } } // 数据比当前节点大，添加到右子树 else { if (this.right == null) { this.right = node; node.parent = this; } else { this.right.addNode(node); } } } public void toArrayNode(){ if(this.left != null){ this.left.toArrayNode(); } BinaryTree.this.dataList[BinaryTree.this.foot++] = this.data; if(this.right != null){ this.right.toArrayNode(); } } } private Node root; // 根节点 private int count ; private int foot ; private Object[] dataList; /** * 数据添加 * * @param data 要添加的数据 */ public void add(Comparable<T> data) { if (data == null) { throw new NullPointerException("数据不允许为空"); } Node node = new Node(data); if (this.root == null) { this.root = node; } else { this.root.addNode(node); } this.count ++; } public Object[] toArray(){ if(this.count == 0){ return null; } this.foot = 0; this.dataList = new Object[this.count]; this.root.toArrayNode(); return this.dataList; } } class Demo { public static void main(String[] args) { BinaryTree<Person> tree = new BinaryTree<>(); tree.add(new Person("小王", 23)); tree.add(new Person("小刘", 27)); tree.add(new Person("小张", 25)); System.out.println(Arrays.toString(tree.toArray())); /** * [ * Person{name='小王', age=23}, * Person{name='小张', age=25}, * Person{name='小刘', age=27} * ] */ } }
57 二叉树数据删除
要删除的节点情况：
1、没有子节点，直接删除
2、只有一个子节点（左节点或右节点），删除后用子节点顶替
3、有左右节点，在右子树中找最左边节点顶替
4、需要特殊考虑根节点
import java.util.Arrays; class BinaryTree<T extends Comparable<T>> { private class Node { private Comparable<T> data; private Node parent; private Node left; private Node right; public Node(Comparable<T> data) { this.data = data; } public void addNode(Node node) { // 数据比当前节点小，添加到左子树 if (node.data.compareTo((T) this.data) <= 0) { if (this.left == null) { this.left = node; node.parent = this; // 保存父节点 } else { this.left.addNode(node); } } // 数据比当前节点大，添加到右子树 else { if (this.right == null) { this.right = node; node.parent = this; } else { this.right.addNode(node); } } } public Node getMostLeftNode() { if (this.left != null) { return this.left.getMostLeftNode(); } else { return this; } } public Node getNode(Comparable<T> data) { if (this.data.compareTo((T) data) == 0) { return this; } // 查找子节点 else { // 右边节点 if (data.compareTo((T) this.data) > 0) { if (this.right != null) { return this.right.getNode(data); } else { return null; } // 左边节点 } else { if (this.left != null) { return this.left.getNode(data); } else { return null; } } } } public void toArrayNode() { if (this.left != null) { System.out.println(this.data + " left-> " + this.left.data); this.left.toArrayNode(); } BinaryTree.this.dataList[BinaryTree.this.foot++] = this.data; if (this.right != null) { System.out.println(this.data + " right-> " + this.right.data); this.right.toArrayNode(); } } } private Node root; // 根节点 private int count; private int foot; private Object[] dataList; /** * 数据添加 * * @param data 要添加的数据 */ public void add(Comparable<T> data) { if (data == null) { throw new NullPointerException("数据不允许为空"); } Node node = new Node(data); if (this.root == null) { this.root = node; } else { this.root.addNode(node); } this.count++; } public void addMany(Comparable<T>... list) { for (Comparable<T> data : list) { this.add(data); } } public void removeRoot() { // 右子树不为空 if (this.root.right != null) { Node mostLeftNode = this.root.right.getMostLeftNode(); System.out.println(mostLeftNode.data); mostLeftNode.parent.left = null; mostLeftNode.parent = null; mostLeftNode.left = root.left; mostLeftNode.right = root.right; this.root = mostLeftNode; } // 右子树为空 else if (this.root.left != null) { this.root.left.parent = null; this.root = this.root.left; } // 单独根节点 else { this.root = null; } } public void removeChild(Node node) { // 1、没有子节点 if (node.left == null && node.right == null) { if (node.parent.left == node) { node.parent.left = null; } else { node.parent.right = null; } } // 2、有一个子节点 // 2-1 只有右节点 else if (node.left == null) { if (node.parent.left == node) { node.parent.left = node.right; } else { node.parent.right = node.right; } } // 2-2只有左节点 else if (node.right == null) { if (node.parent.left == node) { node.parent.left = node.left; } else { node.parent.right = node.left; } } // 3、有两个子节点 else { Node mostLeftNode = node.right.getMostLeftNode(); mostLeftNode.parent.left = null; mostLeftNode.parent = node.parent; mostLeftNode.left = node.left; mostLeftNode.right = node.right; } node.parent = null; } public void remove(Comparable<T> data) { Node node = this.root.getNode(data); if (node == null) { return; } // 单独考虑根节点，没有父节点 if (this.root == node) { this.removeRoot(); } else { this.removeChild(node); } this.count--; } public Object[] toArray() { if (this.count == 0) { return null; } this.foot = 0; this.dataList = new Object[this.count]; this.root.toArrayNode(); return this.dataList; } } class Demo { public static void main(String[] args) { BinaryTree<Integer> tree = new BinaryTree<>(); tree.addMany(8, 7, 12); System.out.println(Arrays.toString(tree.toArray())); tree.remove(7); System.out.println(Arrays.toString(tree.toArray())); } }
58 红黑树原理简介
二叉树主要特点：
优点：数据查询的时候可以提供更好的查询性能
缺陷：二叉树结构改变的时候（增加或删除）就有可能出现不平衡的问题
平衡二叉树 别称：二叉查找树，平衡二叉B树
插入，删除，查找的最坏时间复杂度为O(logn)
在节点上追加了一个颜色表示
也可以使用boolean true或false
enum Color{ RED, BLACK; } class BinaryTree<T>{ private Node left; private Node right; private Node parent; private T data; private Color color; }
红黑树的特点
1、每个节点或者黑色或者红色
2、根节点必须是黑色
3、每个叶子节点是黑色
Java实现的红黑树将使用null代表空节点，因此遍历红黑树将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的
4、如果一个节点是红色的，则它的子节点必须是黑色
从每个根节点的路径上不会有两个连续的红色节点，当黑色节点是可以连续的
若给定黑色节点的个数N，最短路径情况是连续的N个黑色，数的高度为N-1;
最长路径的情况为节点红黑相间，树的高度为2(N-1);
5、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点数量
6、成为红黑树的主要条件，后序的插入、删除操作都是为了遵守这个规定
黑 红 红 null null null null
允许黑-黑连接，不允许红-红连接
利用红色节点和黑色节点实现均衡控制
数据插入处理
1、第一次插入，由于原树为空，所以只会违反红-黑树的规则2
要把根节点涂黑
2、如果插入节点的父节点是黑色的，那不会违背红-黑树的原则，什么也不需要做，
但是遇到如下三种情况时，就要开始变色和旋转了
（1）插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色的
（2）插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点
（3）插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的右子节点
插入节点和父节点，叔叔节点来决定修复处理
数据删除处理
修复的目的是为了保证树结构中黑色节点数量平衡
