热门标签
热门文章
- 1InvalidSpecError: Invalid spec: =2.7报错解决办法
- 2Android Studio工具花样玩法（主题和字体）- mac_mac android studio 设置文字大小
- 3(26)[ICLR15] NEURAL MACHINE TRANSLATION BY JOINTLY LEARNING TO ALIGN AND TRANSLATE
- 4Linux笔记1_虚拟机安装Linux操作系统
- 5【Pytorch】PytorchCPU版或GPU报错异常处理（10X~4090D）
- 6解决java.lang.NoClassDefFoundError 问题
- 7使用vue-video-player播放列表循环，同一个video画面中循环播放列表_vue video循环播放
- 8python能写数据库吗_用 Python 写一个 NoSQL 数据库
- 9Clickhouse Kafka引擎表使用进阶
- 10SSH公/私秘钥的生成及使用_openssh生成公钥和私钥
当前位置: article > 正文
AVL树（平衡二叉搜索树）
作者：知新_RL | 2024-04-18 07:48:24
赞
踩
avl树
一、AVL树
1、AVL树的概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，时间复杂度位O(N),效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：
当向二叉搜索树中插入新结点后，如果能保证每个结点的*左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整，让它即满足二叉搜索树的要求，也接近于一颗完全二叉树)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
推荐阅读
相关标签
Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。
