LinkedList和二进制搜索树之间的区别 [英] Difference between a LinkedList and a Binary Search Tree

问题描述

链接列表和BinarySearchTree之间的主要区别是什么？ BST是一种维护LinkedList的方法吗？我的教练谈到了LinkedList和BST，但没有比较他们，或者没有说什么时候更喜欢一个。这可能是一个愚蠢的问题，但我真的很困惑。

解决方案

链接列表：

 项目（1） - >项目（2） - > Item（3） - >项目（4） - >项目（5） - >项目（6） - >项目（7）
  

二叉树：

 节点（1）
 / 
节点（2）
 / \ 
 / Node（3）
 RootNode ）
 \ Node（5）
 \ / 
节点（6）
 \ 
节点（7）
  

在链表中，这些项目通过单个下一个指针链接在一起。
在二进制树中，每个节点可以具有0,1或2个子节点，其中（在二叉搜索树的情况下），左节点的密钥小于节点的密钥和右侧的密钥节点多于节点。只要树平衡，每个项目的搜索路径比链接列表中的搜索路径短得多。

搜索路径：

  ------ ------ ------ 
键列表树
 ------ ------ ------ 
 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树
 ------ ------ ------ 
 1 1 1 
 3 2 1.67 
 7 4 2.43 
 15 8 3.29 
 31 16 4.16 
 63 32 5.09 
 ------ ------ ------ 
  

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.

解决方案

Linked List:

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

Binary tree:

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

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.

Searchpaths:

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

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