data-structures - 链表和二叉搜索树的区别

Question

链表和二叉搜索树之间的主要区别是什么？ BST只是维护LinkedList的一种方式吗？我的老师先讨论了 LinkedList，然后讨论了 BST，但没有对它们进行比较，也没有说何时更喜欢其中一种。这可能是一个愚蠢的问题，但我真的很困惑。如果有人能以简单的方式澄清这一点，我将不胜感激。

Answer 1

链接列表:

Item(1) -> Item(2) -> Item(3) -> Item(4) -> Item(5) -> Item(6) -> Item(7)

二叉树:

                 Node(1)
                /
            Node(2)
           /    \
          /      Node(3)
  RootNode(4)
          \      Node(5)
           \    /
            Node(6)
                \
                 Node(7)

在链表中，项目通过单个下一个指针链接在一起。在二叉树中，每个节点可以有 0、1 或 2 个子节点，其中(在二叉搜索树的情况下)左节点的键小于该节点的键，右节点的键大于节点。只要树是平衡的，每个项目的搜索路径就会比链表中的搜索路径短得多。

搜索路径:

------ ------ ------
key    List   Tree
------ ------ ------
1      1      3
2      2      2
3      3      3
4      4      1
5      5      3
6      6      2
7      7      3
------ ------ ------
avg    4      2.43
------ ------ ------

通过较大的结构，平均搜索路径会变得更小:

------ ------ ------
items  List   Tree
------ ------ ------
     1      1   1
     3      2   1.67
     7      4   2.43
    15      8   3.29
    31     16   4.16
    63     32   5.09
------ ------ ------