平衡因子(Balance Factor：简称BF)：BF(T) = hL - hR，hL和hR分别为T的左右子树高度
平衡二叉树(Balance Binary Tree)(AVL树)：
空树
或者任一结点，左右子树高度差的绝对值，不超过1，即|BF(T)|<=1
查找时间复杂度：
设nh为高度h的平衡二叉树的最小结点数，则nh = n(h-1)+n(h-2)+1，nh = F(h+2) - 1(h > 0)
推算出：h = O(logn)
平衡二叉树的调整：
右单旋：麻烦结点在发现者右子树的右边，因而叫RR插入，需要RR旋转，即右单旋。
左单旋：麻烦结点在发现者左子树的左边，因而叫LL插入，需要LL旋转，即左单旋。
LR旋转：麻烦结点在发现者左子树的右边
RL旋转：麻烦结点在发现者右子树的左边
数据结构学习笔记：树与树的表示、二叉树及其遍历、二叉搜索树、平衡二叉树、堆、哈夫曼树、集合及其运算算法学习笔记浅谈...
数组 链表 堆/栈/队列 树 数据结构 - 二叉树数据结构 - 二叉查找树数据结构 - 平衡二叉树数据结构 - A...
定义： 平衡二叉树（Balanced Binary Tree），这个性质，在数据结构的发展中出现了几种平衡二叉树。...
93. 平衡二叉树 描述 笔记 数据 评测 给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树...
数据结构 二叉树 完全二叉树 平衡二叉树 二叉查找树（BST） 红黑树 B-，B+，B*树 LSM 树 队列 集合...
数据结构队列集合链表、数组字典、关联数组栈树二叉树完全二叉树平衡二叉树二叉查找树（BST）红黑树B-，B+，B*树...
数据结构队列集合链表、数组字典、关联数组栈树二叉树完全二叉树平衡二叉树二叉查找树（BST）红黑树B-，B+，B*树...
前言 本文章主要说明，相比较B树和平衡二叉树，B+树作为数据库的索引的数据结构优势在哪 平衡二叉树的劣势 数据库作...
_ 跳表是一种可以替代平衡树的数据结构。跳表追求的是概率性平衡，而不是严格平衡。因此，跟平衡二叉树相比，跳表的插入...
二叉树 ：有左右之分，次序不能颠倒 完全二叉树是一种效率很高的数据结构，二叉排序树要借助平衡性来实现，而平衡性基于...
本文标题：数据结构笔记（树->平衡二叉树）
本文链接：https://www.haomeiwen.com/subject/saiicktx.html
网友评论