AVL树和红黑树，哪个更平衡？解决方法
AVL树和红黑树，哪个更平衡？
高度为h的二叉树，
最不平衡的情况相当于链表，有 h+1 个节点。
最平衡的情况是完全二叉树，有 2^(h+1)-1 个节点。
任意一棵高位h的二叉树，节点数都在这两者之间，节点数越多越平衡。
高度为h的AVL树，最少有多少个节点？
高度为h的红黑树，最少有多少个节点？
------解决方案--------------------
红黑树更给力些吧，一般说来是这样的
------解决方案--------------------
从定义就可以知道AVL树更平衡，不过这种平衡是有代价的。
------解决方案--------------------
据说红黑树有较好的统计性能，那么体现在什么地方呢？求高手解答
------解决方案--------------------
性能好都是有针对性的，主要看你需要什么功能，如果你需要大量的插入、删除、查找，红黑树的平均效果还是不错的，如果数据都是固定的，主要操作是查找，那么AVL效果更好，而且还存在更有针对性的最优二叉查找树。如果你的查找方式都是Key Value的方式，Hash表的效果更好。如果包含大量的集合合并操作，就要考虑用那些堆的数据结构了。
------解决方案--------------------
哦，我是看了标题近来的，avl树更平衡吧，红黑树整体统计性能好些，用红黑树的规则，相对于avl树来说，减弱了平衡性的要求
------解决方案--------------------
AVL
------解决方案--------------------
AVL树理解起来教容易，对于红黑树，感觉那些规则，需要很强的数学推理能力才能理解透，反正我看红黑树是头疼的，呵呵
------解决方案--------------------
红黑树是改进后的AVL树，更平衡
误导！
------解决方案--------------------
AVL树更平衡，但平衡和效率是两回事，论平均效率，红黑树比较高
------解决方案--------------------
觉得红黑树更好一些
------解决方案--------------------
一个插入不给力，一个删除不给力。
如果都是用来查找，效率是差不多的。
------解决方案--------------------
------解决方案--------------------
学习了
------解决方案--------------------
单说平衡的话，绝对是AVL。如果只是查找而不增删结点，也是AVL。
问题就在于树结构的改动效率上：如果改变了树结构（增删结点），AVL需要更多的操作才能恢复树的原有秩序（所谓的“平衡是有代价的”）。
暂把树的操作分两类：静态操作——单纯的查询，不改动树结构；动态操作——需要增删结点，就是对树结构有改动。AVL的静态操作效率高，比如先建立一颗树只为查询数据，AVL比红黑好。而在单次动态操作中，红黑树要比AVL快，比如插入数据后需要对树进行调整使其恢复原有秩序，红黑树的调整不超过3次，AVL就不一定了。
AVL的静态得分高，红黑树的动态得分高。单纯查询，AVL优于红黑树；查询但偶尔修改，两者可能不分高下，AVL的效率随修改频率的增加而降低；持续的频繁修改——选红黑吧。
------解决方案--------------------
------解决方案--------------------
从理论上将AVL树要平衡一些，但是平衡的代价太高；相比起来，红黑树的代价很低，但是能做到基本的平衡。所以工业上一般选用红黑树，而不用AVL。Linux下就用很多地方都用到了红黑树。
高度为h的二叉树，
最不平衡的情况相当于链表，有 h+1 个节点。
最平衡的情况是完全二叉树，有 2^(h+1)-1 个节点。
任意一棵高位h的二叉树，节点数都在这两者之间，节点数越多越平衡。
高度为h的AVL树，最少有多少个节点？
高度为h的红黑树，最少有多少个节点？
------解决方案--------------------
红黑树更给力些吧，一般说来是这样的
------解决方案--------------------
从定义就可以知道AVL树更平衡，不过这种平衡是有代价的。
------解决方案--------------------
据说红黑树有较好的统计性能，那么体现在什么地方呢？求高手解答
------解决方案--------------------
性能好都是有针对性的，主要看你需要什么功能，如果你需要大量的插入、删除、查找，红黑树的平均效果还是不错的，如果数据都是固定的，主要操作是查找，那么AVL效果更好，而且还存在更有针对性的最优二叉查找树。如果你的查找方式都是Key Value的方式，Hash表的效果更好。如果包含大量的集合合并操作，就要考虑用那些堆的数据结构了。
------解决方案--------------------
哦，我是看了标题近来的，avl树更平衡吧，红黑树整体统计性能好些，用红黑树的规则，相对于avl树来说，减弱了平衡性的要求
------解决方案--------------------
AVL
------解决方案--------------------
AVL树理解起来教容易，对于红黑树，感觉那些规则，需要很强的数学推理能力才能理解透，反正我看红黑树是头疼的，呵呵
------解决方案--------------------
红黑树是改进后的AVL树，更平衡
误导！
------解决方案--------------------
AVL树更平衡，但平衡和效率是两回事，论平均效率，红黑树比较高
------解决方案--------------------
觉得红黑树更好一些
------解决方案--------------------
一个插入不给力，一个删除不给力。
如果都是用来查找，效率是差不多的。
------解决方案--------------------
------解决方案--------------------
学习了
------解决方案--------------------
单说平衡的话，绝对是AVL。如果只是查找而不增删结点，也是AVL。
问题就在于树结构的改动效率上：如果改变了树结构（增删结点），AVL需要更多的操作才能恢复树的原有秩序（所谓的“平衡是有代价的”）。
暂把树的操作分两类：静态操作——单纯的查询，不改动树结构；动态操作——需要增删结点，就是对树结构有改动。AVL的静态操作效率高，比如先建立一颗树只为查询数据，AVL比红黑好。而在单次动态操作中，红黑树要比AVL快，比如插入数据后需要对树进行调整使其恢复原有秩序，红黑树的调整不超过3次，AVL就不一定了。
AVL的静态得分高，红黑树的动态得分高。单纯查询，AVL优于红黑树；查询但偶尔修改，两者可能不分高下，AVL的效率随修改频率的增加而降低；持续的频繁修改——选红黑吧。
------解决方案--------------------
------解决方案--------------------
从理论上将AVL树要平衡一些，但是平衡的代价太高；相比起来，红黑树的代价很低，但是能做到基本的平衡。所以工业上一般选用红黑树，而不用AVL。Linux下就用很多地方都用到了红黑树。