查找:二分查找
思想
二分查找的思想很常见也很简单,使用分治思想从左边(中间元素大于目标元素)或者从右边(中间元素小于目标元素)查找元素。在一个顺序表中查找等于X的元素的index,从中间元素开始匹配,如果等于则直接返回,如果小于目标元素,则向左边区间查找,如果大于目标元素则向右边查找。
二分查找的思想很常见也很简单,使用分治思想从左边(中间元素大于目标元素)或者从右边(中间元素小于目标元素)查找元素。在一个顺序表中查找等于X的元素的index,从中间元素开始匹配,如果等于则直接返回,如果小于目标元素,则向左边区间查找,如果大于目标元素则向右边查找。
平衡二叉树的严格定义是这样的:二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看,上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树,但是非完全二叉树也有可能是平衡二叉树。
平衡二叉查找树不仅满足上面平衡二叉树的定义,还满足二叉查找树的特点。发明平衡二叉查找树这类数据结构的初衷是,解决普通二叉查找树在频繁的插入、删除等动态更新的情况下,出现时间复杂度退化的问题。
所以,平衡二叉查找树中“平衡”的意思,其实就是让整棵树左右看起来比较“对称”、比较“平衡”,不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些,相应的插入、删除、查找等操作的效率高一些。
常见的平衡二叉查找树有:AVL树、Splay Tree(伸展树)、Treap(树堆)和红黑树等等。使用最广泛的是红黑树,从linux内核到jdk的HashMap等等都被广泛使用到。
树(Tree) 是一种非线性的分层数据结构,由节点(Node)和边(Edge)组成,满足以下条件:
叶节点(Leaf):没有子节点的节点
子树(Subtree):以某节点为根,包含其所有后代节点的子结构
度(Degree):节点的子节点数量;树的度为所有节点度的最大值。
节点的高度(height):当前节点大到叶子节点的最长路径(边的数量)
节点的深度(depth):根节点到当前节点的的边的数量
层级(level):节点的深度 + 1
树高度:从根到最远叶节点的最长路径边数,根节点的高度,树高 = 节点高度 + 节点深度
我们把时间复杂度为O(n)的排序算法称为线性排序。之所以能做到线性的时间复杂度,主要原因是,这样的算法是并非基于比较的排序算法,都不涉及元素之间的比较操作。但是如此高效是有代价的,线性排序的适用场景十分有限,条件苛刻。