数据结构与算法手撕平衡二叉树

　　平衡二叉树定义
　　动机：二叉查找树的操作实践复杂度由树高度决定，所以希望控制树高，左右子树尽可能平衡。平衡二叉树（AVL树）：称一棵二叉查找树为高度平衡树，当且仅当或由单一外结点组成，或由两个子树形Ta和Tb组成，并且满足：h（Ta）h（Tb）1，其中h（T）表示树T的高度Ta和Tb都是高度平衡树
　　即：每个结点的左子树和右子树的高度最多差1的二叉查找树。设T为高度平衡树中结点q的平衡系数为q的右子树高度减去左子树高度高度平衡树所以结点的平衡系数只可能为：1，0，1结点结构
　　1key：关键字的值
　　2value：关键字的存储信息
　　3height：树的高度（只有一个结点的树的高度为1）
　　4left：左子树根结点的的引用
　　5right：右子树根结点的引用复制代码12345678910111213JAVAclassAVLNodeKextendsComparableK，V｛publicKpublicVpublicAVLNodeK，VpublicAVLNodeK，VpublicAVLNode（Kkey，Vvalue，intheight）｛this。this。this。｝｝查找算法
　　同二叉查找树的查找算法：【数据结构与算法】手撕二叉查找树插入算法
　　AVL树是一种二叉查找树，故可以使用二叉查找树的插入方法插入结点，但插入一个新结点时，有可能破坏AVL树的平衡性。
　　如果发生这种情况，就需要在插入结点后对平衡树进行调整，恢复平衡的性质。实现这种调整的操作称为旋转。
　　在插入一个新结点X后，应调整失去平衡的最小子树，即从插入点到根的路径向上找第一个不平衡结点A。
　　平衡因子：该结点的左子树高度和右子树高度的差值。如果差值的绝对值小于等于1，则说明该结点平衡，如果差值的绝对值为2（不会出现其他情况），则说明该结点不平衡，需要做平衡处理。
　　造成结点A不平衡的的原因以及调整方式有以下几种情况。LL型
　　A结点的平衡因子为2，说明该结点是最小不平衡结点，需要对A结点进行调整。问题发生在A结点左子结点的左子结点，所以为LL型。
　　扁担原理：右旋将A的左孩子B提升为新的根结点；将原来的根结点A降为B的右孩子；各子树按大小关系连接（BL和AR不变，BR调整为A的左子树）。高度调整：由于调整后B的高度依赖于A的高度，所以先更新A的高度，再更新B的高度。复制代码12345678JAVAprivateAVLNodeK，VrightRotate（AVLNodeK，Va）｛AVLNodeK，Vba。a。leftb。b。a。heightMath。max（getHeight（a。left），getHeight（a。right））1；b。heightMath。max（getHeight（b。left），getHeight（b。left））1；｝RR型
　　A结点的平衡因子为2，说明该结点是最小不平衡结点，需要对A结点进行调整。问题发生在A结点右子结点的右子结点，所以为RR型。
　　扁担原理：左旋将A的右孩子B提升为新的根结点；将原来的根结点A降为B的左孩子；各子树按大小关系连接（AL和BR不变，BL调整为A的右子树）。高度调整：由于调整后B的高度依赖于A的高度，所以先更新A的高度，再更新B的高度。复制代码12345678JAVAprivateAVLNodeK，VleftRotate（AVLNodeK，Va）｛AVLNodeK，Vba。a。rightb。b。a。heightMath。max（getHeight（a。left），getHeight（a。right））1；b。heightMath。max（getHeight（b。left），getHeight（b。left））1；｝LR型
　　A结点的平衡因子为2，说明该结点是最小不平衡结点，需要对A结点进行调整。问题发生在A结点左子结点的右子结点，所以为LR型。
　　从旋转的角度：对B左旋，然后对A右旋将B的左孩子C提升为新的根结点；将原来的根结点A降为C的右孩子；各子树按大小关系连接（BL和AR不变，CL和CR分别调整为B的右子树和A的左子树）。复制代码1234JAVAprivateAVLNodeK，VleftRightRotate（AVLNodeK，Va）｛a。leftleftRotate（a。left）；对B左旋returnrightRotate（a）；对A右旋｝RL型
　　A结点的平衡因子为2，说明该结点是最小不平衡结点，需要对A结点进行调整。问题发生在A结点右子结点的左子结点，所以为RL型。
　　从旋转的角度：对B右旋，然后对A左旋将B的左孩子C提升为新的根结点；将原来的根结点A降为C的左孩子；各子树按大小关系连接（AL和BR不变，CL和CR分别调整为A的右子树和B的左子树）。复制代码1234JAVAprivateAVLNodeK，VrightLeftRotate（AVLNodeK，Va）｛a。rightrightRotate（a。right）；returnleftRotate（a）；｝插入方法根结点默认高度为1某结点的左右子树高度差的绝对值为2，则需要进行平衡处理左子树高key小于root。left。key：LL型，进行右旋key大于root。left。key：LR型，进行左右旋右子树高key大于root。right。key：RR型，进行左旋key小于root。right。key：RR型，进行右左旋复制代码123456789101112131415161718192021222324252627282930313233JAVApublicvoidinsert（Kkey，Vvalue）｛rootinsert（root，key，value）；｝privateAVLNodeK，Vinsert（AVLNodeK，Vt，Kkey，Vvalue）｛if（tnull）｛returnnewAVLNode（key，value，1）；｝elseif（key。compareTo（t。key）0）｛t。leftinsert（t。left，key，value）；t。heightMath。max（getHeight（t。left），getHeight（t。right））1；平衡因子判断if（getHeight（t。left）getHeight（t。right）2）｛if（key。compareTo（root。left。key）0）左左：右旋trightRotate（t）；else左右：先左旋，再右旋tleftRightRotate（t）；｝｝elseif（key。compareTo（t。key）0）｛t。rightinsert（t。right，key，value）；t。heightMath。max（getHeight（t。left），getHeight（t。right））1；平衡因子判断if（getHeight（t。left）getHeight（t。right）2）｛if（key。compareTo（root。right。key）0）右右：左旋tleftRotate（t）；else右左：先右旋，再左旋trightLeftRotate（t）；｝｝else｛t。｝｝删除算法概述可采用二叉查找树的删除算法进行删除。
　　【数据结构与算法】手撕二叉查找树删除某结点X后，沿从X到根节点的路径上考察沿途结点的平衡系数，若第一个不平衡点为A，平衡以A为根的子树。平衡后，可能使子树A高度变小。这样可能导致A的父节点不满足平衡性。所以要继续向上考察结点的平衡性，最远可能至根结点，即最多需要做O（logn）次旋转。对比插入操作：平衡A后，子树高度不变，A子树以外的结点不受影响，即插入最多涉及O（1）次旋转。实例分析
　　下面举个删除的例子：
　　删除以下平衡二叉树中的16结点
　　116为叶子，将其删除即可，如下图。
　　2指针g指向实际被删除节点16之父25，检查是否失衡，25节点失衡，用g、u、v记录失衡三代节点（从失衡节点沿着高度大的子树向下找三代），判断为RL型，进行RL旋转调整平衡，如下图所示。
　　3继续向上检查，指针g指向g的双亲69，检查是否失衡，69节点失衡，用g、u、v记录失衡三代节点，判断为RR型，进行RR旋转调整平衡，如下图所示。
　　代码
　　代码描述：若当前结点为空，则返回该节点若关键值小于当前结点的关键值，则递归处理该结点的左子树若关键值大于当前结点的关键值，则递归处理该结点的右子树若关键值等于当前结点的关键值若当前结点的左子树为空，则返回该结点的右子树根节点若当前结点的右子树为空，则返回该结点的左子树根节点若当前结点左右子树都不为空，则找到该结点的中序前驱结点（该结点左子树的最右结点）或中序后继结点（该结点右子树的最左结点），将其值赋予该结点，然后递归删除中序前驱或后继结点。更新结点高度若该结点左子树高度更高，且处于不平衡状态若为LL型，进行右旋若为LR型，先左旋，再右旋若该结点右子树高度更高，且处于不平衡状态若为RL型，先右旋，再左旋若我RR型，进行左旋返回该结点复制代码1234567891011121314151617181920212223242526272829303132333435363738394041424344JAVApublicvoidremove（Kkey）｛this。rootdelete（root，key）；｝publicAVLNodeK，Vdelete（AVLNodeK，Vt，Kkey）｛if（tnull）if（key。compareTo（t。key）0）｛t。leftdelete（t。left，key）；｝elseif（key。compareTo（t。key）0）｛t。rightdelete（t。right，key）；｝else｛if（t。leftnull）returnt。elseif（t。rightnull）returnt。else｛t。left！nullt。right！nullAVLNodeK，Vpret。while（pre。right！null）｛prepre。｝t。keypre。t。valuepre。t。leftdelete（t。left，t。key）；｝｝if（tnull）t。heightMath。max（getHeight（t。left），getHeight（t。right））1；if（getHeight（t。left）getHeight（t。right）2）｛if（getHeight（t。left。left）getHeight（t。left。right））｛returnrightRotate（t）；｝else｛returnleftRightRotate（t）；｝｝elseif（getHeight（t。left）getHeight（t。right）2）｛if（getHeight（t。right。left）getHeight（t。right。right））｛returnrightLeftRotate（t）；｝else｛returnleftRotate（t）；｝｝｝完整代码复制代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171JAVAclassAVLNodeKextendsComparableK，V｛publicKpublicVpublicAVLNodeK，VpublicAVLNodeK，VpublicAVLNode（Kkey，Vvalue，intheight）｛this。this。this。｝｝classAVLTreeKextendsComparableK，V｛publicAVLNodeK，VpublicintgetHeight（AVLNodeK，Vt）｛returntnull？0：t。｝publicvoidinsert（Kkey，Vvalue）｛rootinsert（root，key，value）；｝publicvoidremove（Kkey）｛this。rootdelete（root，key）；｝publicAVLNodeK，Vdelete（AVLNodeK，Vt，Kkey）｛if（tnull）if（key。compareTo（t。key）0）｛t。leftdelete（t。left，key）；｝elseif（key。compareTo（t。key）0）｛t。rightdelete（t。right，key）；｝else｛if（t。leftnull）returnt。elseif（t。rightnull）returnt。else｛t。left！nullt。right！nullAVLNodeK，Vpret。while（pre。right！null）｛prepre。｝t。keypre。t。valuepre。t。leftdelete（t。left，t。key）；｝｝if（tnull）t。heightMath。max（getHeight（t。left），getHeight（t。right））1；if（getHeight（t。left）getHeight（t。right）2）｛if（getHeight（t。left。left）getHeight（t。left。right））｛returnrightRotate（t）；｝else｛returnleftRightRotate（t）；｝｝elseif（getHeight（t。left）getHeight（t。right）2）｛if（getHeight（t。right。left）getHeight（t。right。right））｛returnrightLeftRotate（t）；｝else｛returnleftRotate（t）；｝｝｝privateAVLNodeK，Vinsert（AVLNodeK，Vt，Kkey，Vvalue）｛if（tnull）｛returnnewAVLNode（key，value，1）；｝if（key。compareTo（t。key）0）｛t。leftinsert（t。left，key，value）；平衡因子判断if（getHeight（t。left）getHeight（t。right）2）｛if（key。compareTo（t。left。key）0）左左：右旋trightRotate（t）；else左右：先左旋，再右旋tleftRightRotate（t）；｝｝elseif（key。compareTo（t。key）0）｛t。rightinsert（t。right，key，value）；平衡因子判断if（getHeight（t。left）getHeight（t。right）2）｛if（key。compareTo（t。right。key）0）右右：左旋tleftRotate（t）；else右左：先右旋，再左旋trightLeftRotate（t）；｝｝else｛t。｝t。heightMath。max（getHeight（t。left），getHeight（t。right））1；｝privateAVLNodeK，VrightLeftRotate（AVLNodeK，Va）｛a。rightrightRotate（a。right）；returnleftRotate（a）；｝privateAVLNodeK，VleftRightRotate（AVLNodeK，Va）｛a。leftleftRotate（a。left）；returnrightRotate（a）；｝privateAVLNodeK，VleftRotate（AVLNodeK，Va）｛AVLNodeK，Vba。a。rightb。b。a。heightMath。max（getHeight（a。left），getHeight（a。right））1；b。heightMath。max（getHeight（b。left），getHeight（b。right））1；｝privateAVLNodeK，VrightRotate（AVLNodeK，Va）｛AVLNodeK，Vba。a。leftb。b。a。heightMath。max（getHeight（a。left），getHeight（a。right））1；b。heightMath。max（getHeight（b。left），getHeight（b。right））1；｝privatevoidinorder（AVLNodeK，Vroot）｛if（root！null）｛inorder（root。left）；System。out。print（（key：root。key，value：root。value，height：root。height））；inorder（root。right）；｝｝privatevoidpreorder（AVLNodeK，Vroot）｛if（root！null）｛System。out。print（（key：root。key，value：root。value，height：root。height））；preorder（root。left）；preorder（root。right）；｝｝privatevoidpostorder（AVLNodeK，Vroot）｛if（root！null）｛postorder（root。left）；postorder（root。right）；System。out。print（（key：root。key，value：root。value，height：root。height））；｝｝publicvoidpostorderTraverse（）｛System。out。print（后序遍历：）；postorder（root）；System。out。println（）；｝publicvoidpreorderTraverse（）｛System。out。print（先序遍历：）；preorder（root）；System。out。println（）；｝publicvoidinorderTraverse（）｛System。out。print（中序遍历：）；inorder（root）；System。out。println（）；｝｝
　　方法测试复制代码1234567891011121314151617181920JAVApublicstaticvoidmain（String〔〕args）｛AVLTreeInteger，IntegertreenewAVLTree（）；tree。insert（69，1）；tree。insert（25，1）；tree。insert（80，1）；tree。insert（16，1）；tree。insert（56，1）；tree。insert（75，1）；tree。insert（90，1）；tree。insert（30，1）；tree。insert（78，1）；tree。insert（85，1）；tree。insert（98，1）；tree。insert（82，1）；tree。remove（16）；tree。preorderTraverse（）；tree。inorderTraverse（）；tree。postorderTraverse（）；｝
　　输出复制代码123JAVA先序遍历：（key：80，value：1，height：4）（key：69，value：1，height：3）（key：30，value：1，height：2）（key：25，value：1，height：1）（key：56，value：1，height：1）（key：75，value：1，height：2）（key：78，value：1，height：1）（key：90，value：1，height：3）（key：85，value：1，height：2）（key：82，value：1，height：1）（key：98，value：1，height：1）中序遍历：（key：25，value：1，height：1）（key：30，value：1，height：2）（key：56，value：1，height：1）（key：69，value：1，height：3）（key：75，value：1，height：2）（key：78，value：1，height：1）（key：80，value：1，height：4）（key：82，value：1，height：1）（key：85，value：1，height：2）（key：90，value：1，height：3）（key：98，value：1，height：1）后序遍历：（key：25，value：1，height：1）（key：56，value：1，height：1）（key：30，value：1，height：2）（key：78，value：1，height：1）（key：75，value：1，height：2）（key：69，value：1，height：3）（key：82，value：1，height：1）（key：85，value：1，height：2）（key：98，value：1，height：1）（key：90，value：1，height：3）（key：80，value：1，height：4）本文作者：gonghr
　　本文链接：https：www。cnblogs。comgonghrp16064797。html