By

Contents
  1. 1. 计算机内存不足
  2. 2. 进程间通信
    1. 2.1. Linux : 管道，消息队列，共享内存，信号量，套接口等等
    2. 2.2. Windows : 消息(linux信号)、共享内存、邮件槽（mailslot） (点对点消息队列)、管道、socket、
  3. 3. 二叉树种类
    1. 3.1. B-树
    2. 3.2. B+树
    3. 3.3. 字典树

计算机内存不足

  1. 当计算机系统内存不足的时候，系统会自动启用虚拟内存来解决内存不足的问题

    所谓虚拟内存 ，就是把硬盘上的一块区域当作物理内存（RAM）来使用

    性能：由于硬盘的读写速度和内存时不能比的，所以性能会很差

进程间通信

Linux : 管道，消息队列，共享内存，信号量，套接口等等

Windows : 消息(linux信号)、共享内存、邮件槽（mailslot） (点对点消息队列)、管道、socket、

​ 剪切板、动态数据交换、文件映射、对象链接与嵌入、远程过程调用、动态连接库、WM_COPYDATA

二叉树种类

  • 满二叉树：

  • 完全二叉树：深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

  • 二叉查找树、二叉有序树、

    如果树不是一颗空树的话，那么二叉查找树具有以下特征：

    1
    2
    3
    4
    1. 若左子树不为空，那么左子树所有节点的值小于均小于他的根节点的值。
    2. 若右子树不为空，那么右子树的所有节点的值大于根节点的值。
    3. 左右子树也分别为二叉排序树。
    4. 没有键值相等的节点。

  • 平衡二叉树 （AVL） :一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

  • 红黑树

    1
    2
    3
    4
    5
    1. 每个节点要么是红的，要么是黑的
    2. 根节点必须是黑的
    3. 每个叶子节点是黑的
    4. 如果父节点是红的，那么两个子节点是黑的
    5. 对于每个节点，从该节点到其子孙节点的所有路径上包含相同数目

  • B-树

    B-树是一种多路搜索树

    性质：

    1
    2
    3
    4
    5
    1. 根结点至少有两个子女；

    2. 每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；
    3. 除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；
    4.  所有的叶子结点都位于同一层。

  • B+树

    B+树是B-树的变体，也是一种多路搜索树：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     1.其定义基本与B-树同，除了：

     2.非叶子结点的子树指针与关键字个数相同；

    3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树

    （B-树是开区间）；

     5.为所有叶子结点增加一个链指针；

    6.所有关键字都在叶子结点出现；

  • 字典树

    1
    2
    3
    4
    5
    6
    1.又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。
    典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

    2.它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

    3.字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树
Contents
  1. 1. 计算机内存不足
  2. 2. 进程间通信
    1. 2.1. Linux : 管道，消息队列，共享内存，信号量，套接口等等
    2. 2.2. Windows : 消息(linux信号)、共享内存、邮件槽（mailslot） (点对点消息队列)、管道、socket、
  3. 3. 二叉树种类
    1. 3.1. B-树
    2. 3.2. B+树
    3. 3.3. 字典树