所有栏目

什么是不平衡二叉树

已输入 0 字
优质回答
  • 它或者是一颗空树,或者具有以下性质的二叉树:它的左子树和右子树的深度之差的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。

    平衡因子(bf):结点的左子树的深度减去右子树的深度,那么显然-1<=bf<=1;

    很显然,平衡二叉树是在二叉排序树(BST)上引入的,就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降,那么AVL就保持住了(BST)的最好时间复杂度O(logn),所以每次的插入和删除都要确保二叉树的平衡

    2023-10-24 19:21:17
  • 二叉搜索树(Binary Search Tree),又叫二叉排序树,简单而言就是左子树上所有节点的值均小于根节点的值,而右子树上所有结点的值均大于根节点的值,左小右大,并不是乱序,因此得名二叉排序树。

    2023-10-24 19:21:17
最新问题 全部问题