And*_*dre 0 sorting tree binary-tree
我试图理解排序树是什么,二叉树和avl和和......我还是不确定,是什么使排序树排序？在排序中搜索和在未排序树中搜索之间的复杂性(Big-Oh)是多少？希望您能够帮助我.
存在两种主要类型的二叉树,平衡和不平衡.平衡树旨在尽可能保持树的高度(高度=根与最远的孩子之间的节点数量).平衡树有几种类型的算法,最着名的两种算法是AVL和RedBlack树.AVL和RedBlack树上的插入/删除/搜索操作的复杂性是O(log n)或更好 - 这是重要的部分.其他自平衡算法是AA-,Splay-和Scapegoat-tree.
平衡树获得其平衡的属性(和名称),因为在树上的每次删除或插入操作之后,算法会对树进行内省以确保它仍然是平衡的,如果它不是它将尝试修复它(这是完成的)与每种算法不同)通过旋转树中的节点.
正常(或不平衡)二叉树不会修改它们的结构以保持自身平衡,并且有可能(通常是超时)变得非常低效(特别是如果按顺序插入值).但是,如果性能没有问题,并且您主要想要一个排序的数据结构,那么他们可能会这样做.在非平衡树上插入/删除/搜索操作的复杂性范围从O(1)(最好的情况 - 如果你想要根)到O(n)(如果按顺序插入所有节点并想要最大节点,则最坏情况) )
存在另一种变体,称为随机二叉树,它使用某种随机化来确保树不会完全不平衡(这与链表相同)