平衡二叉树AVL(JS实现) 左手的ㄟ右手 2022-04-04 11:40 303阅读 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/
相关 平衡二叉树 <table style="width:1615px; margin-bottom:20px; background-color:transparent"> <tbody> 淡淡的烟草味﹌/ 2022年06月02日 07:59/ 0 赞/ 232 阅读
相关 平衡二叉树 平衡二叉树(Balanced Binary Tree)是二叉查找树的一个进化体,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和 E.M. 墨蓝/ 2022年05月28日 08:57/ 0 赞/ 401 阅读
相关 平衡二叉树 写在前面 > 剑指offer:平衡二叉树 题目要求 > 输入一棵二叉树,判断该二叉树是否是平衡二叉树。平衡二叉树要求任意一个节点的左右字数之间的高度差不超过1。 浅浅的花香味﹌/ 2022年05月17日 01:54/ 0 赞/ 271 阅读
相关 平衡二叉树 平衡二叉树又称AVL树。它或者是颗空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。若将二叉树节点的平衡因子BF定 骑猪看日落/ 2022年05月17日 01:24/ 0 赞/ 244 阅读
相关 平衡二叉树 时间限制:1秒 空间限制:32768K 热度指数:160212 [ 算法知识视频讲解][Link 1] 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 向右看齐/ 2022年03月08日 01:44/ 0 赞/ 292 阅读
相关 平衡二叉树(c++)实现 [平衡二叉树(c++)实现][c] \------ 欢迎指正------- 1、参考资料: 书籍:《算法导论》 博文:[http://www.cnblogs 淩亂°似流年/ 2022年02月28日 08:14/ 0 赞/ 207 阅读
相关 平衡二叉树 平衡二叉树介绍 是由前苏联的两位数学家G.M.Adelse-Velskil和E.M.Landis提出,因此一般也称作AVL树,AVL树本质还是一棵二叉查找树,只是在其基础 青旅半醒/ 2022年02月24日 07:54/ 0 赞/ 328 阅读
相关 平衡二叉树 (平衡查找树) 平衡二叉树(AVL 树) 看一个案例(说明二叉排序树可能的问题) ![1460404-20190609204205330-1398837969.png][] 上 小咪咪/ 2021年10月29日 07:24/ 0 赞/ 442 阅读
相关 平衡二叉树 package com.avl; / @Auther: 大哥的叔 @Date: 2019/8/18 06:12 @ 忘是亡心i/ 2021年10月15日 05:37/ 0 赞/ 392 阅读
相关 二叉平衡树 二叉平衡树 说起这个树,我找了整整两天的时间,刚开始考虑的不周全,然后就一直该一直该,一直加一直加。 定义: 它是一颗空疏或它的左右两个子树的高度差的绝对值不超过 Dear 丶/ 2021年09月22日 09:42/ 0 赞/ 445 阅读
还没有评论,来说两句吧...