平衡二叉树AVL(JS实现) 左手的ㄟ右手 2022-04-04 11:40 276阅读 0赞 ## 1 定义 ## **平衡二叉树**是一种[二叉排序树][Link 1],其中每个节点的左子树和右子树的高度差至多等于1。其中,二叉树节点的左子树深度减去右子树深度的值称为**平衡因子**(BF),因此平衡二叉树节点的平衡因子值只能为1、0或-1。距离插入节点最近的,且平衡因子的绝对值大于1的节点为根的子树,我们称为**最小不平衡子树**。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70] ## 2 平衡二叉树的构建过程 ## 平衡二叉树的构建过程基于二叉排序树的构建过程,在插入节点的过程中,一旦出现不平衡现象(即某节点的平衡因子大于1或小于-1),就找出最小不平衡子树,进行“旋转”操作,调整最小不平衡子树中各节点的链接关系,使之成为新的平衡子树。“旋转过程”就好比一条扁担出现一头重一头轻的现象,若能将扁担的支撑点改变,扁担两头就平衡了。 **前人总结出在二叉排序树中插入节点而失去平衡的情况下,对最小不平衡子树进行调整,有4种“旋转”类型(LL型,RR型,LR型,RL型),分别对应不同的不平衡情况。其中LL型和RR型只需要一次旋转,而LR型和RL型则需要两次旋转。每种类型又可进一步细分为3种情况,总共4×3=12种情况** **LL型**(最小不平衡子树的根结点平衡因子值大于1且与根结点左孩子节点的平衡因子符号相同) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 1] **RR型**(最小不平衡子树的根结点平衡因子值小于-1且与根结点右孩子节点的平衡因子符号相同) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 2] **LR型**(最小不平衡子树的根结点平衡因子值大于1且与根结点左孩子节点的平衡因子符号不相同) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 3] **RL型**(最小不平衡子树的根结点平衡因子值小于-1且与根结点右孩子节点的平衡因子符号不相同) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 4] **注意最小不平衡子树中节点的平衡因子值在旋转调整前后的变化,其中LL型和RR型平衡因子变化一致,而LR型和RL型则需分开讨论** ## 3 代码 ## 首先建立二叉树节点进行定义 function Node(key){ this.data = key; //存储数据 this.bf = 0; //平衡因子 this.lChild = null; //左孩子节点 this.rChild = null; //右孩子节点 } 接着是对不平衡子树中某一节点T的一次左旋和右旋操作函数代码,返回旋转后的新节点 //左旋 function L_Rotate(T){ let R = T.rChild; T.rChild = R.lChild; R.lChild = T; return R; } //右旋 function R_Rotate(T){ let L = T.lChild; T.lChild = L.rChild; L.rChild = T; return L; } 现在我们假设对根结点为T的不平衡子树做左旋和右旋操作函数分别为`LeftBalance(T)`和`RightBalance(T)`,该函数返回新的根结点。那么平衡二叉树的插入操作代码如下 var taller = true; var temp = null; function insertAVL(T,key){ //插入节点至平衡二叉树 if (!T){ //节点不存在,则在此位置新建节点 T = new Node(key); taller = true; }else{ if (key === T.data){ //如果二叉树中已有与key相同的值,而不插入 taller = false; return 0; }else if (key < T.data){ //如果插入值小于当前节点值 temp = insertAVL(T.lChild,key); //则在当前节点的左子树继续搜索 if ( temp === 0) return 0; //未插入 T.lChild = temp; if (taller){ switch (T.bf){ //在当前节点的左子树成功插入节点时 case 1: //原本左子树比右子树高,插入节点后,需要做平衡处理 T = leftBalance(T); taller = false; break; case 0: //原本左子树和右子树一样高,插入节点后,树长高 T.bf = 1; taller = true; break; case -1: //原本左子树比右子树矮,插入节点后,现左右树等高 T.bf = 0; taller = false; break; } } }else{ //如果插入值大于当前节点值 temp = insertAVL(T.rChild,key); //则在当前节点的右子树继续搜索 if ( temp === 0) return 0; //未插入 T.rChild = temp; if (taller){ switch (T.bf){ //在当前节点的右子树成功插入节点时 case 1: //原本左子树比右子树高,插入节点后,现左右树等高 T.bf = 0; taller = false; break; case 0: //原本左子树和右子树一样高,插入节点后,树长高 T.bf = -1; taller = true; break; case -1: //原本左子树比右子树矮,插入节点后,需要做平衡处理 T = rightBalance(T); taller = false; break; } } } } return T; } 最后一步,实现对根结点为T的不平衡子树的旋转操作,需要分情况讨论只用一次旋转还是要有两次旋转。 function leftBalance(T){ //对根结点为T的不平衡子树进行旋转调整操作 let lc = T.lChild; //根结点的左孩子 switch (lc.bf){ case 1: //新节点插入在根结点左孩子的左子树。为LL型 lc.bf = 0; T.bf = 0; return R_Rotate(T); //LL型为一次旋转 case -1: //新节点插入在根结点左孩子的右子树。为LR型 let rd = lc.rChild; //指向根结点左孩子的右子树根 switch (rd.bf){ //对应LR型的三种平衡因子变化情况 case 1: lc.bf = 0; T.bf = -1; break; case -1: lc.bf = 1; T.bf = 0; break; case 0: lc.bf = 0; T.bf = 0; break; } rd.bf = 0; T.lChild = L_Rotate(T.lChild); //LR型为两次旋转 return R_Rotate(T); } } function rightBalance(T){ //对根结点为T的不平衡子树进行旋转调整操作 let rc = T.rChild; //根结点的右孩子 switch (rc.bf){ case -1: //新节点插入在根结点左孩子的左子树。为RR型 rc.bf = 0; T.bf = 0; return L_Rotate(T); //RR型为一次旋转 case 1: //新节点插入在根结点左孩子的右子树。为RL型 let ld = rc.lChild; //指向根结点左孩子的右子树根 switch (ld.bf){ //对应RL型的三种平衡因子变化情况 case 1: rc.bf = -1; T.bf = 0; break; case -1: rc.bf = 0; T.bf = 1; break; case 0: rc.bf = 0; T.bf = 0; break; } ld.bf = 0; T.rChild = R_Rotate(T.rChild); //RL型为两次旋转 return L_Rotate(T); } } 平衡二叉树的删除操作更为复杂,先占个坑,以后有空再来慢慢研究,[https://blog.csdn.net/goodluckwhh/article/details/11786079/][https_blog.csdn.net_goodluckwhh_article_details_11786079] [Link 1]: https://blog.csdn.net/zjw_python/article/details/82320128 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70]: /images/20220404/1841a264531646a2a55f4cceaa213af3.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 1]: /images/20220404/ac3aff0be6204c5488220d389b4f5841.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 2]: /images/20220404/36df625e1d7d443a85fe94bcf2bbe607.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 3]: /images/20220404/d1413fff86354bdd8820886113b8ffd7.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 4]: /images/20220404/927d990e4f3042bfac3db62f8aeecfa2.png [https_blog.csdn.net_goodluckwhh_article_details_11786079]: https://blog.csdn.net/goodluckwhh/article/details/11786079/
还没有评论,来说两句吧...