老师，为什么我测试的BST和AVL树性能差异不大啊？
来源：12-8 基于AVL树的集合和映射
小蜗牛有大理想
2023-04-20
测试结果：
total words is 125901
time1===========14.8127835
total words is 125901
time2===========0.0949778
total words is 125901
time3===========0.0821608
测试类：
package com.company;
import java.util.ArrayList;
public class Main {
/*public static void main(String[] args) {
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile("pride-and-prejudice.txt",words)){
System.out.println("total words is "+words.size());
}
Map<String,Integer> map = new LinkedListMap<>();
for(String word : words){
if(map.contains(word)){
map.set(word,map.get(word)+1);
}else{
map.add(word,1);
}
}
System.out.println("different words is "+map.getSize());
System.out.println("pride size is"+map.get("pride"));
System.out.println("prejudice size is"+map.get("prejudice"));
// write your code here
}*/
/*public static void main(String[] args) {
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile("pride-and-prejudice.txt",words)){
System.out.println("total words is "+words.size());
}
Map<String,Integer> map = new BSTMap<>();
for(String word : words){
if(map.contains(word)){
map.set(word,map.get(word)+1);
}else{
map.add(word,1);
}
}
System.out.println("different words is "+map.getSize());
System.out.println("pride size is"+map.get("pride"));
System.out.println("prejudice size is"+map.get("prejudice"));
// write your code here
}*/
private static double testTime(String fileName,Map<String,Integer> map){
long time1 = System.nanoTime();
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile(fileName,words)){
System.out.println("total words is "+words.size());
}
for(String word : words){
if(map.contains(word)){
map.set(word,map.get(word)+1);
}else{
map.add(word,1);
}
}
for(String word:words){
map.contains(word);
}
/*System.out.println("different words is "+map.getSize());
System.out.println("pride size is"+map.get("pride"));
System.out.println("prejudice size is"+map.get("prejudice"));*/
long time2 = System.nanoTime();
return (time2 - time1) / 1000000000.0;
}
public static void main(String[] args) {
Map<String,Integer> map1 = new LinkedListMap<>();
double time1 = testTime("pride-and-prejudice.txt",map1);
System.out.println("time1==========="+time1);
BSTMap<String,Integer> map2 = new BSTMap<>();
double time2 = testTime("pride-and-prejudice.txt",map2);
System.out.println("time2==========="+time2);
AVLMap<String,Integer> map3 = new AVLMap<>();
double time3 = testTime("pride-and-prejudice.txt",map3);
System.out.println("time3==========="+time3);
}
}
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;
}
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{
//已找到要删除的元素
//1 如果只有左子节点或只有右子节点，则直接将子节点替换
if(node.left==null){
retNode = node.right;
size--;
}else if(node.right==null){
retNode = node.left;
size--;
}else{
//2 如果有左子节点和右子节点，则寻找前驱或后继 对当前节点替换掉
Node nodeMain = findMin(node.right);
nodeMain.right = remove(node.right,nodeMain.key);//这块要么用removMin方法（添加维护平衡的代码），要么复用remove方法(删除以node右子树为根的二叉树的最小值)
nodeMain.left = node.left;
node.left = node.right = null;
retNode = nodeMain;
size--;
}
}
if(retNode==null){
return null;
}
retNode.height = 1+Math.max(getHeight(retNode.left),getHeight(retNode.right));
int balanceFactor = getBalanceFactor(retNode);
//左左情况
if(balanceFactor>1&&getBalanceFactor(retNode.left)>=0){
return rightRotate(retNode);
//右右情况
}else if(balanceFactor<-1&&getBalanceFactor(retNode.right)<=0){
return leftRotate(retNode);
//左右情况
}else if(balanceFactor>1&&getBalanceFactor(retNode.left)<0){
//先对左子节点左旋转，然后整体右旋转
retNode.left = leftRotate(retNode.left);
return rightRotate(retNode);
//右左情况
}else if(balanceFactor<-1&&getBalanceFactor(retNode.right)>0){
retNode.right = rightRotate(retNode.right);
return leftRotate(retNode);
}
return retNode;
}
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){
root = remove(root, key);
return node.value;
}
return null;
}
//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());
for(String word:words){
avlTree.remove(word);
if(!avlTree.judgeBalance()||!avlTree.judgeBST()){
System.out.println("平衡二叉树删除元素后不满足二叉树或者平衡二叉树性质");
}
}
}
}
}
写回答
1回答
-
liuyubobobo
2023-04-20
AVL 的改进是在 BST 退化的情况下才能显现出来，对于通常数据，大体随机分布的情况，AVL 的性能和 BST 就是不大。
一个简单的让 BST 退化的方式是，把插入的元素排序，按顺序插入，再按顺序查找，再按顺序删除，应该能看到 BST 和 AVL 的显著性能差异。
继续加油！：）
032023-04-26
相似问题