链表和二叉搜索树的区别 [英] Difference between a LinkedList and a Binary Search Tree

问题描述

链表和二叉搜索树的主要区别是什么?BST 只是维护 LinkedList 的一种方式吗?我的导师谈到了 LinkedList 和 BST，但没有比较它们，也没有说明何时更喜欢一个而不是另一个.这可能是一个愚蠢的问题，但我真的很困惑.如果有人能以简单的方式澄清这一点，我将不胜感激.

What are the main differences between a Linked List and a BinarySearchTree? Is BST just a way of maintaining a LinkedList? My instructor talked about LinkedList and then BST but did't compare them or didn't say when to prefer one over another. This is probably a dumb question but I'm really confused. I would appreciate if someone can clarify this in a simple manner.

推荐答案

链表:

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 个子节点，其中(在二叉搜索树的情况下)左节点的键小于节点的键，右节点的键大于节点.只要树是平衡的，到每一项的搜索路径就比链表短很多.

In a linked list, the items are linked together through a single next pointer. In a binary tree, each node can have 0, 1 or 2 subnodes, where (in case of a binary search tree) the key of the left node is lesser than the key of the node and the key of the right node is more than the node. As long as the tree is balanced, the searchpath to each item is a lot shorter than that in a linked list.

搜索路径:

------ ------ ------
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
------ ------ ------

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

By larger structures the average search path becomes significant smaller:

------ ------ ------
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
------ ------ ------

这篇关于链表和二叉搜索树的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！