0 课程地址
https://coding.imooc.com/lesson/207.html#mid=14351
1 重点关注
1.1 破坏二分搜索树的四种情况
左左LL:新插入的节点导致不平衡,向上回溯找到第一个不平衡的节点在左孩子的左侧
右右RR:新插入的节点导致不平衡,向上回溯找到第一个不平衡的节点在右孩子的右侧
左右LR:新插入的节点导致不平衡,向上回溯找到第一个不平衡的节点在左孩子的右侧
右左RL:新插入的节点导致不平衡,向上回溯找到第一个不平衡的节点在右孩子的左侧
1.2 LR解析和RL解析
- LR
- RL
1.3 LR和RL的解决
- LR
左子树先左旋转,形成LL的情况,整棵树再右旋转,实现平衡
- RL
右子树先右旋转,形成RR的情况,整棵树再左旋转,实现平衡
2 课程内容
2.1 LR和RL的不平衡情况分析
见1.2
2.2 LR和RL的实现平衡的解决思路
见1.3
2.3 LR和RL的实现平衡的代码实现
见3.1
2.4 实现自平衡的代码和退化成链表的二叉树性能差异测试
见3.1
3 Coding
3.1 coding
案例:傲慢与偏见 统计单词
- 关键代码
//左左情况 if(balanceFactor>1&&getBalanceFactor(node.left)>=0){ return rightRotate(node); //右右情况 }else if(balanceFactor<-1&&getBalanceFactor(node.right)<=0){ return leftRotate(node); //左右情况 }else if(balanceFactor>1&&getBalanceFactor(node.left)<0){ //先对左子节点左旋转,然后整体右旋转 node.left = leftRotate(node.left); return rightRotate(node); //右左情况 }else if(balanceFactor<-1&&getBalanceFactor(node.right)>0){ node.right = rightRotate(node.right); return leftRotate(node); }
- 主类AVLTree:
package com.company; import java.util.ArrayList; import java.util.List; public class AVLTree<K extends Comparable<K>,V> { //1 定义Node class Node{ private K key; private V value; private Node left,right; private int height; public Node(K key, V value){ this.key = key; this.value = value; this.left = null; this.right = null; this.height = 1; } @Override public String toString() { final StringBuffer sb = new StringBuffer("Node{"); sb.append("key=").append(key); sb.append(", value=").append(value); sb.append('}'); return sb.toString(); } } //2 定义属性 private int size; private Node root; /** * getHeight * @author weidoudou * @date 2023/4/1 11:34 * @param node 请添加参数描述 * @return int **/ private int getHeight(Node node){ if(null==node){ return 0; } return node.height; } /** * getBalanceFactor * @author weidoudou * @date 2023/4/1 11:36 * @param node 请添加参数描述 * @return int **/ private int getBalanceFactor(Node node){ if(null==node){ return 0; } return getHeight(node.left) - getHeight(node.right); } /** * 无参构造函数 * @author weidoudou * @date 2023/1/1 11:09 * @return null **/ public AVLTree(){ this.size = 0; this.root = null; } public boolean isEmpty() { return size==0?true:false; } public int getSize() { return size; } //3 定义包含函数 private Node containsKey(K key,Node node){ //结束条件 if(null==node){ return null; } //循环条件 if(key.compareTo(node.key)<0){ return containsKey(key,node.left); }else if(key.compareTo(node.key)>0){ return containsKey(key, node.right); }else{//key.compareTo(node.key)=0 其实这个也是结束条件 return node; } } public boolean contains(K key) { return containsKey(key,root)==null?false:true; } public V get(K key) { Node node = containsKey(key,root); if(null!=node){ return node.value; } return null; } //3 递归,添加元素 public Node add(K key,V value,Node node){ //3.1 终止条件 //3.1.1 要插入的元素和二叉树原有节点相同,这个不用判断,因为已经调了containsKey方法判断了 if(node==null){ size++; return new Node(key,value); } //3.1.2 最终插入左孩子 if(key.compareTo(node.key)<0 ){ node.left = add(key,value,node.left); }else if(key.compareTo(node.key)>0){ node.right = add(key,value,node.right); }else{ node.value = value; } node.height = 1+Math.max(getHeight(node.left),getHeight(node.right)); int balanceFactor = getBalanceFactor(node); /*if(Math.abs(balanceFactor)>1){ System.out.println("unbalanced:"+balanceFactor); }*/ //左左情况 if(balanceFactor>1&&getBalanceFactor(node.left)>=0){ return rightRotate(node); //右右情况 }else if(balanceFactor<-1&&getBalanceFactor(node.right)<=0){ return leftRotate(node); //左右情况 }else if(balanceFactor>1&&getBalanceFactor(node.left)<0){ //先对左子节点左旋转,然后整体右旋转 node.left = leftRotate(node.left); return rightRotate(node); //右左情况 }else if(balanceFactor<-1&&getBalanceFactor(node.right)>0){ node.right = rightRotate(node.right); return leftRotate(node); } return node; } // 对节点y进行向右旋转操作,返回旋转后新的根节点x // y x // / \ / \ // x T4 向右旋转 (y) z y // / \ - - - - - - - -> / \ / \ // z T3 T1 T2 T3 T4 // / \ // T1 T2 /** * 右旋转 * 1 旋转 * 2 变更高度 * @author weidoudou * @date 2023/4/14 7:27 * @param y 请添加参数描述 * @return com.company.AVLTree<K,V>.Node **/ private Node rightRotate(Node y){ //1 右旋转 Node x = y.left; Node T3 = x.right; x.right = y; y.left = T3; //2 变更高度 y.height = Math.max(getHeight(y.left),getHeight(y.right))+1; x.height = Math.max(getHeight(x.left),getHeight(x.left))+1; return x; } // 对节点y进行向左旋转操作,返回旋转后新的根节点x // y x // / \ / \ // T1 x 向左旋转 (y) y z // / \ - - - - - - - -> / \ / \ // T2 z T1 T2 T3 T4 // / \ // T3 T4 private Node leftRotate(Node y) { Node x = y.right; Node T2 = x.left; // 向左旋转过程 x.left = y; y.right = T2; // 更新height y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1; x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1; return x; } public void add(K key, V value) { root = add(key,value,root); /*Node node = containsKey(key,root); //未找到,插值 if(node==null){ //2.1 考虑特殊情况,如果是第一次调用,root为null if(root==null){ root = new Node(key,value); size++; }else{ //2.2 添加递归方法 add(key,value,root); } }else{ node.value = value; }*/ //找到后,更新值 } public void set(K key, V value) { Node node = containsKey(key,root); if(node == null){ throw new IllegalArgumentException("要修改的值不存在"); } node.value = value; } private Node remove(Node node,K key){ //终止条件1 基本判断不到,因为已经判断了containskey /*if(node==null){ return null; }*/ //递归 if(key.compareTo(node.key)<0){ node.left = remove(node.left,key); return node; }else if(key.compareTo(node.key)>0){ node.right = remove(node.right,key); return node; }else{ //已找到要删除的元素 //1 如果只有左子节点或只有右子节点,则直接将子节点替换 if(node.left==null){ return node.right; }else if(node.right==null){ return node.left; }else{ //2 如果有左子节点和右子节点,则寻找前驱或后继 对当前节点替换掉 Node nodeMain = findMin(node.right); nodeMain.right = removMin(node.right);//这块一箭双雕,既把后继节点问题解决了,也把后继删除了 nodeMain.left = node.left; node.left = node.right = null; return node; } } } private Node findMin(Node node){ //1 终止条件 if(node.left==null){ return node; } //2 递归 return findMin(node.left); } private Node removMin(Node node){ //终止条件 if(node.left==null){ Node rightNode = node.right; node.right = null; return rightNode; } //递归 node.left = removMin(node.left); return node; } /** * 删除任意元素 若删除元素节点下只有一个节点直接接上即可,若有两个节点,则找前驱或后继,本节找前驱 * @author weidoudou * @date 2023/1/1 11:52 * @param key 请添加参数描述 * @return V **/ public V remove(K key) { Node node = containsKey(key,root); if(node == null){ throw new IllegalArgumentException("要修改的值不存在"); } size--; return remove(root, key).value; } //1 校验二分搜索树(中序遍历参考之前的中序遍历一节) public boolean judgeBST(){ List<K> list = new ArrayList<>(); inOrder(root,list); for(int i=1;i<list.size();i++){ if(list.get(i-1).compareTo(list.get(i))>0){ return false; } } return true; } private void inOrder(Node node, List<K> list){ if(node==null){ return; } inOrder(node.left,list); list.add(node.key); inOrder(node.right,list); } //2 校验平衡二叉树 public boolean judgeBalance(){ return judgeBalance(root); } private boolean judgeBalance(Node node){ if(node == null){ return true; } int balanceFactor = getBalanceFactor(node); if(Math.abs(balanceFactor)>1){ return false; } return judgeBalance(node.left)&&judgeBalance(node.right); } public static void main(String[] args) { System.out.println("Pride and Prejudice"); ArrayList<String> words = new ArrayList<>(); if(FileOperation.readFile("pride-and-prejudice.txt",words)){ System.out.println("Total words: "+words.size()); AVLTree<String,Integer> avlTree = new AVLTree<>(); for(String word:words){ if(avlTree.contains(word)){ avlTree.set(word,avlTree.get(word)+1); }else{ avlTree.add(word,1); } } System.out.println("Total different words:"+avlTree.getSize()); System.out.println("judge BST:"+avlTree.judgeBST()); System.out.println("judge Balance:"+avlTree.judgeBalance()); } } }
- 对照类BST:
package com.company; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class BST<K extends Comparable<K>,V> { //1 定义Node class Node{ private K key; private V value; private Node left,right; public Node(K key, V value){ this.key = key; this.value = value; this.left = null; this.right = null; } @Override public String toString() { final StringBuffer sb = new StringBuffer("Node{"); sb.append("key=").append(key); sb.append(", value=").append(value); sb.append('}'); return sb.toString(); } } //2 定义属性 private int size; private Node root; /** * 无参构造函数 * @author weidoudou * @date 2023/1/1 11:09 * @return null **/ public BST(){ this.size = 0; this.root = null; } public boolean isEmpty() { return size==0?true:false; } public int getSize() { return size; } //3 定义包含函数 private Node containsKey(K key,Node node){ //结束条件 if(null==node){ return null; } //循环条件 if(key.compareTo(node.key)<0){ return containsKey(key,node.left); }else if(key.compareTo(node.key)>0){ return containsKey(key, node.right); }else{//key.compareTo(node.key)=0 其实这个也是结束条件 return node; } } public boolean contains(K key) { return containsKey(key,root)==null?false:true; } public V get(K key) { Node node = containsKey(key,root); if(null!=node){ return node.value; } return null; } //3 递归,添加元素 public void add(K key,V value,Node root){ //3.1 终止条件 //3.1.1 要插入的元素和二叉树原有节点相同,这个不用判断,因为已经调了containsKey方法判断了 /*if(key.equals(root.e)){ return; }*/ //3.1.2 最终插入左孩子 if(key.compareTo(root.key)<0 && root.left==null){ root.left = new Node(key,value); size++; return; } //3.1.2 最终插入右孩子 if(key.compareTo(root.key)>0 && root.right == null){ root.right = new Node(key,value); size++; return; } //3.2 递归 //3.2.1 递归左孩子 if(key.compareTo(root.key)<0){ add(key,value,root.left); } //3.2.2 递归右孩子 if(key.compareTo(root.key)>0){ add(key,value,root.right); } } public void add(K key, V value) { Node node = containsKey(key,root); //未找到,插值 if(node==null){ //2.1 考虑特殊情况,如果是第一次调用,root为null if(root==null){ root = new Node(key,value); size++; }else{ //2.2 添加递归方法 add(key,value,root); } }else{ node.value = value; } //找到后,更新值 } public void set(K key, V value) { Node node = containsKey(key,root); if(node == null){ throw new IllegalArgumentException("要修改的值不存在"); } node.value = value; } private Node remove(Node node,K key){ //终止条件1 基本判断不到,因为已经判断了containskey /*if(node==null){ return null; }*/ //递归 if(key.compareTo(node.key)<0){ node.left = remove(node.left,key); return node; }else if(key.compareTo(node.key)>0){ node.right = remove(node.right,key); return node; }else{ //已找到要删除的元素 //1 如果只有左子节点或只有右子节点,则直接将子节点替换 if(node.left==null){ return node.right; }else if(node.right==null){ return node.left; }else{ //2 如果有左子节点和右子节点,则寻找前驱或后继 对当前节点替换掉 Node nodeMain = findMin(node.right); nodeMain.right = removMin(node.right);//这块一箭双雕,既把后继节点问题解决了,也把后继删除了 nodeMain.left = node.left; node.left = node.right = null; return node; } } } private Node findMin(Node node){ //1 终止条件 if(node.left==null){ return node; } //2 递归 return findMin(node.left); } private Node removMin(Node node){ //终止条件 if(node.left==null){ Node rightNode = node.right; node.right = null; return rightNode; } //递归 node.left = removMin(node.left); return node; } /** * 删除任意元素 若删除元素节点下只有一个节点直接接上即可,若有两个节点,则找前驱或后继,本节找前驱 * @author weidoudou * @date 2023/1/1 11:52 * @param key 请添加参数描述 * @return V **/ public V remove(K key) { Node node = containsKey(key,root); if(node == null){ throw new IllegalArgumentException("要修改的值不存在"); } size--; return remove(root, key).value; } }
- 测试类:
package com.company; import java.util.ArrayList; import java.util.Collections; import java.util.stream.Collectors; public class Main { public static void main(String[] args) { //1 先把字数全部放进list ArrayList<String> list1 = new ArrayList<>(); if(FileOperation.readFile("pride-and-prejudice.txt",list1)){ Collections.sort(list1); BST<String,Integer> bst = new BST(); //2.1 测试BST long startTime1 = System.nanoTime(); for(int i = 0;i<list1.size();i++){ if(bst.contains(list1.get(i))){ bst.set(list1.get(i),bst.get(list1.get(i))+1); }else{ bst.add(list1.get(i),1); } } for(String key: list1){ bst.contains(key); } long endTime1 = System.nanoTime(); System.out.println("BST USE TIME ="+(endTime1-startTime1)/100000000.0); //2.2 测试AVLTree long startTime2 = System.nanoTime(); AVLTree<String,Integer> avlTree = new AVLTree<>(); for(int i = 0;i<list1.size();i++){ if(avlTree.contains(list1.get(i))){ avlTree.set(list1.get(i),avlTree.get(list1.get(i))+1); }else{ avlTree.add(list1.get(i),1); } } for(String key: list1){ avlTree.contains(key); } long endTime2 = System.nanoTime(); System.out.println("AVLTREE USE TIME ="+(endTime2-startTime2)/100000000.0); } } }
- 测试结果:
BST USE TIME =103.097125 AVLTREE USE TIME =0.434623 Process finished with exit code 0
标签:node,Node,12,return,null,right,LR,key,数据结构 From: https://www.cnblogs.com/1446358788-qq/p/17322694.html