完全二叉搜索树和AVL树的区别？

Question

完全二叉查找树和AVL树有区别吗？举个例子。

在 google 上搜索，但找到了 this。帮助不大

Answer 1

每棵完全二叉树都是AVL树，但反过来不一定。

完全二叉树是指除最后一层外的每一层都被完全填满的树。AVL 树是指每个节点的子节点都是高度最多相差 1 的 AVL 树。最大倾斜的 AVL 树是斐波那契树，它们通常不是完整的树。这是一个 AVL 树而非完整二叉树的示例：

          .
        /    \
     .         .
    / \       / \
   .   .     .   .
      /     /   / \
     .     .   .   .
                  /
                 .

Answer 2

AVL树和二叉搜索树是一样的，但是AVL树有一个约束，即左子树和右子树的高度差必须是0、1或-1。

如果任何二叉搜索树满足这些条件，它将被称为 AVL 树。

二叉搜索树+HEIGHT CONDITION是AVL树。

参考：Cormen 的算法简介 https://books.google.co.in/books..

完全二叉搜索树和AVL树的区别？

Difference between complete binary search tree and AVL tree?

data-structures

binary-search-tree

avl-tree