这个树是不是平衡二叉树,如果不是,请说明为什么?怎么算?

发布网友发布时间：2022-04-28 23:08

共1个回答

热心网友时间：2022-06-24 23:36

首先，对于不同的平衡定义有不同的平衡二叉树

1. 如果定义”平衡“为：左右子树的高度差的绝对值不超过1，也就是说|h(tree.left)-h(tree.right)|<=1。那么称这样的平衡二叉树为AVL数

2.若定义”平衡“为：较深的子树的高度不超过另一个子树的两倍，如H(tree.left)<=2*H(tree.right)，其中左子树较深。那么称这样的平衡二叉树为红黑树（RB-Tree）

3.当然，还有很多其他的平衡二叉树

另外：这个平衡的定义是递归的，也就是说：左子树和右子树也必须是一个平衡二叉树。

对二叉树进行平衡的目的是使得整个二叉树的高度降下来，那么我们对二叉树进行遍历或者查找的时间复杂度就能降下来，因为这个时间复杂度和二叉树的高度是正相关的。通常我们所说的平衡二叉树指的是AVL树。

因此图中的二叉树既是AVL平衡二叉树，也是一个红黑树。可以通过定义验证。