树的定义问题

Question

老师您好，学完了二分搜索树，我自己学网上找了一下相关的树的知识。看到网上对于树的一些定义，我感觉有点不对，但是看到很多人都是这么说（不知是什么时候开始这样传的），比如平衡二叉树（Balanced BinaryTree）又被称为AVL树。我先讲我的理解，不知对不对，如果我说的不对，可以帮我指正吗？
首先我的理解是，将平衡二叉树称做AVL树是不对的，平衡树是任意节点的子树的高度差都小于等于1。平衡树不只是有AVL树，B树，红黑树也是平衡树。而且二叉树不能不只是有二叉搜索树，还可以有二叉树不是搜索树。我不知道他们这些定义是如何来的，而且好像传了很多。
我对树分类如下
二叉树（Binary tree）指树中节点的度不大于2的有序树。
二叉搜索树（Binary Search Tree）在二叉树的基础上进一步定义。
平衡树（Balance Tree）是任意节点的子树的高度差都小于等于1。
AVL树（Adelson-Velsky and Landis Tree）在二叉搜索树和平衡树的基础定义之上定义的树。
红黑树（Red–black tree）在二叉搜索树和平衡树和AVL树的基础定义之上定义的树。
AVL树和红黑树可以说都是平衡二叉搜索树，但是不能反过来说平衡二叉树就是AVL树，他们具有继承关系。
AVL树和红黑树都是自平衡的二叉搜索树。他们只是自平衡的二叉搜索树的一种。

Answer 1

提问者 Mosea 2021-11-14 09:54:16

谢谢bobo老师的回答!老师的每一次回答都是那么用心，学生很受感动。

Answer 2

liuyubobobo 2021-11-14 02:34:13

赞！整体你的理解没有毛病，我补充几点：

你在问题主体说的“平衡二叉树（Balanced BinaryTree）又被称为AVL树”完全不正确。你的理解完全正确。“AVL 树是一种平衡二叉树，但平衡二叉树不是仅仅有 AVL 树”。

另外，是的，“二叉树不能不只是有二叉搜索树，还可以有二叉树不是搜索树”。只要一个树每个节点的子节点最多有两个，就是二叉树。但需要满足所有左子树结点小于自身，所有右子树节点大于自身，才叫二分搜索树。

你对“二叉树，二叉搜索树，平衡树，AVL树”的理解都是正确的。对于“红黑树”，稍微有一些复杂。

严格来说，红黑树不是“平衡二叉树”，因为红黑树的左右子树的高度差可能大于 1。但是，红黑树保证了左右子树的高度差，不可能多于 logn，也就是红黑树的最大高度值是 2logn 级别的，所以，其各项操作也能保证性能是 O(logn) 的。更具体的说，红黑树可以达到黑平衡，即黑节点的高度一定是 logn 的。要了解这些，就需要具体了解红黑树到底是怎么回事儿了。有兴趣可以在网上找相应资料仔细学习一下。我的体系课程中，对红黑树的一个“弱化的变种”：左倾红黑树，有比较详细的讲解：https://class.imooc.com/sale/datastructure

从另外一个角度，红黑树也不是基于 AVL 树的定义再加定义得到的。红黑树和 AVL 树都是为了解决单纯的 BST 可能退化成链表，而加入维护“自平衡”的机制，得到的。（这里自平衡加引号，就是因为红黑树的平衡不是严格意义的平衡，但是也能让各项操作性能达到 O(logn)，而不可能退化成 O(n)）这两种树的自平衡机制是不同的。（虽然如果你只是粗略地看各种资料，会发现似乎他们都需要使用类似“旋转”的操作，但实际上他们的思路是不同的。）

另外，你的问题中提到了 B 树。B 树不是二叉树，是平衡的多叉树。但我相信你了解这一点。另外，值的一提的是，B 树不仅仅是平衡的多叉树，还是“绝对平衡”的多叉树。即：左右子树的高度差一定是 0。B 树的最简单版本：2-3 树，也在我的体系课程中有概念性的讲解。（我们实际上是通过 2-3 树，来理解红黑树的原理的。）

再补充一下，除了你总结的这个线条以外，很多特殊作用的树，也是平衡二叉树。最典型的，二叉堆就是一棵平衡二叉树；线段树也是一棵平衡二叉树；等等。但是他们的作用是用在特殊的场合，而非一般的存储作用。

继续加油！：）