二叉查找树

二叉查找树也有一些缺陷。例如，二叉查找树只有在满员(或平衡)时效率最高。不平衡的数查找并不比链表快。

避免串状树的方法之一是在创建树时多加注意。如果树或子树的一边或 另一边太不平衡，就需要重新排列节点使之恢复平衡

与此类似，可能在进行删除操作后要重新排列树。俄国数学家Adel’son-Vel’skii和Landis发明了一 种算法来解决这个问题。根据他们的算法创建的树称为AVL树。因为要重 构，所以创建一个平衡的树所花费的时间更多，但是这样的树可以确保最大 化搜索效率。