p/structure-avl-tree/

[giscus[bot]]

p/structure-avl-tree/

平衡二叉树介绍 平衡二叉树，又称AVL树，实际上就是遵循一下两个特点的二叉树：\n每一子树中的左子树和右子树的深度都不超过1； 二叉树的每一个子树都要求是平衡二叉树。 只要是每个子树都满足左子树还有右子树的深度都不超过1即可。\n平衡因子 每一个结点都有各自的平衡因子，表示的就是左子树深度同右子树深度的差。\n平衡二叉树中的各结点平衡因子取值只可能是：0、1、-1.\n其中 （a） 的两棵二叉树中由于各个结点的平衡因子数的绝对值都不超过 1，所以 （a） 中两棵二叉树都是平衡二叉树；而 （b） 的两棵二叉树中有结点的平衡因子数的绝对值超过 1，所以都不是平衡二叉树。\n二叉排序树转化为平衡二叉树 为了排除动态查找表中不同的数据排列方式对算法性能的影响，需要考虑在不会破坏二叉排序树本身结构的前提下，将二叉排序树转化为平衡二叉树。\n例如，使用上一节的算法在对查找表{13，24，37，90，53}构建二叉排序树时，当插入 13 和 24 时，二叉排序树此时还是平衡二叉树：\n当继续插入 37 时，生成的二叉排序树如图 （a），平衡二叉树的结构被破坏，此时只需要对二叉排序树做“旋转”操作（如图（b）），即整棵树以结点 24 为根结点，二叉排序树的结构没有破坏，同时将该树转化为了平衡二叉树：\n当二叉排序树的平衡性被打破时，就如同扁担的两头出现了一头重一头轻的现象，如图（a）所示，此时只需要改变扁担的支撑点（树的树根），就能使其重新归为平衡。实际上（b） 是对（a） 的二叉树做了一个向左逆时针旋转的操作。\n继续插入 90 和 53 后，二叉排序树如图 （a）所示，导致二叉树中结点 24 和 37 的平衡因子的绝对值大于 1 ，整棵树的平衡被打破。此时，需要做两步操作：\n如图 （b） 所示，将结点 53 和 90 整体向右顺时针旋转，使本该以 90 为根结点的子树改为以结点 53 为根结点； 如图 （c） 所示，将以结点 37 为根结点的子树向左逆时针旋转，使本该以 37 为根结点的子树，改为以结点 53 为根结点；

https://blog.debuginn.com/p/structure-avl-tree/