数据结构与算法之二三树【料视出品】

二叉搜索树在最好的情况下搜索的时间复杂度为O(logn)，但如果插入节点时，插入元素序列本身就是有序的，那么BST树就退化成一个线性表了，搜索的时间复杂度为O(n)。
  如果想要减少比较次数，就需要降低树的高度。在插入和删除节点时，要保证插入节点后不能使叶子节点之间的深度之差大于1，这样就能保证整棵树的深度最小，这就是AVL树解决BST搜索性能降低的策略。但由于每次插入或删除节点后，都可能会破坏AVL的平衡，而要动态保证AVL的平衡需要很多操作，这些操作会影响整个数据结构的性能，除非是在树的结构变化特别少的情形下，否则AVL树平衡带来的搜索性能提升有可能还不足为了平衡树所带来的性能损耗。
  因此，引入了2-3树来提升效率。2-3树本质也是一种平衡搜索树，但2-3树已经不是一棵二叉树了，因为2-3树允许存在3这种节点，3-节点中可以存放两个元素，并且可以有三个子节点。

内容版权声明：除非注明，否则皆为本站转载文章。文章及图片版权归原作者所有，如有侵权请联系我们，我们立刻删除。