JAVA基础集合框架【四】HashMap之源码分析红黑树-BST

文章首发于：clawhub.club

---

定义

SBT(Binary Sort Tree或者Binary Search Tree),二叉查找树，二叉排序树，是有一定性质的二叉树。
在理想的情况下，二叉查找树增删查改的时间复杂度为O(logN)（其中N为节点数），最坏的情况下为O(N)。
当它的高度为logN+1时，我们就说二叉查找树是平衡的。

性质：

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
• 左、右子树也分别为二叉查找树。

注意：

• 从特性中可以看出是支持重复值的。如果有重复的值，会影响到查询效率，所以一般在插入的时候，如果碰到重复的值，直接过滤处理。
• 当二叉查找树以中序遍历时，遍历的结果是一个从小到大排列的顺序。

节点定义

Java代码实现：

/**
 * 节点
 */
private class Node<V> {
    /**
     * 值
     */
    private V value;
    /**
     * 频率,如果value相同，则此值+1，去掉了重复的项
     */
    private int freq;
    /**
     * 父节点
     */
    private Node<V> parent;
    /**
     * 左节点
     */
    private Node<V> left;
    /**
     * 右节点
     */
    private Node<V> right;

}

查找

当BST查找的时候，先与当前节点进行比较：

• 如果相等的话就返回当前节点；
• 如果少于当前节点则继续查找当前节点的左节点；
• 如果大于当前节点则继续查找当前节点的右节点。

直到当前节点指针为空或者查找到对应的节点
Java代码实现：

/**
 * Search .
 *
 * @param value the value
 * @return node
 */
public Node<V> search(V value) {
    //死循环
    while (true) {
        //如果根节点为null,返回null
        if (root == null) {
            return null;
        }
        //如果根节点的value与待查找value相同，返回根节点的值
        if (root.value.equals(value)) {
            return root;
        } else if (root.value.compareTo(value) < 0) {
            //如果待查找的value大于根节点的value,则继续查找根节点右边的节点
            root = root.right;
        } else {
            //如果待查找的value小于根节点的value，则查找根节点左边的节点
            root = root.left;
        }
    }

}

插入

• 通过循环查找到待插入的节点的父节点，比大小，小的往左，大的往右。
• 如果父节点为空，就此节点作为根节点。
• 如果父节点不为空，对比父节点，小的就插入到父节点的左节点，大就插入到父节点的右节点上。
• 重复节点的插入用值域中的freq标记

Java代码实现：

/**
 * Insert.
 *
 * @param current the current
 */
public void insert(Node<V> current) {
    //父节点
    Node<V> parent = null;

    //循环查找到待插入的节点的父节点
    while (true) {
        //如果根节点为null,跳出寻循环
        if (root == null) {
            break;
        }
        //指定父节点
        parent = root;

        //如果待插入的值 等于 根节点节点的值
        if (root.value.equals(current.value)) {
            //频率加1
            current.freq++;
            //程序结束
            return;

        } else if (root.value.compareTo(current.value) < 0) {
            //如果待插入的值 大于 根节点的值,则查找当前节点右边的节点
            root = root.right;
        } else {
            //如果待插入的值 小于 根节点的值,则查找当前节点左边的节点
            root = root.left;
        }
    }
    //找到待插入值的父节点
    if (null != parent) {
        //如果待插入的值 大于 父节点的值，则插入到父节点的右边
        if (parent.value.compareTo(current.value) < 0) {
            current.parent = parent;
            parent.right = current;
        } else {
            //如果待插入的值 小于 父节点的值，则插入到父节点的左边
            current.parent = parent;
            parent.left = current;
        }
    } else {
        //如果根节点为空，就此节点作为根节点
        root = current;
    }

}

删除

• 查找到要删除的节点。
• 没有左右子节点，可以直接删除
• 存在左节点或者右节点，删除后需要对子节点移动
• 同时存在左右子节点，不能简单的删除，但是可以通过和后继节点交换后转换为前两种情况
  Java代码实现：

  /**
       * Delete.
       *
       * @param value the value
       */
      public void delete(V value) {
          //找到要删除的节点
          Node<V> current = search(value);
          //如果未找到
          if (current == null) {
              return;
          }
          Node<V> parent = current.parent;
          //如果删除节点为根节点，直接删除
          if (parent == null) {
              //被删节点如果为根节点
              root = null;
          }
  
          //3-如果同时存在左右子节点
          if (current.left != null && current.right != null) {
              //获取中序遍历后的后继结点，以其右孩子为根的子树的最小结点
              Node<V> successor = minimum(current.right);
              //将后继结点值转移到到当前节点上
              current.value = successor.value;
              //把要删除的当前节点设置为后继结点
              current = successor;
          }
  
          //1-被删节点为叶子节点，直接删除
          if (current.left == null && current.right == null) {
              if (parent.left == current) {
                  //当前节点为父节点的左节点
                  parent.left = null;
              } else {
                  //当前节点为父节点的右节点
                  parent.right = null;
              }
  
              //2-被删除的节点只有一个子节点
          } else if (current.left == null || current.right == null) {
              Node<V> child;
              if (current.left != null) {
                  child = current.left;
              } else {
                  child = current.right;
              }
  
              if (parent.left == current) {
                  //当前节点的父节点的左节点指向当前节点的子节点
                  parent.left = child;
              } else {
                  //当前节点的父节点的右节点指向当前节点的子节点
                  parent.right = child;
              }
              //当前节点的子节点指向当前节点的父节点
              child.parent = parent;
          }
  
      }
  
  
      /**
       * 查找最小结点：返回node为根结点的二叉树的最小结点。
       *
       * @param node the node
       * @return the node
       */
      private Node<V> minimum(Node<V> node) {
          if (node == null) {
              return null;
          }
          while (node.left != null) {
              node = node.left;
          }
          return node;
      }

参考资料：
https://blog.csdn.net/isea533/article/details/80345507