Af14caef947747050aa75dd9bbd580b3
数据结构与算法——心中有“树”

1 二叉树基础
2 二叉搜索树
3 平衡二叉树
4 2-3树
5 2-3-4树
6 红黑树
7 B树
8 B+树
9 霍夫曼树

1 性能分析

1.1 二叉搜索树 链接

  定义:二叉搜索树又称二叉查找树,亦称为二叉排序树。设x为二叉查找树中的一个节点,x节点包含关键字key,节点x的key值记为key[x]。如果y是x的左子树中的一个节点,则key[y] <= key[x];如果y是x的右子树的一个节点,则key[y] >= key[x]。
查找性能
  当数据数目为N,树高度保持logN附近。则平均查找长度与logN成正比,查找平均时间复杂度为O(logN)。 当先后插入的关键字有序时,二叉搜索树退化成单支树结构。此时树高N。平均查找长度为(N+1)/2,查找的平均时间复杂度为O(N)。
插入性能
  插入效率与查找效率一致。
删除性能
  删除节点时,若节点为叶子节点,或者节点只有单一子树,则时间复杂度为O(1)。若节点既有左子树又有右子树,则需要执行递归过程,对应时间复杂度为O(logN)。

1.2 平衡二叉树 链接

  平衡二叉树是一种特殊的二叉搜索树。平衡二叉树保证节点平衡因子的绝对值不超过1,保证了树的平衡。
查找性能
  平衡二叉树是严格平衡的,那么查找过程与二叉搜索树一样,只是平衡二叉树不会出现最差的单支树情形。因此查找效率最好,最坏情况时间复杂度为O(logN)。
插入性能
  插入数据之前需要进行查找操作,查找到插入位置。插入数据后需要进行旋转操作,旋转操作复杂度为常量级。因此插入数据的时间复杂度与查找相同为O(logN)。
删除性能
  删除数据同样需要查找数据,在删除数据后需要进行调整。一次删除最多需要需要O(logN)次旋转,因此删除数据的时间复杂度为O(logN)+O(logN)=O(2logN)。

1.3 红黑树 链接

  平衡二叉树的严格平衡策略以牺牲建立查找结构(插入,删除操作)的代价,换来了稳定的O(logN) 的查找时间复杂度。红黑树采用了折中策略,即不牺牲太大的建立查找结构的代价,同时又能保证稳定高效的查找效率。

查找性能
  由于红黑树的性质(最长路径长度不超过最短路径长度的2倍),可以说明红黑树虽然不像平衡二叉树一样是严格平衡的,但平衡性能还是要比二叉搜索树要好。其查找代价基本维持在O(logN)左右,但在最差情况下(最长路径是最短路径的2倍少1),比平衡二叉树效率低一些。
插入性能
  红黑树插入结点时,需要旋转操作和变色操作。但由于只需要保证红黑树基本平衡就可以了。因此插入结点最多只需要2次旋转,这一点和平衡二叉树的插入操作一样,但是变色操作的时间复杂度为O(logN)。
删除性能
  红黑树的删除操作代价要比平衡二叉树要好的多,删除一个结点最多只需要3次旋转操作,保证了删除时间复杂度维持在常量级。

top Created with Sketch.