树——二叉搜索树

二叉搜索树

概述

　　随着计算机算力的提升和对数据结构的深入研究，二叉搜索树也不断被优化和扩展，例如AVL树、红黑树等。

特性

　　二叉搜索树（也称二叉排序树）是符合下面特征的二叉树：

1. 　　树节点增加 key 属性，用来比较谁大谁小，key 不可以重复；
2. 　　对于任意一个树节点，它的 key 比左子树的 key 都大，同时也比右子树的 key 都小。

　　查找的时间复杂度与树高相关，插入、删除也是如此。

　　注：

• 　　二叉搜索树 - 英文 binary search tree，简称 BST
• 　　二叉排序树 - 英文 binary ordered tree 或 binary sorted tree

  代码

  import java.util.ArrayList;
  import java.util.LinkedList;
  import java.util.List;
  /**
   * Binary Search Tree 二叉搜索树
   */
  @SuppressWarnings("all")
  public class BSTTree1 {
      BSTNode root; // 根节点
      static class BSTNode {
          int key;
          Object value;
          BSTNode left;
          BSTNode right;
          public BSTNode(int key) {
              this.key = key;
          }
          public BSTNode(int key, Object value) {
              this.key = key;
              this.value = value;
          }
          public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
              this.key = key;
              this.value = value;
              this.left = left;
              this.right = right;
          }
      }
      /**
       * 
  查找关键字对应的值
       *
       * @param key 关键字
       * @return 关键字对应的值
       */
      public Object get(int key) {
          BSTNode node = root;
          while (node != null) {
              if (key < node.key) {
                  node = node.left;
              } else if (node.key < key) {
                  node = node.right;
              } else {
                  return node.value;
              }
          }
          return null;
      }
      /**
       * 
  查找最小关键字对应值
       *
       * @return 关键字对应的值
       */
      public Object min() {
          return min(root);
      }
      private Object min(BSTNode node) {
          if (node == null) {
              return null;
          }
          BSTNode p = node;
          while (p.left != null) {
              p = p.left;
          }
          return p.value;
      }
      /**
       * 
  查找最大关键字对应值
       *
       * @return 关键字对应的值
       */
      public Object max() {
          return max(root);
      }
      private Object max(BSTNode node) {
          if (node == null) {
              return null;
          }
          BSTNode p = node;
          while (p.right != null) {
              p = p.right;
          }
          return p.value;
      }
      /**
       * 
  存储关键字和对应值
       *
       * @param key   关键字
       * @param value 值
       */
      public void put(int key, Object value) {
          root = doPut(root, key, value);
      }
      private BSTNode doPut(BSTNode node, int key, Object value) {
          if (node == null) {
              return new BSTNode(key, value);
          }
          if (key < node.key) {
              node.left = doPut(node.left, key, value);
          } else if (node.key < key) {
              node.right = doPut(node.right, key, value);
          } else {
              node.value = value;
          }
          return node;
      }
      /**
       * 
  查找关键字的前任值
       *
       * @param key 关键字
       * @return 前任值
       */
      public Object predecessor(int key) {
          BSTNode p = root;
          BSTNode ancestorFromLeft = null;
          while (p != null) {
              if (key < p.key) {
                  p = p.left;
              } else if (p.key < key) {
                  ancestorFromLeft = p;
                  p = p.right;
              } else {
                  break;
              }
          }
          // 没找到节点
          if (p == null) {
              return null;
          }
          // 找到节点 情况1：节点有左子树，此时前任就是左子树的最大值
          if (p.left != null) {
              return max(p.left);
          }
          // 找到节点 情况2：节点没有左子树，若离它最近的、自左而来的祖先就是前任
          return ancestorFromLeft != null ?
                  ancestorFromLeft.value : null;
      }
      /**
       * 
  查找关键字的后任值
       *
       * @param key 关键字
       * @return 后任值
       */
      public Object successor(int key) {
          BSTNode p = root;
          BSTNode ancestorFromRight = null;
          while (p != null) {
              if (key < p.key) {
                  ancestorFromRight = p;
                  p = p.left;
              } else if (p.key < key) {
                  p = p.right;
              } else {
                  break;
              }
          }
          // 没找到节点
          if (p == null) {
              return null;
          }
          // 找到节点 情况1：节点有右子树，此时后任就是右子树的最小值
          if (p.right != null) {
              return min(p.right);
          }
          // 找到节点 情况2：节点没有右子树，若离它最近的、自右而来的祖先就是后任
          return ancestorFromRight != null ?
                  ancestorFromRight.value : null;
      }
      /**
       * 
  根据关键字删除
       *
       * @param key 关键字
       * @return 被删除关键字对应值
       */
  //    public Object remove(int key) {
  //        ArrayList