树型查找-平衡二叉树
树型查找-平衡二叉树
- 平衡二叉树结点数的递推公式为：n
0=0，n1=1，n2=2，nh=1+n（h-1）+nh-2- h为平衡二叉树高度，n
h为构造此高度的平衡二叉树所需的最少结点数 - 所有非叶结点的平衡因子均为1，即平衡二叉树满足平衡的最少结点情况，可用递推公式
- h为平衡二叉树高度，n
- AVL是高度平衡的二叉查找树，红黑树是适度平衡的二叉查找树
- 可以看出AVL的查找效率往往更优
- 自平衡的二叉排序树是指在插入和删除时能自动调整以保持其所定义的平衡性，红黑树和AVL都属于自平衡二叉树
- 在非空平衡二叉树中插入结点，在失去平衡调整前，一定插入在叶结点的位置。
- 若删除的是叶结点，则删除后平衡二叉树可能不会失去平衡，即不会发生调整，再插入此结点得到的二叉平衡树相同
- 若删除后平衡二叉树失去平衡而发生调整，再插入结点得到的二叉平衡树与可能不同。