数据结构之AVL树

树的平衡，我们已经知道DWL算法，不过DWL算法需要从整体上平衡树，但是树的平衡也可以局部的进行，由Adel'son-Vel'skii-Landis提出了一种经典方法，称为AVL树。

1。概念：AVL树，或者说可适应树，是指树中每个节点的的平衡因子的绝对值不大于1，即只能为-1，0，1
平衡因子：节点的右子树的高度减去左子树的高度

2。AVL树的插入：从新插入节点到根的路径上，修改遇到的节点的平衡因子即可，对其他部分没影响
1）向右子女的右子树插入一个节点，单旋转就可以
2）向右子女的左子树插入一个节点，双旋转，先围绕父节点，再围绕祖父节点

3。AVL树的删除：从删除节点到根的路径上，任何不平衡因子的节点都需要修改，与插入不同，需要O(lgn)次旋转。

4。一个java实现：
http://www.koders.com/java/fid3B5247D34968077A6EFD4216589026D343559FF9.aspx?s=avl%2Btree

文章转自庄周梦蝶，原文发布时间5.17

时间： 2024-08-01 03:56:20

数据结构之AVL树的相关文章

数据结构之AVL树详解_C 语言

1. 概述 AVL树是最早提出的自平衡二叉树,在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树.AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis.AVL树种查找.插入和删除在平均和最坏情况下都是O(log n),增加和删除可能需要通过一次或多次树旋转来重新平衡这个树.本文介绍了AVL树的设计思想和基本操作. 2. 基本术语有四种种情况可能导致二叉查找树不平衡,分别为: (1)LL:插入一个新节点到根节点的左子树(Left)的左子树

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

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

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树[转]

二叉搜索树的深度与搜索效率我们在树, 二叉树, 二叉搜索树中提到,一个有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上其他码农一样,需要具有分享精神.... 本文是当时我想投稿的一个

数据结构之伸展树详解_C 语言

1. 概述二叉查找树(Binary Search Tree,也叫二叉排序树,即Binary Sort Tree)能够支持多种动态集合操作,它可以用来表示有序集合.建立索引等,因而在实际应用中,二叉排序树是一种非常重要的数据结构. 从算法复杂度角度考虑,我们知道,作用于二叉查找树上的基本操作(如查找,插入等)的时间复杂度与树的高度成正比.对一个含n个节点的完全二叉树,这些操作的最坏情况运行时间为O(log n).但如果因为频繁的删除和插入操作,导致树退化成一个n个节点的线性链(此时即为一个单链表