数据结构基本概念

1、B+Tree/Hash_Map/STL Map三种数据结构的优势:

      Hash操作能根据散列值直接定位数据的存储地址,设计良好的hash表能在常数级时间下找到需要的数据,但是更适合于内存中的查找。
      B+树是一种是一种树状的数据结构,适合做索引,对磁盘数据来说,索引查找是比较高效的
      STL_Map的内部实现是一颗红黑树,但是只是一颗在内存中建立二叉树树,不能用于磁盘操作,而其内存查找性能也比不上Hash查找。
      因此对于内存中数据,查找性能较好的数据结构是Hash_Map,对于磁盘中数据,查找性能较好的数据结构是B+Tree。

2、最大堆和最小堆

  (1)是一颗完全二叉树,遵循完全二叉树的所有性质。

  (2)父节点的键值(大于)小于等于左右子节点的键值。

   最大堆和最小堆删除问题:即删除最大或者最小的元素,即根结点。取最后的元素提到根结点,然后再把新的根节点放到合适的位置。

3、平衡二叉树

    平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),具有以下性质:

    它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

    常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中,其高度一般都良好地维持在O(log2n),大大降低了操作的时间复杂度。

4、循环队列的元素个数:

     (Q.rear-Q.front+Q.size)%Q.size  //非常重要

5、海量数据处理:

     http://kb.cnblogs.com/page/95701/

     采用各种数据结构实现,其中堆排序,以及Hash函数以及Bit比较常用。

6、根据无向图得到最小生成树的算法:Prim算法和Kruskal算法

     参考的博客如下:http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html

原文地址:https://www.cnblogs.com/cxmhy/p/4749044.html