HashMap为什么使用红黑树而不用普通的AVL树_map为什么用红黑树不用avl树

作者：2023面试高手 | 2024-04-21 11:22:22

踩

map为什么用红黑树不用avl树

红黑树是一种平衡二叉树，要求从根到叶子的最长路径不会超过最短路径的2倍。

AVL树是高度平衡的二叉树，左右子树树高不超过1。

【补充】AVL是Adelson-Velskii和Landis树的缩写，是一种用于排序的二叉搜索树。

一般用平衡因子判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1，和红黑树相
比，AVL树是高度平衡的二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过
1)，不管我们是执行插入还是除操作，只要不满足上面的条件，就要通过旋转来保持平衡，
而由于旋转比较耗时，由此我们可以知道AVL树适合用于插入与删除次数比较少，但查找多的情况。

在这里插入图片描述

参考资料：【5分钟背八股】169：hashmap为什么用红黑树不用普通的AVL树？

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/462722