1、二叉查找树

  1. package search;
  3. import javax.swing.*;
  5. /**
  6.  * @author zwlstart
  7.  * @create 2020-12-26 20:55
  8.  */
  9. public class BinerySearchTree {
  12.     //返回树的全部节点数量
  13.     private  int size(Node x){
  14.         if (x == null){
  15.             return 0;
  16.         }else{
  17.             return x.n;
  18.         }
  19.     }
  21.     //查找一个节点
  22.     public Node get(Node x,int v){
  23.         if (x == null){
  24.             return null;
  25.         }
  26.         int i = x.val - v;
  27.         if (i == 0){
  28.             return x;
  29.         }else if (i > 0){
  30.             return get(x.left,v);
  31.         }else{
  32.             return get(x.right,v);
  33.         }
  34.     }
  36.     //插入一个节点
  37.     public Node put(Node x,int v){
  38.         if (x == null){
  39.             return new Node(v,1);
  40.         }
  41.         int i = x.val - v;
  42.         if (i == 0){
  43.             x.val = v;
  44.         }else if (i > 0){
  45.             x.left = put(x.left,v);
  46.         }else{
  47.             x.right = put(x.right,v);
  48.         }
  49.         x.n = size(x.left) + size(x.right) + 1;
  50.         return x;
  51.     }
  53.     //查找第i个节点
  54.     public int search(Node root,int i){
  55.         if (root == null || i > size(root) || i < 0){
  56.             return -1;
  57.         }
  58.         int size = size(root.left);
  59.         if (size > i){
  60.             return search(root.left,i);
  61.         }else if(size < i){
  62.             return search(root.right,i - size - 1);
  63.         }else {
  64.             return root.val;
  65.         }
  66.     }
  68.     /**
  69.      * 给定一个数，然后二叉树中节点值小于此数的节点数目
  70.      * @param v
  71.      * @return
  72.      */
  73.     public int rank(Node x,int v){
  74.         if (x == null){
  75.             return -1;
  76.         }
  77.         int i = x.val - v;
  78.         if (i == 0){
  79.             return size(x.left);
  80.         }else if (i > 0){
  81.             return rank(x.left,v);
  82.         }else{
  83.             return size(x.left) + 1 + rank(x.right,v);
  84.         }
  85.     }
  87.     /**
  88.      * 删除树中的最小值
  89.      * @param root
  90.      * @return
  91.      */
  92.     public Node deleteMin(Node root){
  93.         if (root.left == null){
  94.             return root.right;
  95.         }
  96.         root.left = deleteMin(root.left);
  97.         root.n = size(root.left) + size(root.right) + 1;
  98.         return root;
  99.     }
  101.     /**
  102.      * 删除指定的值，分为三种情况，当该节点只有一个子节点时，直接删除即可，让该节点的指针
  103.      * 指向唯一的子节点
  104.      * 如果该节点有两个孩子，则不能直接删除，需要找到该节点的直接后继或直接前继节点然后再删除
  105.      * 可分为四步：
  106.      *      1、找到后续节点
  107.      *      2、该节点指向后续节点
  108.      *      3、删除后续节点
  109.      *      4、后续的节点的左右孩子指向原节点的左右孩子节点
  110.      * @param root
  111.      * @param v
  112.      * @return
  113.      */
  114.     public Node delete(Node root, int v){
  115.         if (root == null){
  116.             return null;
  117.         }
  118.         int i = root.val - v;
  119.         if (i > 0){
  120.             root.left = delete(root.left,v);
  121.         }else if (i < 0){
  122.             root.right = delete(root.right,v);
  123.         }else{
  124.             if (root.left == null){
  125.                 return root.right;
  126.             }
  127.             if (root.right == null){
  128.                 return root.left;
  129.             }
  130.             Node temp = root;
  131.             root = searchMin(root.right);
  132.             //这一步必须在前，否则删除的会有问题，
  133.             //如果先执行 root.left = temp.left; 这步，则会将原本temp.left挂载到root.left上，
  134.             //此时root还是temp.right子树上的最小节点，再执行root.right = deleteMin(temp.right);
  135.             //删除的就不是temp了
  136.             root.right = deleteMin(temp.right);
  137.             root.left = temp.left; 
  138.         }
  140.         root.n = size(root.right) + size(root.left) + 1;
  141.         return root;
  142.     }
  144.     private Node searchMin(Node node) {
  145.         while (node.left != null){
  146.             node = node.left;
  147.         }
  148.         return node;
  149.     }
  151.     public BinerySearchTree() {
  153.     }
  154. }

2、avl树的实现

  1. package search;
  3. import javax.swing.*;
  5. /**
  6.  * @author zwlstart
  7.  * @create 2020-12-28 10:45
  8.  */
  9. public class AVL {
  10.     /**
  11.      * 返回以该节点为根的树高度
  12.      */
  13.     public int height(AvlNode x){
  14.         if (x == null){
  15.             return 0;
  16.         }
  17.         return x.height;
  18.     }
  20.     /**
  21.      * 插入一个节点
  22.      */
  23.     public AvlNode put(AvlNode x,int value){
  24.         if (x == null){
  25.             return new AvlNode(value,1);
  26.         }
  27.         int i = x.val - value;
  28.         if (i > 0){
  29.             x.left = put(x.left,value);
  30.         }else if (i < 0){
  31.             x.right = put(x.right,value);
  32.         }else {
  33.             x.val = value;
  34.         }
  36.         if (height(x.left) - height(x.right) > 1){
  37.             if (height(x.left.left) > height(x.left.right)){
  38.                 x = rotatlRight(x);
  39.             }else{
  40.                 x.left = rotatlLeft(x.left);
  41.                 x = rotatlRight(x);
  42.             }
  43.         }else if (height(x.left) - height(x.right) < -1) {
  44.             if (height(x.right.right) < height(x.right.left)){
  45.                 x = rotatlLeft(x);
  46.             }else{
  47.                 x.right = rotatlRight(x.right);
  48.                 x = rotatlLeft(x);
  49.             }
  50.         }
  51.         x.height = Integer.max(height(x.left),height(x.right)) + 1;
  52.         return x;
  53.     }
  55.     /**
  56.      * 左旋
  57.      */
  58.     private AvlNode rotatlLeft(AvlNode x) {
  59.         AvlNode temp = x.right;
  60.         x.right = temp.left;
  61.         temp.left = x;
  62.         x.height = Integer.max(height(x.left),height(x.right)) + 1;
  63.         temp.height = Integer.max(x.height,height(temp.right)) + 1;
  64.         return temp;
  65.     }
  67.     /**
  68.      * 右旋
  69.      */
  70.     private AvlNode rotatlRight(AvlNode x) {
  71.         AvlNode temp = x.left;
  72.         x.left = temp.right;
  73.         temp.right = x;
  74.         x.height = Integer.max(height(x.left),height(x.right)) + 1;
  75.         temp.height = Integer.max(height(temp.left),x.height) + 1;
  76.         return temp;
  77.     }
  79.     public AvlNode delete(AvlNode root,int k){
  80.         if (root == null){
  81.             return null;
  82.         }
  83.         int i = root.val - k;
  84.         if (i > 0){
  85.             root.left = delete(root.left,k);
  86.         }else if (i < 0){
  87.             root.right = delete(root.right,k);
  88.         }else{
  90.             if (root.left == null && root.right == null){
  91.                 return null;
  92.             }
  93.             if (root.left != null && root.right == null){
  94.                 return root.left;
  95.             }
  96.             if (root.left == null && root.right != null){
  97.                 return root.right;
  98.             }
  99.             if (root.left != null && root.right != null){
  100.                 AvlNode t = searchMin(root.right);
  101.                 root.val = t.val;
  102.                 root.right = delete(root.right,t.val);
  103.             }
  104.         }
  105.         if (height(root.left) - height(root.right) > 1){
  106.             if (height(root.left.left) > height(root.left.right)){
  107.                 root = rotatlRight(root);
  108.             }else{
  109.                 root.left = rotatlLeft(root.left);
  110.                 root = rotatlRight(root);
  111.             }
  112.         }else if (height(root.left) - height(root.right) < -1) {
  113.             if (height(root.right.right) < height(root.right.left)){
  114.                 root = rotatlLeft(root);
  115.             }else{
  116.                 root.right = rotatlRight(root.right);
  117.                 root = rotatlLeft(root);
  118.             }
  119.         }
  120.         root.height = Integer.max(height(root.left),height(root.right)) + 1;
  121.         return root;
  122.     }
  124.     private AvlNode searchMin(AvlNode x) {
  125.         if (x.left != null){
  126.             x = x.left;
  127.         }
  128.         return x;
  129.     }
  131. }

3、红黑树实现

未全部实现，删除操作尚未实现。

  1. package search;
  4. /**
  5.  * 红黑树的java实现
  6.  * @author zwlstart
  7.  * @create 2020-12-27 21:01
  8.  */
  9. public class RedBalckTree {
  10.     /**
  11.      * 查找一个节点
  12.      */
  13.     public RBNode get(RBNode x,int k){
  14.         if (x == null){
  15.             return null;
  16.         }
  17.         int i = x.val - k;
  18.         if (i == 0){
  19.             return x;
  20.         }else if (i > 0){
  21.             return get(x.left,k);
  22.         }else{
  23.             return get(x.right,k);
  24.         }
  25.     }
  27.     /**
  28.      * 返回树的全部节点数量
  29.      */
  30.     public int size(RBNode x){
  31.         if (x == null){
  32.             return 0;
  33.         }else{
  34.             return x.n;
  35.         }
  36.     }
  38.     /**
  39.      * 插入一个节点，需保持红黑树的性质
  40.      */
  41.     public RBNode put(RBNode x,int v){
  42.         if (x == null){
  43.             return new RBNode(v,1,true);
  44.         }
  45.         int i = x.val - v;
  46.         if (i == 0){
  47.             x.val = v;
  48.         }else if (i > 0){
  49.             x.left = put(x.left,v);
  50.         }else{
  51.             x.right = put(x.right,v);
  52.         }
  53.         if (isRed(x.right) && !isRed(x.left)){
  54.             x = rotateRight(x);
  55.         }
  56.         if (isRed(x.left) && isRed(x.left.left)){
  57.             x = rotateLeft(x);
  58.         }
  59.         if (isRed(x.left) && isRed(x.right)){
  60.             x = flipColors(x);
  61.         }
  62.         x.n = size(x.left) + size(x.right) + 1;
  63.         return x;
  64.     }
  66.     /**
  67.      * 判断该节点是否是红链接所指向的
  68.      * @param x
  69.      * @return
  70.      */
  71.     public boolean isRed(RBNode x){
  72.         if (x == null){
  73.             return false;
  74.         }
  75.         return x.color;
  76.     }
  78.     /**
  79.      * 右旋
  80.      * @param x
  81.      * @return
  82.      */
  83.     public RBNode rotateRight(RBNode x){
  84.         RBNode t = x.right;
  85.         x.right = t.left;
  86.         t.left = x;
  87.         t.color = x.color;
  88.         x.color = true;
  89.         t.n = x.n;
  90.         x.n = size(x.left) + size(x.right) + 1;
  91.         return t;
  92.     }
  94.     /**
  95.      * 左旋
  96.      * @param x
  97.      * @return
  98.      */
  99.     public RBNode rotateLeft(RBNode x){
  100.         RBNode t = x.left;
  101.         x.left = t.right;
  102.         t.right = x;
  103.         t.color = x.color;
  104.         x.color = true;
  105.         t.n = x.n;
  106.         x.n = size(x.left) + size(x.right) + 1;
  107.         return t;
  108.     }
  110.     /**
  111.      * 变换节点颜色
  112.      * @param x
  113.      * @return
  114.      */
  115.     public RBNode flipColors(RBNode x){
  116.         x.right.color = false;
  117.         x.left.color = false;
  118.         x.color = true;
  119.         return x;
  120.     }
  122.     //查找第i个节点
  123.     public int search(RBNode root,int i){
  124.         if (root == null || i > size(root) || i < 0){
  125.             return -1;
  126.         }
  127.         int size = size(root.left);
  128.         if (size > i){
  129.             return search(root.left,i);
  130.         }else if(size < i){
  131.             return search(root.right,i - size - 1);
  132.         }else {
  133.             return root.val;
  134.         }
  135.     }
  137.     /**
  138.      * 给定一个数，然后二叉树中节点值小于此数的节点数目
  139.      * @param v
  140.      * @return
  141.      */
  142.     public int rank(RBNode x,int v){
  143.         if (x == null){
  144.             return -1;
  145.         }
  146.         int i = x.val - v;
  147.         if (i == 0){
  148.             return size(x.left);
  149.         }else if (i > 0){
  150.             return rank(x.left,v);
  151.         }else{
  152.             return size(x.left) + 1 + rank(x.right,v);
  153.         }
  154.     }
  156.     /**
  157.      * 删除树中的最小值
  158.      * @param root
  159.      * @return
  160.      */
  161.     public RBNode deleteMin(RBNode root){
  162.         if (root.left == null){
  163.             return root.right;
  164.         }
  165.         root.left = deleteMin(root.left);
  166.         root.n = size(root.left) + size(root.right) + 1;
  167.         return root;
  168.     }
  170. }

4、散列表的实现

  1. SeparateChainingHashST.java
  3. Below is the syntax highlighted version of SeparateChainingHashST.java.
  6. /******************************************************************************
  7.  *  Compilation:  javac SeparateChainingHashST.java
  8.  *  Execution:    java SeparateChainingHashST < input.txt
  9.  *  Dependencies: StdIn.java StdOut.java
  10.  *  Data files:   https://algs4.cs.princeton.edu/34hash/tinyST.txt
  11.  *
  12.  *  A symbol table implemented with a separate-chaining hash table.
  13.  * 
  14.  ******************************************************************************/
  16. package edu.princeton.cs.algs4;
  18. /**
  19.  *  The {@code SeparateChainingHashST} class represents a symbol table of generic
  20.  *  key-value pairs.
  21.  *  It supports the usual <em>put</em>, <em>get</em>, <em>contains</em>,
  22.  *  <em>delete</em>, <em>size</em>, and <em>is-empty</em> methods.
  23.  *  It also provides a <em>keys</em> method for iterating over all of the keys.
  24.  *  A symbol table implements the <em>associative array</em> abstraction:
  25.  *  when associating a value with a key that is already in the symbol table,
  26.  *  the convention is to replace the old value with the new value.
  27.  *  Unlike {@link java.util.Map}, this class uses the convention that
  28.  *  values cannot be {@code null}—setting the
  29.  *  value associated with a key to {@code null} is equivalent to deleting the key
  30.  *  from the symbol table.
  31.  *  <p>
  32.  *  This implementation uses a separate chaining hash table. It requires that
  33.  *  the key type overrides the {@code equals()} and {@code hashCode()} methods.
  34.  *  The expected time per <em>put</em>, <em>contains</em>, or <em>remove</em>
  35.  *  operation is constant, subject to the uniform hashing assumption.
  36.  *  The <em>size</em>, and <em>is-empty</em> operations take constant time.
  37.  *  Construction takes constant time.
  38.  *  <p>
  39.  *  For additional documentation, see <a href="https://algs4.cs.princeton.edu/34hash">Section 3.4</a> of
  40.  *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
  41.  *  For other implementations, see {@link ST}, {@link BinarySearchST},
  42.  *  {@link SequentialSearchST}, {@link BST}, {@link RedBlackBST}, and
  43.  *  {@link LinearProbingHashST},
  44.  *
  45.  *  @author Robert Sedgewick
  46.  *  @author Kevin Wayne
  47.  */
  48. public class SeparateChainingHashST<Key, Value> {
  49.     private static final int INIT_CAPACITY = 4;
  51.     private int n;                                // number of key-value pairs
  52.     private int m;                                // hash table size
  53.     private SequentialSearchST<Key, Value>[] st;  // array of linked-list symbol tables
  56.     /**
  57.      * Initializes an empty symbol table.
  58.      */
  59.     public SeparateChainingHashST() {
  60.         this(INIT_CAPACITY);
  61.     } 
  63.     /**
  64.      * Initializes an empty symbol table with {@code m} chains.
  65.      * @param m the initial number of chains
  66.      */
  67.     public SeparateChainingHashST(int m) {
  68.         this.m = m;
  69.         st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[m];
  70.         for (int i = 0; i < m; i++)
  71.             st[i] = new SequentialSearchST<Key, Value>();
  72.     } 
  74.     // resize the hash table to have the given number of chains,
  75.     // rehashing all of the keys
  76.     private void resize(int chains) {
  77.         SeparateChainingHashST<Key, Value> temp = new SeparateChainingHashST<Key, Value>(chains);
  78.         for (int i = 0; i < m; i++) {
  79.             for (Key key : st[i].keys()) {
  80.                 temp.put(key, st[i].get(key));
  81.             }
  82.         }
  83.         this.m  = temp.m;
  84.         this.n  = temp.n;
  85.         this.st = temp.st;
  86.     }
  88.     // hash function for keys - returns value between 0 and m-1
  89.     private int hashTextbook(Key key) {
  90.         return (key.hashCode() & 0x7fffffff) % m;
  91.     }
  93.     // hash function for keys - returns value between 0 and m-1 (assumes m is a power of 2)
  94.     // (from Java 7 implementation, protects against poor quality hashCode() implementations)
  95.     private int hash(Key key) {
  96.         int h = key.hashCode();
  97.         h ^= (h >>> 20) ^ (h >>> 12) ^ (h >>> 7) ^ (h >>> 4);
  98.         return h & (m-1);
  99.     }
  101.     /**
  102.      * Returns the number of key-value pairs in this symbol table.
  103.      *
  104.      * @return the number of key-value pairs in this symbol table
  105.      */
  106.     public int size() {
  107.         return n;
  108.     } 
  110.     /**
  111.      * Returns true if this symbol table is empty.
  112.      *
  113.      * @return {@code true} if this symbol table is empty;
  114.      *         {@code false} otherwise
  115.      */
  116.     public boolean isEmpty() {
  117.         return size() == 0;
  118.     }
  120.     /**
  121.      * Returns true if this symbol table contains the specified key.
  122.      *
  123.      * @param  key the key
  124.      * @return {@code true} if this symbol table contains {@code key};
  125.      *         {@code false} otherwise
  126.      * @throws IllegalArgumentException if {@code key} is {@code null}
  127.      */
  128.     public boolean contains(Key key) {
  129.         if (key == null) throw new IllegalArgumentException("argument to contains() is null");
  130.         return get(key) != null;
  131.     } 
  133.     /**
  134.      * Returns the value associated with the specified key in this symbol table.
  135.      *
  136.      * @param  key the key
  137.      * @return the value associated with {@code key} in the symbol table;
  138.      *         {@code null} if no such value
  139.      * @throws IllegalArgumentException if {@code key} is {@code null}
  140.      */
  141.     public Value get(Key key) {
  142.         if (key == null) throw new IllegalArgumentException("argument to get() is null");
  143.         int i = hash(key);
  144.         return st[i].get(key);
  145.     } 
  147.     /**
  148.      * Inserts the specified key-value pair into the symbol table, overwriting the old 
  149.      * value with the new value if the symbol table already contains the specified key.
  150.      * Deletes the specified key (and its associated value) from this symbol table
  151.      * if the specified value is {@code null}.
  152.      *
  153.      * @param  key the key
  154.      * @param  val the value
  155.      * @throws IllegalArgumentException if {@code key} is {@code null}
  156.      */
  157.     public void put(Key key, Value val) {
  158.         if (key == null) throw new IllegalArgumentException("first argument to put() is null");
  159.         if (val == null) {
  160.             delete(key);
  161.             return;
  162.         }
  164.         // double table size if average length of list >= 10
  165.         if (n >= 10*m) resize(2*m);
  167.         int i = hash(key);
  168.         if (!st[i].contains(key)) n++;
  169.         st[i].put(key, val);
  170.     } 
  172.     /**
  173.      * Removes the specified key and its associated value from this symbol table     
  174.      * (if the key is in this symbol table).    
  175.      *
  176.      * @param  key the key
  177.      * @throws IllegalArgumentException if {@code key} is {@code null}
  178.      */
  179.     public void delete(Key key) {
  180.         if (key == null) throw new IllegalArgumentException("argument to delete() is null");
  182.         int i = hash(key);
  183.         if (st[i].contains(key)) n--;
  184.         st[i].delete(key);
  186.         // halve table size if average length of list <= 2
  187.         if (m > INIT_CAPACITY && n <= 2*m) resize(m/2);
  188.     } 
  190.     // return keys in symbol table as an Iterable
  191.     public Iterable<Key> keys() {
  192.         Queue<Key> queue = new Queue<Key>();
  193.         for (int i = 0; i < m; i++) {
  194.             for (Key key : st[i].keys())
  195.                 queue.enqueue(key);
  196.         }
  197.         return queue;
  198.     } 
  201.     /**
  202.      * Unit tests the {@code SeparateChainingHashST} data type.
  203.      *
  204.      * @param args the command-line arguments
  205.      */
  206.     public static void main(String[] args) { 
  207.         SeparateChainingHashST<String, Integer> st = new SeparateChainingHashST<String, Integer>();
  208.         for (int i = 0; !StdIn.isEmpty(); i++) {
  209.             String key = StdIn.readString();
  210.             st.put(key, i);
  211.         }
  213.         // print keys
  214.         for (String s : st.keys()) 
  215.             StdOut.println(s + " " + st.get(s)); 
  217.     }
  219. }