专注Java教育14年 全国咨询/投诉热线:400-8080-105
动力节点LOGO图
始于2009,口口相传的Java黄埔军校
首页 hot资讯 让我们简单的看下什么是平衡二叉树

让我们简单的看下什么是平衡二叉树

更新时间:2023-02-08 16:54:01 来源:动力节点 浏览976次

平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

什么是平衡二叉树

1、平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。替罪羊树是 计算机科学中,一种基于部分重建的自平衡二叉搜索树。在替罪羊树上,插入或删除节点的平摊最坏 时间复杂度是O(log n),搜索节点的最坏时间复杂度是O(log n)。在非平衡的 二叉搜索树中,每次操作以后检查操作路径,找到最高的满足max(size(son_L),size(son_R))>alpha*size(this)的结点,重建整个子树。

什么是平衡二叉树

2、红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构。红黑树这些节点中的某一个节点总是担当启始位置的功能,它不是任何节点的儿子;我们称之为根节点或根。它有最多两个"儿子",都是它连接到的其他节点。所有这些儿子都可以有自己的儿子,以此类推。这样根节点就有了把它连接到在树中任何其他节点的路径。

什么是平衡二叉树

3、AVL是最先发明的自平衡二叉查找树算法。从AVL树中删除,可以通过把要删除的节点向下旋转成一个叶子节点,接着直接移除这个叶子节点来完成。因为在旋转成叶子节点期间最多有log n个节点被旋转,而每次AVL旋转耗费固定的时间,所以删除处理在整体上耗费O(log n) 时间。

以上就是动力节点小编介绍的"让我们简单的看下什么是平衡二叉树",希望对大家有帮助,如有疑问,请在线咨询,有专业老师随时为您务。

提交申请后,顾问老师会电话与您沟通安排学习

免费课程推荐 >>
技术文档推荐 >>