AVL树的问题

问题描述

在看AVL树的时候遇到个问题：节点的平衡因子是它的右子树的高度减去它的左子树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的。不太理解这句话。以上图为例，我认为的是：15的左子树的高度是1，右子树的高度也是1，1-1应该等于0啊，怎么等于2呢。。。求解答。问题补充：chen_yongkai 写道

解决方案

3 7 17 20 在同一层左子数多了两层（4 13）和（9）所以高度差=2很明显的！！！

时间： 2024-10-08 20:57:20

AVL树的问题的相关文章

平衡二叉树:php实现平衡二叉树(avl树)

<?phprequire 'bstorder.php';$test = range(1, 10);//$test = array(3,9,1,4,8,5,7,6,2,10);$tree = new bst($test, true);//$tree->deletenode('30');(非平衡树可删除,平衡树的没写删除操作)print_r($tree->gettree());?>bstorder.php<?php/*** php实现二叉排序树* @author zhaojian

AVL树的实现代码

本文配套源码 /******************************************************************** created: 2007/08/28 filename: avltree.c author: Lichuang purpose: AVL树的实现代码, 参考资料<<数据结构与算法分析-C语言描述>>, 作者Allen Weiss **************************************************

二叉树学习笔记之经典平衡二叉树（AVL树）

二叉查找树(BSTree)中进行查找.插入和删除操作的时间复杂度都是O(h),其中h为树的高度.BST的高度直接影响到操作实现的性能,最坏情况下,二叉查找树会退化成一个单链表,比如插入的节点序列本身就有序,这时候性能会下降到O(n).可见在树的规模固定的前提下,BST的高度越低越好. 平衡二叉树平衡二叉树是计算机科学中的一类改进的二叉查找树. 平衡二叉树具有以下性质: (1)一棵空树是平衡二叉树 (2)如果树不为空,它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树.

AVL树的研究

3 实现算法 3.1 数据结构 template<typename T>struct BSTNode//平衡二叉树的结点类型结构体 { T data;//结点数据类型 int bf;//结点的平衡因子,比二叉链表结点多此项 BSTNode<T>*lchild,*rchild;//左右孩子指针 }; 3.2 算法 3.2．1 递归法递归实现AVL树的节点删除的思想如下. 在AVL树T上删除值为E的节点步骤如下: (1)

AVL树的删除探讨

AVL树的删除很多教材上都没有提供,本人对AVL树有着较为深入的研究.现在晒出大体的算法思想. 3.2．1 递归法递归实现AVL树的结点删除的思想如下. 在AVL树T上删除值为E的结点步骤如下: (1) 若树T为空,返回0退出否则到(2); (2) 比较T的数据和E,若相等跳到(3),若E小于T->data跳到(4),若E大于T->data则跳到(5) (3) 分析T结点的类型 (3.1)若T是叶子结点则直接删除,树变矮即lower=1: (3.2

Python数据结构——AVL树的实现

既然,我们已经证明,保持 AVL 树的平衡将会使性能得到很大的提升,那我们看看如何在程序中向树插入一个新的键值.因为所有的新键是作为叶节点插入树的,而新叶子的平衡因子为零,所以我们对新插入的节点不作调整.不过一旦有新叶子的插入我们必须更新其父节点的平衡因子.新叶子会如何影响父节点的平衡因子取决于叶节点是左子节点还是右子节点.如果新节点是右子节点,父节点的平衡因子减 1.如果新节点是左子节点,父节点的平衡因子将加 1.这种关系可以递归地应用于新节点的前两个节点,并有可能影响到之前的每一个甚至是根节

纸上谈兵: AVL树[转]

二叉搜索树的深度与搜索效率我们在树, 二叉树, 二叉搜索树中提到,一个有n个节点的二叉树,它的最小深度为log(n),最大深度为n.比如下面两个二叉树: 深度为n的二叉树深度为log(n)的二叉树这两个二叉树同时也是二叉搜索树(参考树, 二叉树, 二叉搜索树).注意,log以2为基底.log(n)是指深度的量级.根据我们对深度的定义,精确的最小深度为floor(log(n)+1). 我们将处于同一深度的节点归为一层.如果除最后一层外的其他层都被节点填满时,二叉树有最小深度log(n). 二

AVL树双旋转疑问

问题描述近日在学习AVL树的旋转,尤其是双旋转处有些模糊不清,在MarkAllenWeiss的数据结构与算法分析--C语言描述这本书里面看到,感觉书中的双旋转例程有错误,如下图:这里面的代码显示先右旋,然后左旋,可是注释里面写着是Left-right双旋转,难道不是先左旋,后右旋吗?好像先左旋,后右旋才是正确的做法.请各位指点一下!谢谢.

AVL树删除算法的实现--长安大学毕业设计

AVL树的删除算法的两种实现方法本文是本人原创,当时作为长安大学高一凡老师带的学生,我的毕业设计就是做一个AVL 算法的演示软件.其中,AVL树的删除算法在度娘和谷歌了很久都没有找到逻辑通畅或者说是我能够看懂的.后来,闭门造成,费了十几张A4纸才把算法设计出来.实现之后得到了老师的认同.非常的开心.之前我骗了大家,用网络上能搜到的算法来敷衍大家,一直觉得我的努力成果,不能让别人剽窃.但是,这么多年过去了.我觉得,我要和CSDN上其他码农一样,需要具有分享精神.... 本文是当时我想投稿的一个

数据结构之AVL树

树的平衡,我们已经知道DWL算法,不过DWL算法需要从整体上平衡树,但是树的平衡也可以局部的进行,由Adel'son-Vel'skii-Landis提出了一种经典方法,称为AVL树. 1.概念:AVL树,或者说可适应树,是指树中每个节点的的平衡因子的绝对值不大于1,即只能为-1,0,1 平衡因子:节点的右子树的高度减去左子树的高度 2.AVL树的插入:从新插入节点到根的路径上,修改遇到的节点的平衡因子即可,对其他部分没影响 1)向右子女的右子树插入一个节点,单旋转就可以 2)向右子女的左子树插入