AVL平衡二叉树(java版本)

复习AVL，平衡二叉树。 带个传送门

List item添加链接描述

首先什么是平衡二叉树？ 平衡二叉树，又称AVL树，它是一种特殊的二叉排序树。AVL树或者是一棵空树，或者是具有以下性质的二叉树： （1）左子树和右子树都是平衡二叉树； （2）左子树和右子树的深度（高度）之差的绝对值不超过1。

首先怎么实现的平衡二叉树的关键就在哪呢？ 答案在平衡二叉树的节点定义： 由于每个节点都有深度的定义。于是能引申出左子树高度和右子树高度只差。

private class Node{ public K key; public V value; public Node left,right; public int height; public Node(K key,V value){ this.key = key; this.value = value; left = null; right =null; height = 1; //每个初始节点深度都定义为1 } }

往往 往树中插入节点时才会导致不平衡，所以必须检索插入节点的父节点和祖先节点的各节点数目，判断是否是平衡，不平衡再进行调整。 而又有以下几种不平衡需要调整：

LL 由于不平衡节点的左子树左子节点导致不平衡RR 由于不平衡节点的右子树右子节点导致不平衡LR 由于不平衡节点的左子树右子节点导致不平衡RL 由于不平衡节点的右子树左子节点导致不平衡 那么他们的解决办法是什么呢？ LL,RR为一组，LR,RL为另外一组，方便记忆的话，就是LL左左，解决办法是右旋，RR右右，解决办法是左旋，而LR，RL，则就是根据符号的先后处理顺序，LR解决办法先左旋，再右旋，而RL先右旋，再左旋。

其次就是对于在每次插入过程中，插入后，必须更新当前节点的信息深度，同时计算平衡性，判断是否平衡。 不平衡则进行调整。左旋和右旋

// LL // y x // / \ / \ // x T4 右旋 z y // / \ ---------------------> / \ / \ // z T3 T1 T2 T3 T4 // / \ // T1 T2 private Node rightRotate(Node y){ Node x = y.left; Node T3 = x.right; x.right = y; y.left = T3; y.height = 1+ Math.max(getHeight(y.left),getBalance(y.right)); x.height = 1+ Math.max(getHeight(x.left),getHeight(x.right)); return x; } // RR // y x // / \ / \ // T1 X 左旋 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; y.height = 1+ Math.max(getHeight(y.left),getHeight(y.right)); x.height = 1+ Math.max(getHeight(x.left),getHeight(x.right)); return x; }

其次就是一些辅助函数，特别重要

// 得到当前节点的深度 private int getHeight(Node x) { if(x == null) return 0; return x.height; } //判断是否是二分搜索树 public boolean isBST(){ List<K> list = new ArrayList<>(); InOrderBST(root,list); for(int i = 1;i<list.size();i++) if(list.get(i-1).compareTo(list.get(i))>0) return false; return true; } // 中序遍历,添加进list private void InOrderBST(Node node,List<K> list){ if(node == null) return; InOrderBST(node.left,list); list.add(node.key); InOrderBST(node.right,list); } // 判断一棵二叉树是不是一棵平衡二叉树 public boolean isBalanced() { return isBalanced(root); } private boolean isBalanced(Node root){ if(root == null) return true; int balance = getBalance(root); if(Math.abs(balance)>1) return false; // 先根 再左右 return isBalanced(root.left)&&isBalanced(root.right); } // 返回node 为根节点的二分搜索树中,Key 所在的节点 private Node getNode(Node node,K key){ if(node == null) return null; if(key.equals(node.key)) return node; else if(key.compareTo(node.key)<0) return getNode(node.left,key); else return getNode(node.right,key); }

带个liuyubobo老师的代码

package com.hnist.lzn.tree; import java.util.ArrayList; import java.util.List; public class AVLTree<K extends Comparable<K>,V> { private class Node{ public K key; public V value; public Node left,right; public int height; public Node(K key,V value){ this.key = key; this.value = value; left = null; right =null; height = 1; } } private Node root; private int size; public AVLTree(){ root = null; size = 0; } private int getHeight(Node x) { if(x == null) return 0; return x.height; } private int getBalance(Node node){ if(node == null) return 0; return getHeight(node.left)-getHeight(node.right); } //判断是否是二分搜索树 public boolean isBST(){ List<K> list = new ArrayList<>(); InOrderBST(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 InOrderBST(Node node,List<K> list){ if(node == null) return; InOrderBST(node.left,list); list.add(node.key); InOrderBST(node.right,list); } // 判断一棵二叉是不是一棵平衡二叉树 public boolean isBalanced() { return isBalanced(root); } private boolean isBalanced(Node root){ if(root == null) return true; int balance = getBalance(root); if(Math.abs(balance)>1) return false; // 先根 再左右 return isBalanced(root.left)&&isBalanced(root.right); } // LL // y x // / \ / \ // x T4 右旋 z y // / \ ---------------------> / \ / \ // z T3 T1 T2 T3 T4 // / \ // T1 T2 private Node rightRotate(Node y){ Node x = y.left; Node T3 = x.right; x.right = y; y.left = T3; y.height = 1+ Math.max(getHeight(y.left),getBalance(y.right)); x.height = 1+ Math.max(getHeight(x.left),getHeight(x.right)); return x; } // RR // y x // / \ / \ // T1 X 左旋 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; y.height = 1+ Math.max(getHeight(y.left),getHeight(y.right)); x.height = 1+ Math.max(getHeight(x.left),getHeight(x.right)); return x; } // 添加节点 private void add(K key,V value){ root = add(root,key,value); } private Node add(Node node,K key,V value){ if(node == null) return new Node(key,value); if(key.compareTo(node.key)<0) { node.left = add(node.left,key,value); }else if(key.compareTo(key)>0){ node.right = add(node.right,key,value); }else{ node.value = value; } // 更新节点 得加1 node.height = 1+getHeight(node.left)+getHeight(node.right); //判断平衡吗 int balance = getBalance(node); if(Math.abs(balance)>1) System.out.println("no balcne"+balance); // 平衡维护 LL 为啥node.left >=0 为左 node.right <=0为右？？？ if(balance>1 && getBalance(node.left) >= 0) return rightRotate(node); // RR if(balance<-1 && getBalance(node.left) <=0) return leftRotate(node); // LR if(balance>1 && getBalance(node.left) < 0) { node.left = leftRotate(node.left); return rightRotate(node); } // RL if(balance <-1 && getBalance(node.right) > 0) { node.right = rightRotate(node.right); return leftRotate(node); } return node; } // 返回node 为根的二分搜索的最小值的所在的节点 private Node minimum(Node node){ if(node.left == null) return node; return minimum(node.left); } // 返回node 为根节点的二分搜索树中,Key 所在的节点 private Node getNode(Node node,K key){ if(node == null) return null; if(key.equals(node.key)) return node; else if(key.compareTo(node.key)<0) return getNode(node.left,key); else return getNode(node.right,key); } // 删除key 的节点 public V remove(K key){ Node node= getNode(root,key); if(node != null) { root = remove(root,key); return node.value; } return null; } public int getSize(){ return size; } public V get(K key){ Node node = getNode(root, key); return node == null ? null : node.value; } public boolean contains(K key){ return getNode(root, key) != null; } public void set(K key, V newValue){ Node node = getNode(root, key); if(node == null) throw new IllegalArgumentException(key + " doesn't exist!"); node.value = newValue; } public Node remove(Node node,K key){ if(node == null) return null; Node retNode; if(key.compareTo(node.key)<0){ node.left = remove(node.left,key); retNode = node; }else if(key.compareTo(node.key)>0){ node.right = remove(node.right,key); retNode = node; }else{ if(node.left == null){ Node rightNode = node.right; node.right = null; size--; retNode = rightNode; } else if(node.right == null) { Node leftNode = node.left; node.left = null; size--; retNode = leftNode; } else{ Node successor = minimum(node.right); successor.right = remove(node.right,successor.key); successor.left = node.left; node.left = node.right = null; retNode = successor; } } if(retNode == null) return null; // 更新height retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right)); // 计算平衡因子 int balanceFactor = getBalance(retNode); // 平衡维护 // LL if (balanceFactor > 1 && getBalance(retNode.left) >= 0) return rightRotate(retNode); // RR if (balanceFactor < -1 && getBalance(retNode.right) <= 0) return leftRotate(retNode); // LR if (balanceFactor > 1 && getBalance(retNode.left) < 0) { retNode.left = leftRotate(retNode.left); return rightRotate(retNode); } // RL if (balanceFactor < -1 && getBalance(retNode.right) > 0) { retNode.right = rightRotate(retNode.right); return leftRotate(retNode); } return retNode; } public static void main(String[] args){ System.out.println("Pride and Prejudice"); ArrayList<String> words = new ArrayList<>(); if(FileOperation.readFile("D:\\Downloads\\pride-and-prejudice.txt", words)) { System.out.println("Total words: " + words.size()); AVLTree<String, Integer> map = new AVLTree<>(); for (String word : words) { if (map.contains(word)) map.set(word, map.get(word) + 1); else map.add(word, 1); } System.out.println("Total different words: " + map.getSize()); System.out.println("Frequency of PRIDE: " + map.get("pride")); System.out.println("Frequency of PREJUDICE: " + map.get("prejudice")); System.out.println("is BST : " + map.isBST()); System.out.println("is Balanced : " + map.isBalanced()); for(String word: words){ map.remove(word); if(!map.isBST() || !map.isBalanced()) throw new RuntimeException(); } } System.out.println(); } }