二叉树,AVL,B,B+树的区别

Height-Balanced Binary Search(平衡二叉树):是一种二叉排序树,不同的是其中每个节点的左子树和右子树的高度差(平衡因子Balance Factor)至多等于1;而对于二叉排序树不是必要的。

平衡的关键在于,当构建过程当中出现最小不平衡子树的时候,适当的进行改造,使其时刻满足平衡的要求。

距离插入节点最近的,且平衡因子(简称BF)的绝对值大于1的节点为根的子树,我们称为最小不平衡子树。

BF值为正,最小不平衡子树进行右旋;BF值为负,最小不平衡子树进行左旋。【注意旋转时要时刻保持二叉排序树特性】

当遇到最小不平衡子树的根节点与其子节点的BF符号不统一的时候;首先根据其子节点的BF符号进行旋转,再根据最小不平衡子树根节点的BF进行旋转。

原文地址:https://www.cnblogs.com/LearnSB/p/13275449.html