20120920-AVL树定义《数据结构与算法分析》

水深无声 2022-01-15 01:49 159阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

AVL树节点声明：

1 struct AvlNode 2 { 3 Comparable element; 4     AvlNode *left; 5     AvlNode  *right; 6     int height; 7 
    8     AvlNode( const Comparable & theElement,AvlNode *lt,AvlNode *rt,int h=0):element ( theElement),left(lt),right(rt),height(t) 9 };

计算节点高度：

1 int height( AvlNode * t) const
    2 { 3     return t == NULL ? -1 : t->height; 4 }

向AVL中插入操作：

void insert( const Comparable & x,AvlNode * & t) { if(t == NULL) t = new AvlNode ( x,NULL,NULL); else if (x < t->element); { insert( x ,t->left); if(height(t->left)-height(t->right) == 2) if(x < t->element) rotateWithLeftChild(t); else doubleWithLeftChild(t); } else if (t->element < x) { insert(x,t->right); if(height(t->right) - height(t->left) == 2) if(t->right->element < x) rotateWithLeftChild(t); else doubleWithLeftChild(t); } else ; t->height = max(height(t->left),height(t->right))+1; }

执行单旋转过程：

1 void rotateWithLeftChild(AvlNode * & k2) 2 { 3     AvlNode *k1 = k2->left; 4     k2->left = k1->right; 5     k1->right = k2; 6     k2->height = max(height(k2->left),height(k2->right))+1; 7     k1->height = max(height(k1->left),height(k1->right))+1; 8     k2=k1; 9 }

执行双旋转过程：

void doubleWithLeftChild( AvlNode * & k3) { rotateWithLeftChild(k3->left); rotateWithLeftChild(k3); }

转载于:https://my.oschina.net/u/204616/blog/545511

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/6fb552be38c246fa9b3a1e545aead8e5.png

发表评论取消回复

表情：

评论列表（有 0 条评论，159人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构与算法之树（三）AVL树

*数据结构与算法之树** [数据结构与算法之树（一）二叉树概念及遍历方式（图文并茂）][Link 1] [数据结构与算法之树（二）二叉查找树][Link 2] [数...

柔情只为你懂/ 2024年04月19日 12:35/ 0 赞/ 83 阅读

相关【数据结构与算法之树结构】二叉排序树与AVL树

【数据结构与算法之树结构】二叉排序树与AVL树文章目录【数据结构与算法之树结构】二叉排序树与AVL树二叉排序树也称为二叉查找树。它或者

冷不防/ 2024年03月25日 14:12/ 0 赞/ 94 阅读

相关数据结构与算法简记：AVL树

前面记录了二叉查找树，它在搜索方面的效率显而易见，可它也存在某种缺陷，假设我们连续插入较小或较大的数据，那么二叉查找树将会逐渐退变为一个线性结构，从而搜索就变为了线性查找，效率

骑猪看日落/ 2022年07月19日 05:21/ 0 赞/ 178 阅读

相关 Java数据结构与算法解析(六)——AVL树

Java数据结构与算法解析(六)——AVL树之前我们说过普通二叉查找树的删除算法会使得左子树比右子树深，因为我们总是

末蓝、/ 2022年05月29日 06:13/ 0 赞/ 192 阅读

相关数据结构与算法-平衡二叉树（AVL树）-思想篇

概要基本概念实现原理图示平衡二叉树构建过程思想总结基本概念 >

叁歲伎倆/ 2022年04月10日 13:46/ 0 赞/ 250 阅读

相关 AVL树和伸展树-二叉树-数据结构与算法

1. AVL树(高度平衡树) AVL树是高度平衡的二叉树。它的特点是：树中任何节点的两个子树的高度最大差别为1 ![在这里插入图片描述][waterm

迈不过友情╰/ 2022年02月18日 19:41/ 0 赞/ 241 阅读

相关数据结构之AVL树

AVL树相关学习与实现：简介 AVL树是最早被发明的`自平衡二叉查找树`。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入

红太狼/ 2022年01月27日 08:05/ 0 赞/ 260 阅读

相关数据结构之「AVL树」

前言二叉搜索树在一般情况下它的查找时间复杂度是 O(log n)。但在一些特殊的情况下，它会退化为斜树变成线性结构，导致查询效率大大降低，根本发挥不出折半查找的优势。因

你的名字/ 2022年01月20日 08:43/ 0 赞/ 236 阅读

相关 20120920-AVL树定义《数据结构与算法分析》

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] AVL树节点声明： 1 struct AvlN

水深无声/ 2022年01月15日 01:49/ 0 赞/ 160 阅读

相关数据结构与算法(九)：AVL树详细讲解

[数据结构与算法(一):基础简介][Link 1] [数据结构与算法(二):基于数组的实现ArrayList源码彻底分析][ArrayList] [数据结构与算法(三

深碍√TFBOYSˉ_/ 2021年09月29日 14:30/ 0 赞/ 274 阅读