0

我试图理解什么是排序树，二叉树和 avl 和 and ......我仍然不确定，是什么让排序树排序？在排序的树中搜索和在未排序的树中搜索之间的复杂性（Big-Oh）是多少？希望您能够帮助我。

4

5 回答 5

5

二叉树

存在两种主要类型的二叉树，平衡的和不平衡的。平衡树旨在尽可能保持树的高度（高度 = 根与最远的子节点之间的节点数量）。平衡树有几种类型的算法，其中最著名的两种是 AVL- 和 RedBlack-trees。AVL 和 RedBlack 树上的插入/删除/搜索操作的复杂性是O(log n)或更好- 这是重要的部分。其他自平衡算法是 AA-、Splay- 和 Scapegoat-tree。

平衡树获得了平衡的属性（和名称），因为在树上的每次删除或插入操作之后，算法都会对树进行内省以确保它仍然是平衡的，如果不是，它将尝试修复这个问题（完成不同的算法）通过在树中旋转节点。

正常（或不平衡）二叉树不会修改其结构以保持自身平衡，并且通常会加班，变得非常低效（特别是如果按顺序插入值）。但是，如果性能没有问题并且您主要想要一个排序的数据结构，那么他们可能会这样做。在不平衡树上插入/删除/搜索操作的复杂性范围从 O(1)（最好的情况 - 如果你想要根）到 O(n)（最坏的情况，如果你按顺序插入所有节点并想要最大的节点)

存在另一种称为随机二叉树的变体，它使用某种随机化来确保树不会变得完全不平衡（与链表相同）

于 2009-05-31T09:53:00.627 回答
2

二叉搜索树是一种“树”结构，其中每个节点都有两个子节点。
左节点都具有小于其父节点的属性，而右节点都大于其父节点。

二叉树的有趣之处在于，当树正确排序时，我们可以在 O(log n) 中搜索一个值。例如，在 LinkedList 中进行相同的搜索将为我们提供 O(n) 的搜索速度。

学习数据结构的最好方法是花一天时间搜索和阅读维基百科文章。
这可能会让你开始
http://en.wikipedia.org/wiki/Binary_search_tree

于 2009-05-31T09:37:56.400 回答
1

谷歌搜索以下内容：

site:stackoverflow.com binary trees

获取 SO 问题列表，这些问题将回答您的几个问题。

于 2009-05-31T09:33:55.393 回答
0

如果树结构没有以某种方式排序，那么使用树结构并没有多大意义——如果您计划在树中搜索一个节点并且它是未排序的，那么您将不得不遍历整个树（在））。如果你有一棵以某种方式排序的树，那么只需要遍历树的一个分支（通常为 O(log n)）。

于 2009-05-31T09:36:40.287 回答
0

在二叉树中，右叶总是比头小，左叶总是大，所以你可以在 O(log(n)) 中搜索排序树，如果 key 小于你只需要向右走如果 bgger 向左移动

于 2009-05-31T09:37:02.500 回答