Java手写AVL树（非常详细）_java avl树

作者：繁依Fanyi0 | 2024-05-27 13:11:56

踩

java avl树

思维导图：

1. 二叉搜索树复杂度

AVL树需要二叉搜索树的先导知识，可以看上一篇文章：java实现，二叉搜索树(过程非常详细)

我们来分析一下BST的复杂度：

如下图左边部分，我们可以知道BST的添加、删除和搜索效率都非常的高，其复杂度与元素的个数没有关系，只与树的高度有关系，即复杂度为：O(h) ，h为树的高度，当BST为满二叉树时，其复杂度为O(logn)，n为元素个数，此时：O(h) == O(logn)

但是如果是按照从小到大的顺序添加结点，如上图右边所示，可以看到这样的BST与链表是一样的，其复杂度O(h) == O(n)

我们称这样的BST退化成了链表

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

Java手写AVL树（非常详细）_java avl树

文章目录

1. 二叉搜索树复杂度