AVL树-scala实现
二叉查找树已经能够很好的应用到应用程序中,但它们在最坏的情况下性能还是很糟糕。考虑到如图所示这种情况: 查找操作的性能完全等同于线性。而AVL树的查找操作,能够保证无论怎么构造它,运行时间一直对数级别的。一起来学习一下AVL树吧。什么是AVLAVL(Adelson-Velsky 和 Landis)树,是带有平衡条件的二叉查找树,这个平衡条件必须要容易保持,并且它保证树的深度是O(LogN).一颗AVL树是其每个节点的左右子树节点高度最多差1的二叉查找树。平...