链接列表:
项目(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和二进制搜索树之间的区别
发布评论