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

平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过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) 时间。

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