二叉搜索树在最好的情况下搜索的时间复杂度为O(logn),但如果插入节点时,插入元素序列本身就是有序的,那么BST树就退化成一个线性表了,搜索的时间复杂度为O(n)。
如果想要减少比较次数,就需要降低树的高度。在插入和删除节点时,要保证插入节点后不能使叶子节点之间的深度之差大于1,这样就能保证整棵树的深度最小,这就是AVL树解决BST搜索性能降低的策略。但由于每次插入或删除节点后,都可能会破坏AVL的平衡,而要动态保证AVL的平衡需要很多操作,这些操作会影响整个数据结构的性能,除非是在树的结构变化特别少的情形下,否则AVL树平衡带来的搜索性能提升有可能还不足为了平衡树所带来的性能损耗。
因此,引入了2-3树来提升效率。2-3树本质也是一种平衡搜索树,但2-3树已经不是一棵二叉树了,因为2-3树允许存在3这种节点,3-节点中可以存放两个元素,并且可以有三个子节点。
课程介绍
课程目录
往期学员作品
用户评论
课程介绍
课程目录
往期学员作品
用户评论
你将获得
- 二三树的算法
教学服务
录播课程
讲师介绍
课程详情
温馨提示
- 请勿私下交易请勿在平台外交易。与机构和老师私下交易造成的任何损失及纠纷,腾讯课堂不承担任何责任
- 听课说明
1、电脑:访问腾讯课堂官网 ke.qq.com 查看我的课表或下载win/mac客户端听课
2、手机/平板:下载腾讯课堂APP, 进入学习页面听课