# 顺序查找

  • 思想: 这是最简单的算法,从头开始遍历每个元素,并将每个元素与查找元素比较,如果一致则返回。

  • 时间复杂度: O(n)

  • 空间复杂度: O(1)

  • 代码示例:

    public int search(int[] array, int num) {
        if (array == null || array.length == 0) {
            return -1;
        }
        for (int i = 0; i < array.length; i++) {
            if (array[i] == num) {
                return i;
            }
        }
        return -1;
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11

# 二分查找

  • 思想: 二分查找前提是查找的数组是有序的,利用数据有序的特性提高查找性能。首先与数组中间位置的值比较,如果查找值大于中间位置值,则对数组右边以相同的思路查找,否则在左边以相同方式查找。这种方式使得每次查找范围变为原来的1/2。

  • 时间复杂度: O(log2n)

  • 空间复杂度: O(1)

  • 代码示例:

    public int halfSearch(int[] array, int num) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int lo = 0, hi = array.length - 1;
        while(lo <= hi) {
            int mid = lo + ((hi - lo) >> 1); //此处考虑边界问题不能使用 (lo + hi) / 2
            if (array[mid] == num) {
                return mid;
            } else if (array[mid] < num) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return -1;
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17

# hash算法

  • 思想: 哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映射到一个有限的地址区间上,并将关键字对应的值存储在该地址空间,可以通过关键字快速获取对应的值,这种表成为哈希表或散列,所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比,哈希表无疑是查找速度比较快的一种。
  • 时间复杂度: O(1)
  1. 哈希函数:

    1. 直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key)=a?key + b,其中a和b为常数(这种散列函数叫做自身函数)。
    2. 数字分析法:数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相同,这样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用后面的数字来构成散列地址,则冲突的几率会明显降低。
    3. 平方取中法:取关键字平方后的中间几位作为散列地址。
    4. 折叠法:将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加(去除进位)作为散列地址。
    5. 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即H(key)= key MOD p,p <= m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义词。
  2. hash冲突及解决

    hash冲突在所难免,解决冲突是一个复杂问题。冲突主要取决于:

    • 与散列函数有关,一个好的散列函数的值应尽可能平均分布。
    • 与解决冲突的哈希冲突函数有关。
    • 与负载因子的大小有关。太大不一定就好,而且浪费空间严重,负载因子和散列函数是联动的。

    解决冲突的办法:

    • 开放地址法:线性探查法、平方探查法、伪随机序列法、双哈希函数法。
    • 拉链法:把所有同义词,及hash值相同的记录,用单链表连接起来。
  3. 应用:字符串哈希;加密哈希;集合哈希;布隆过滤器

  4. 不足:获取有序序列复杂度高

# 二叉搜索树

  • 思想: 二叉查找树(Binary Search Tree),也称有序二叉树(Ordered Binary Tree),排序二叉树(Sorted Binary Tree),是指一棵空树或者具有下列性质的二叉树:1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;3. 任意节点的左、右子树也分别为二叉查找树;4. 没有键值相等的节点(no duplicate nodes)。
  • 时间复杂度: 插入和查找的时间复杂度均为O(logn),最坏为O(n)
  1. 插入

    • 如果当前节点是null,则创建新节点返回。
    • 如果插入节点比当前节点值大,则插入其右孩子节点中。
    • 如果插入节点比当前节点值小,则插入其左孩子节点中。
      • 复杂度:平均O(logn) 最坏O(n)

      • 代码示例:

        public Tree insert(Tree root, int val) {
            if (root == null) {
                return new Tree(val);
            }
            if (val == root.val) {
                return root;
            } else if (val > root.val) {
                root.right = insert(root.right, val);
            } else {
                root.left = insert(root.left, val);
            }
            return root;
        }
        
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
  2. 查找

    • 某个值

      • 思想:查找方式有点类似二分查找方法,只是这里采用的树结构进行存储。首先与根节点进行判断:

        1. 如果当前节点为null,则直接返回null。
        2. 如果当前节点值与查找值相同则返回当前节点。
        3. 如果当前节点值小于查找值,则以递归方式到当前节点的右孩子查找。
        4. 如果当前节点值大于查找值,则以递归方式到当前节点的左孩子查找。
      • 时间复杂度:平均O(logn) 最坏O(n)

      • 代码示例:

        public Tree search(Tree root, int val) {
            if (root == null) {
                return null;
            }
            if (root.val = val) {
                return root;
            } else if (root.val > val) {
                return search(root.left, val);
            } else {
                return search(root.right, val);
            }
        }
        
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
    • 查找最小值

      • 思想:根据二叉查找树的特点,最小节点都是在最左节点上或者如果根节点无左孩子便是其本身。

      • 代码示例:

        public Tree min(Tree root) {
            if (root == null) {
                return null;
            }
            if (root.left != null) {
                return min(root.left);
            }
            return root;
        }
        
        1
        2
        3
        4
        5
        6
        7
        8
        9
    • 查找最大节点

      • 思想:同最小节点。

      • 代码示例:

        public Tree max(Tree root) {
            if (root == null) {
                return null;
            }
            if (root.right != null) {
                return max(root.right);
            }
            return root;
        }
        
        1
        2
        3
        4
        5
        6
        7
        8
        9
  3. 删除

    • 删除最小节点

      • 思想:找到根节点最左节点,如果其不存在右孩子则直接删除,否则用右孩子替换最左节点。需要注意的是根节点可能为null和不存在左孩子的情况。

      • 代码示例:

        public Tree deleteMin(Tree root) {
            if (root == null) {
                return null;
            }
            if (root.left != null) {
                root.left = deleteMin(root.left);
            } else if (root.right != null) {
                return root.right;
            }
            return null;
        }
        
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
    • 删除最大节点

      • 思想:与删除最小节点类似,根据二叉搜索树的特性,最大节点是根节点的最右孩子。所以只要找到最右孩子节点,其存在左节点的话就用左节点替换否则直接删除。

      • 代码示例:

        public Tree deleteMax(Tree root) {
            if (root == null) {
                return null;
            }
            if (root.right != null) {
                root.right = deleteMax(root.right);
            } else if (root.left != null) {
                return root.left;
            }
            return null;
        }
        
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
    • 删除某个节点

      • 思想:要删除一个节点首先需要找到该节点的位置,采用上面的查找方式进行查找。找到节点后就是删除的问题,可以按照下面的策略进行删除。

        1. 如果一个节点无左孩子和右孩子,那么就可以直接删除。
        2. 如果只存在一个孩子节点,则用孩子节点替换。
        3. 如果存在两个孩子节点,那么可以用其左孩子最大的节点或者右孩子最小节点替换,并删除最左孩子节点或最右孩子节点。
      • 代码示例:

        public Tree delete(Tree root, int val) {
            if (root == null) {
                return null;
            }
            if (root.val == val) {
                if (root.left == null && root.right == null) {
                    return null;
                } else if (root.left != null && root.right != null) {
                    Tree leftBig = max(root.left);
                    root.val = leftBig.val;
                    root.left = delete(root.left, leftBig.val);
                } else if (root.left != null) {
                    return root.left;
                } else {
                    return root.right;
                }
            } else if (root.val < val) {
                root.right  = delete(root.right, val);
            } else {
                root.left = delete(root.left, val);
            }
            return root;
        }
        
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23

# AVL查找树

  • 思想: 二叉树查找树在插入时没有对二叉树的深度和结构做一个调整,使得叶子节点深度不一,在查找时深度越深的节点时间复杂度越高。为了改进查找的时间复杂度,于是出现了平衡二叉树(AVL)。平衡二叉树使得每个节点的左节点和右节点的深度差不超过1。
  1. 查找

    查找与二叉查找树一样。

  2. 插入

    当在AVL中插入新的结点时,需要根据实际情况对AVL中的某些结点做单旋转或双旋转操作,单旋转表示做一次顺时针或逆时针的旋转操作,而双旋转则做两次单旋转操作(先顺时针后逆时针,或者先逆时针后顺时针),单旋转发生在LL型插入和RR型插入,而双旋转则发生在LR型插入和RL型插入。以下的失去平衡点都指的是离插入点最近的那个失去平衡的结点。

    • LL型:插入点位于失去平衡点的左孩子的左子树上;
    • RR型:插入点位于失去平衡点的右孩子的右子树上;
    • LR型:插入点位于失去平衡点的左孩子的右子树上;
    • RR型:插入点位于失去平衡点的右孩子的左子树上。

    插入思路 和二叉搜索树的插入一样,首先在树中找到对应的位置然后插入,接着自底向上向根节点折回,于在插入期间成为不平衡的所有节点上进行旋转来完成。因为折回到根节点的路途上最多有 1.5 乘 log n 个节点,而每次AVL 旋转都耗费恒定的时间,插入处理在整体上耗费 O(log n) 时间。具体插入过程如下:

     1. 如果当前结点为空,创建新结点返回.
     1. 如果当前结点值和插入值相同,不做处理返回。
     1. 如果插入值大于当前结点则插入到右其右孩子结点中。插入完成后比较左右孩子结点进行判断树是否失去平衡。如果是判断属于那种类型(RR, RL),并响应的旋转。最后更新当前结点的深度(孩子结点的最大深度加1,默认null深度为-1)。
     1. 否则插入到其做孩子上。 同样比较左右孩子的深度判断是否平衡,对于失去平衡的情况下做出调整。
    
    • 代码示例:

      private AvlNode insert(AnyType x, AvlNode t) { 
          if (t == null) {
              return new AvlNode(x, null, null); 
          }
          int compareResult = myCompare(x, t.element); 
          if (compareResult < 0) {
              t.left = insert(x, t.left); 
              if (height(t.left) - height(t.right) == 2) {
                  if (myCompare(x, t.left.element) < 0) {
                      //左左情况 
                      t = rotateWithLeftChild(t); 
                  } else {
                      //左右情况
                      t = doubleWithLeftChild(t); 
                  }
              } 
          } else if (compareResult > 0) {
              t.right = insert(x, t.right); 
              if (height(t.right) - height(t.left) == 2) {
                  if (myCompare(x, t.right.element) < 0) {
                      //右左情况 
                      t = doubleWithRightChild(t); 
                  } else {
                      //右右情况 
                      t = rotateWithRightChild(t); 
                  }
              } 
          }
          //完了之后更新height值 
          t.height = Math.max(height(t.left), height(t.right)) + 1; 
          return t; 
      }
      
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
  3. 删除

    从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点,接着直接剪除这个叶子节点来完成。因为在旋转成叶子节点期间最多有 log n个节点被旋转,而每次 AVL 旋转耗费恒定的时间,删除处理在整体上耗费 O(log n) 时间。 a.当被删除节点n是叶子节点,直接删除 b.当被删除节点n只有一个孩子,删除n,用孩子替代该节点的位置 c.当被删除结点n存在左右孩子时,真正的删除点应该是n的中序遍在前驱,或者说是左子树最大的节点,之后n的值替换为真正删除点的值。这就把c归结为a,b的问题。

    从删除的结点处自低向上向根结点折回,根据当前结点的左右孩子深度判断是否平衡,如果不平衡则按选择规则进行旋转。最后更新当前结点深度,如此递归折回到根结点。

# B-树

  • 定义

    B-树是一种平衡的多路查找树,它在文件系统中很有用。 定义:一棵m 阶的B-树,或者为空树,或为满足下列特性的m 叉树:

    • 树中每个结点至多有m 棵子树;
    • 若根结点不是叶子结点,则至少有两棵子树;
    • 除根结点之外的所有非终端结点至少有⎡m/2⎤ 棵子树;
    • 所有的非终端结点中包含以下信息数据:(n,A0,K1,A1,K2,…,Kn,An) 其中:Ki(i=1,2,…,n)为关键码,且Ki< Ki+1,Ai 为指向子树根结点的指针(i=0,1,…,n),且指针Ai-1 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n),An 所指子树中所有结点的关键码均大于Kn, ⎡m/2⎤ −1 ≤ n ≤m −1 ,n 为关键码的个数。
    • 所有的叶子结点都出现在同一层次上,并且不带信息(可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空
  • B-树的特性:

    1. 关键字集合分布在整棵树中;
    2. 任何一个关键字出现且只出现在一个节点中;
    3. 搜索有可能在非叶子节点结束;
    4. 其搜索性能等价于在关键字全集内做一次二分查找;
    5. 自动层次控制。
  1. 查找

    B-树的查找是由两个基本操作交叉进行的过程,即

    • 在B-树上找结点;
    • 在结点中找关键码。

    由于,通常B-树是存储在外存上的,操作⑴就是通过指针在磁盘相对定位,将结点信息读入内存,之后,再对结点中的关键码有序表进行顺序查找或折半查找。因为,在磁盘上读取结点信息比在内存中进行关键码查找耗时多,每次向下搜索一层都需要从内存中加载磁盘信息,B-树的层次树是决定B-树查找效率的首要因素。

  2. 插入

    在B-树上插入关键码与在二叉排序树上插入结点不同,关键码的插入不是在叶结点上 进行的,而是在最底层的某个非终端结点中添加一个关键码,若该结点上关键码个数不超过m-1 个,则可直接插入到该结点上;否则,该结点上关键码个数至少达到m 个,因而使该结点的子树超过了m棵,这与B-树定义不符。所以要进行调整,即结点的“分裂”。方法为:关键码加入结点后,将结点中的关键码分成三部分,使得前后两部分关键码个数个结点将其插入到父结点中。若插入父结点而使父结点中关键码个数超过m-1,则父结点继续分裂,直到插入某个父结点,其关键码个数小于m。可见,B-树是从底向上生长的。

  3. 删除

    分两种情况:

    1. 删除最底层结点中关键码

      • 若结点中关键码个数大于⎡m / 2⎤ -1,直接删去。
      • 否则除余项与左兄弟(无左兄弟,则找左兄弟)项数之和大于等于2( -1) 就与它 们父结点中的有关项一起重新分配
    2. 删除为非底层结点中关键码 若所删除关键码非底层结点中的Ki,则可以指针Ai 所指子树中的最小关键码X 替代 Ki,然后,再删除关键码X,直到这个X 在最底层结点上,即转为(1)的情形

# B+树

  • 定义

    • 有n 棵子树的结点中含有n 个关键码;
    • 所有的叶子结点中包含了全部关键码的信息,及指向含有这些关键码记录的指针,且 叶子结点本身依关键码的大小自小而大的顺序链接。
    • 所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键码。
  • B+树的特性

    1. 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
    2. 不可能在非叶子结点命中;
    3. 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;
    4. 更适合文件索引系统;
  1. 查找

    对B+树可以进行两种查找运算:

    • 从最小关键字起顺序查找;
    • 从根结点开始,进行随机查找。

    在查找时,若非终端结点上的剧组机等于给定值,并不终止,而是继续向下直到叶子结点。因此,在B+树中,不管查找成功与否,每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。

  2. 插入

    B+树的插入与B树的插入过程类似。不同的是B+树在叶结点上进行,如果叶结点中的关键码个数超过m,就必须分裂成关键码数目大致相同的两个结点,并保证上层结点中有这两个结点的最大关键码。

  3. 删除

    B+树的删除也仅在叶子结点进行,当叶子结点中的最大关键字被删除时,其在非终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少于m/2 (m/2结果取上界,如5/2结果为3)时,其和兄弟结点的合并过程亦和B-树类似。

# B+树和B-树最大的不同点

  1. B-树的关键字和记录是放在一起的,叶子节点可以看作外部节点,不包含任何信息;B+树的非叶子节点中只有关键字和指向下一个节点的索引,记录只放在叶子节点中。

  2. 在B-树中,越靠近根节点的记录查找时间越快,只要找到关键字即可确定记录的存在;而B+树中每个记录的查找时间基本是一样的,都需要从根节点走到叶子节点,而且在叶子节点中还要再比较关键字。从这个角度看B-树的性能好像要比B+树好,而在实际应用中却是B+树的性能要好些。因为B+树的非叶子节点不存放实际的数据,这样每个节点可容纳的元素个数比B-树多,树高比B-树小,这样带来的好处是减少磁盘访问次数。尽管B+树找到一个记录所需的比较次数要比B-树多,但是一次磁盘访问的时间相当于成百上千次内存比较的时间,因此实际中B+树的性能可能还会好些,而且B+树的叶子节点使用指针连接在一起,方便顺序遍历(例如查看一个目录下的所有文件,一个表中的所有记录等),这也是很多数据库和文件系统使用B+树的缘故。

  3. B+树支持range-query非常方便,而B树不支持。这是数据库选用B+树的最主要原因。

# 红黑树

  • 思想

    红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

  • 特性

    • 节点是红色或黑色。
    • 根是黑色。
    • 所有叶子都是黑色(叶子是NIL节点)。
    • 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
    • 从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。
  1. 插入

    红黑树插入的几种情况:

    1. z的叔叔y是红色的。
    2. z的叔叔y是黑色的,且z是右孩子
    3. z的叔叔y是黑色的,且z是左孩子
  2. 删除

    红黑树删除的几种情况。

    1. x的兄弟w是红色的。
    2. x的兄弟w是黑色的,且w的俩个孩子都是黑色的。
    3. x的兄弟w是黑色的,且w的左孩子是红色,w的右孩子是黑色。
    4. x的兄弟w是黑色的,且w的右孩子是红色的。

# 红黑树和AVL树的比较

  • 红黑树

    • (1)并不追求“完全平衡”——它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。
    • (2)此外,由于它的设计,任何不平衡都会在三次旋转之内解决。红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高。
  • AVL树

    • 它的左子树和右子树都是AVL树,左子树和右子树的高度差不能超过;
    • 查找、插入和删除在平均和最坏情况下都是O(log n),增加和删除可能需要通过一次或多次树旋转来重新平衡这个树;
    • 一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1) 一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)). 一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n)).

# 哈夫曼树