二分搜索树的创建问题

Question

如果把一个基本有序的数列添加进一个二分搜索树从而创建这个树，那么会导致树的结构严重倒向一边(如图）。想问这种情况怎么创建二分搜索树？

    1
      \
       2
        \
         3
          \
           4

Answer 1

liuyubobobo 2017-03-26 23:03:37

非常好的问题，这就是普通的二分搜索树的缺点。对于这种情况，就需要使用平衡二叉树了。使用最多的平衡二叉树是红黑树。由于我们这个课程的限制，没有深入讲解红黑树。在课程的5-10和5-11两小节，我简单介绍了一些和二叉树相关的更多扩展。有兴趣的话，可以通过互联网或者其他书籍自学一下。有机会，我会在更高级的算法课程中向大家介绍：）

• 提问者 Wish大人 #1

  非常感谢！