自平衡二叉树
普通的二叉查找树（BST）虽然已经实现了对于节点的快速查找，但是如果树的拓扑结构没有设计正确，例如将一个有序序列存入BST中，就会使BST的二分查找能力损失，也就是常说的失去了平衡。为了保证BST的查找能力，在BST形成过程中进行平衡调整，就形成了平衡二叉查找树，简称平衡二叉树（AVL-tree）。
普通的二叉查找树（BST）虽然已经实现了对于节点的快速查找，但是如果树的拓扑结构没有设计正确，例如将一个有序序列存入BST中，就会使BST的二分查找能力损失，也就是常说的失去了平衡。为了保证BST的查找能力，在BST形成过程中进行平衡调整，就形成了平衡二叉查找树，简称平衡二叉树（AVL-tree）。
二叉查找树（Binary Search Tree，BST）是一种特殊的二叉树，BST通过定义节点的左孩子和右孩子的约定关系，提升了二叉树节点的搜索效率。
二叉树（Binary Tree）是指树中的所有节点的度都不大于2的树，也就是说，二叉树中的所有节点最多只有2个子节点。二叉树的每个节点有左树和右树之分，而节点的左树和右树同样也是二叉树。