3分钟火速手写一个二叉查找树，搞快点。

女爷i 2023-10-07 21:27 14阅读 0赞

#### 文章目录 ####

*   *  定义
     *  实现
     *  完整代码
     *  测试
     *  问题

因为二叉查找树的原理和实现比较简单，所以我们简单了解一下最基本的概念，就直接开始写代码。

### 定义 ###

> **二叉查找树(Binary Search Tree，BST)**，又叫做二叉排序树、二叉搜索树，是一种对查找和排序都有用的特殊二叉树。

> 二叉查找树或是空树，或是满足如下三个性质的二叉树：
> 
>  *  若其左子树非空，则左子树上所有节点的值都小于根节点的值 若其右子树非空，则右子树上所有节点的值都大于根节点的值 其左右子树都是一棵二叉查找树
>  *  二叉查找树的特性：左子树<根<右子树，即二叉查找树的中序遍历是一个递增序列。

### 实现 ###

树吗，无非查找，新增和删除。

首先定义一下节点的结构：

class BSTreeNode<K, V> {
        
    
           /**
            * 键值
            */
           private K nodeKey;
    
           /**
            * 值
            */
           private V nodeValue;
    
           /**
            * 左节点引用
            */
           private BSTreeNode<K, V> left;
    
           /**
            * 右节点引用
            */
           private BSTreeNode<K, V> right;
    
           /**
            * 父节点引用
            */
           private BSTreeNode<K, V> parent;
    
       }

对于查找，看看谁大谁小，递归慢慢找呗：

/**
       * 给定一个根节点，根据Key搜索某一个节点
       * 时间复杂度和二叉树的层数有关，所以时间复杂度为O(Logn)
       *
       * @param root 根节点引用
       * @param key  需要搜索的值
       * @return 节点
       */
      private BSTreeNode<K, V> indexSearch(BSTreeNode<K, V> root, K key) {
        
          //如果当前的根节点为null，返回空节点
          if (root == null) {
        
              return null;
          }
          // 如果当前节点key大于待搜索值，那么向左查找，反之，向右查找。
          if (root.nodeKey.compareTo(key) > 0) {
        
              return indexSearch(root.left, key);
          } else if (root.nodeKey.compareTo(key) < 0) {
        
              return indexSearch(root.right, key);
          } else return root;
      }

对于新增，先找到在哪增加，然后就加进去呗，引用换一换就好了：

/**
     * 新增node
     *
     * @param root    root
     * @param newNode 新增的节点
     */
    void insertNode(BSTreeNode<K, V> root, BSTreeNode<K, V> newNode) {
        
    
        // 如果当前根节点为null，将当前根节点引用只想新的node节点
        if (root == null) {
        
            firstRoot = newNode;
            return;
        }
    
        // 如果当前根节点key大于新增的节点key，则向当前节点的左节点进行操作
        if (root.nodeKey.compareTo(newNode.nodeKey) > 0) {
        
            // 如果当前根节点的左节点为null，则将当前根节点的左节点引用指向新增的节点，
            // 否则进行递归，直到左节点尽头为止
            if (root.left == null) {
        
                root.left = newNode;
                newNode.parent = root;
            } else insertNode(root.left, newNode);
        } else if (root.nodeKey.compareTo(newNode.nodeKey) < 0) {
        
            // 如果当前根节点key小于新增的节点key，则向当前节点的右节点进行操作，
            // 如果右节点为空，则将当前根节点的右节点引用指向新增的节点，
            // 否则进行递归，直到右节点尽头为止
            if (root.right == null) {
        
                root.right = newNode;
                newNode.parent = root;
            } else insertNode(root.right, newNode);
        }
    
    }

删除可能情况多一些，不过注释写的清清楚楚：

/**
      * 删除node
      *
      * @param key key
      */
     private void removeNode(K key) {
        
    
         // 根据key找到节点所在的位置
         BSTreeNode<K, V> search = indexSearch(firstRoot, key);
         // 如果找不到，直接返回
         if (search == null) {
        
             return;
         }
    
         // 将要删除的节点的父节点
         BSTreeNode<K, V> parent = search.parent;
         // 如果父节点为空，说明没有节点或者只有一个根节点，则将根节点置为空即可
         // 否则，将分为3种情况：
         //     1. 删除的节点没有左右节点，直接删除即可
         //     2. 删除的节点有左节点，没有右节点，那么需要将删除节点的父节点的左/右节点指向删除节点的左节点，
         //        删除节点的左节点的父节点需要指向删除节点的父节点
         //     3. 删除的节点有右节点，没有左节点，那么需要将删除节点的父节点的左/右节点指向删除节点的右节点，
         //        删除节点的右节点的父节点需要指向删除节点的父节点
         //     4. 删除的节点有左右节点，那么需要找到当前节点的中序前序节点或中序后继节点，替换掉当前节点，包括key和value，
         //        再删掉这个当前节点的中序前序节点或中序后继节点
         if (parent == null) {
        
             firstRoot = null;
         } else {
        
             //     1. 删除的节点没有左右节点，直接删除即可
             if (search.left == null && search.right == null) {
        
                 if (parent.left == search) {
        
                     parent.left = null;
                 } else if (parent.right == search) {
        
                     parent.right = null;
                 }
             }
    
             //     2. 删除的节点有左节点，没有右节点，那么需要将删除节点的父节点的左/右节点指向删除节点的左节点，
             //        删除节点的左节点的父节点需要指向删除节点的父节点
             if (search.right == null) {
        
    
                 if (parent.left == search) {
        
                     parent.left = search.left;
                     search.left.parent = parent;
    
                 } else if (parent.right == search) {
        
                     parent.right = search.left;
                     search.left.parent = parent;
                 }
    
             }
             //     3. 删除的节点有右节点，没有左节点，那么需要将删除节点的父节点的左/右节点指向删除节点的右节点，
             //        删除节点的右节点的父节点需要指向删除节点的父节点
             if (search.left == null) {
        
    
                 if (parent.left == search) {
        
                     parent.left = search.right;
                     search.right.parent = parent;
    
                 } else if (parent.right == search) {
        
                     parent.right = search.right;
                     search.right.parent = parent;
                 }
             }
    
             //     4. 删除的节点有左右节点，那么需要找到当前节点的中序前序节点或中序后继节点，替换掉当前节点，包括key和value，
             //        再删掉这个当前节点的中序前序节点或中序后继节点
             if (search.left != null && search.right != null) {
        
    
                 BSTreeNode<K, V> left = search.left;
                 while (left.right != null) {
        
                     left = left.right;
                 }
                 search.nodeKey = left.nodeKey;
                 search.nodeValue = left.nodeValue;
                 removeNode(left.nodeKey);
             }
         }
     }

### 完整代码 ###

/**
     * 二叉树
     *
     * @param <K> K
     * @param <V> V
     */
    public class BSTreeMap<K extends Comparable<K>, V> {
        
    
        /**
         * 原始根节点
         */
        private BSTreeNode<K, V> firstRoot;
    
        /**
         * 根据Key搜索某一个节点
         *
         * @param key 需要搜索的值
         * @return 节点值
         */
        public V get(K key) {
        
            // 如果节点不存在，则返回空
            if (indexSearch(firstRoot, key) == null) {
        
                return null;
            }
            return indexSearch(firstRoot, key).nodeValue;
        }
    
        /**
         * 存值
         *
         * @param key   key
         * @param value value
         */
        public void put(K key, V value) {
        
    
            // 将key和value封装成node对象
            BSTreeNode<K, V> newNode = new BSTreeNode<K, V>(key, value);
            insertNode(firstRoot, newNode);
        }
    
        /**
         * 根据key删除node节点
         *
         * @param key key
         */
        public void delete(K key) {
        
            removeNode(key);
        }
    
        /**
         * 新增node
         *
         * @param root    root
         * @param newNode 新增的节点
         */
        void insertNode(BSTreeNode<K, V> root, BSTreeNode<K, V> newNode) {
        
    
            // 如果当前根节点为null，将当前根节点引用只想新的node节点
            if (root == null) {
        
                firstRoot = newNode;
                return;
            }
    
            // 如果当前根节点key大于新增的节点key，则向当前节点的左节点进行操作
            if (root.nodeKey.compareTo(newNode.nodeKey) > 0) {
        
                // 如果当前根节点的左节点为null，则将当前根节点的左节点引用指向新增的节点，
                // 否则进行递归，直到左节点尽头为止
                if (root.left == null) {
        
                    root.left = newNode;
                    newNode.parent = root;
                } else insertNode(root.left, newNode);
            } else if (root.nodeKey.compareTo(newNode.nodeKey) < 0) {
        
                // 如果当前根节点key小于新增的节点key，则向当前节点的右节点进行操作，
                // 如果右节点为空，则将当前根节点的右节点引用指向新增的节点，
                // 否则进行递归，直到右节点尽头为止
                if (root.right == null) {
        
                    root.right = newNode;
                    newNode.parent = root;
                } else insertNode(root.right, newNode);
            }
    
        }
    
        /**
         * 删除node
         *
         * @param key key
         */
        private void removeNode(K key) {
        
    
            // 根据key找到节点所在的位置
            BSTreeNode<K, V> search = indexSearch(firstRoot, key);
            // 如果找不到，直接返回
            if (search == null) {
        
                return;
            }
    
            // 将要删除的节点的父节点
            BSTreeNode<K, V> parent = search.parent;
            // 如果父节点为空，说明没有节点或者只有一个根节点，则将根节点置为空即可
            // 否则，将分为3种情况：
            //     1. 删除的节点没有左右节点，直接删除即可
            //     2. 删除的节点有左节点，没有右节点，那么需要将删除节点的父节点的左/右节点指向删除节点的左节点，
            //        删除节点的左节点的父节点需要指向删除节点的父节点
            //     3. 删除的节点有右节点，没有左节点，那么需要将删除节点的父节点的左/右节点指向删除节点的右节点，
            //        删除节点的右节点的父节点需要指向删除节点的父节点
            //     4. 删除的节点有左右节点，那么需要找到当前节点的中序前序节点或中序后继节点，替换掉当前节点，包括key和value，
            //        再删掉这个当前节点的中序前序节点或中序后继节点
            if (parent == null) {
        
                firstRoot = null;
            } else {
        
                //     1. 删除的节点没有左右节点，直接删除即可
                if (search.left == null && search.right == null) {
        
                    if (parent.left == search) {
        
                        parent.left = null;
                    } else if (parent.right == search) {
        
                        parent.right = null;
                    }
                }
    
                //     2. 删除的节点有左节点，没有右节点，那么需要将删除节点的父节点的左/右节点指向删除节点的左节点，
                //        删除节点的左节点的父节点需要指向删除节点的父节点
                if (search.right == null) {
        
    
                    if (parent.left == search) {
        
                        parent.left = search.left;
                        search.left.parent = parent;
    
                    } else if (parent.right == search) {
        
                        parent.right = search.left;
                        search.left.parent = parent;
                    }
    
                }
                //     3. 删除的节点有右节点，没有左节点，那么需要将删除节点的父节点的左/右节点指向删除节点的右节点，
                //        删除节点的右节点的父节点需要指向删除节点的父节点
                if (search.left == null) {
        
    
                    if (parent.left == search) {
        
                        parent.left = search.right;
                        search.right.parent = parent;
    
                    } else if (parent.right == search) {
        
                        parent.right = search.right;
                        search.right.parent = parent;
                    }
                }
    
                //     4. 删除的节点有左右节点，那么需要找到当前节点的中序前序节点或中序后继节点，替换掉当前节点，包括key和value，
                //        再删掉这个当前节点的中序前序节点或中序后继节点
                if (search.left != null && search.right != null) {
        
    
                    BSTreeNode<K, V> left = search.left;
                    while (left.right != null) {
        
                        left = left.right;
                    }
                    search.nodeKey = left.nodeKey;
                    search.nodeValue = left.nodeValue;
                    removeNode(left.nodeKey);
                }
            }
        }
    
        /**
         * 给定一个根节点，根据Key搜索某一个节点
         * 时间复杂度和二叉树的层数有关，所以时间复杂度为O(Logn)
         *
         * @param root 根节点引用
         * @param key  需要搜索的值
         * @return 节点
         */
        private BSTreeNode<K, V> indexSearch(BSTreeNode<K, V> root, K key) {
        
            //如果当前的根节点为null，返回空节点
            if (root == null) {
        
                return null;
            }
            // 如果当前节点key大于待搜索值，那么向左查找，反之，向右查找。
            if (root.nodeKey.compareTo(key) > 0) {
        
                return indexSearch(root.left, key);
            } else if (root.nodeKey.compareTo(key) < 0) {
        
                return indexSearch(root.right, key);
            } else return root;
        }
    
        /**
         * 内部类-node
         *
         * @param <K> K
         * @param <V> V
         */
        static class BSTreeNode<K, V> {
        
    
            /**
             * 键值
             */
            private K nodeKey;
    
            /**
             * 值
             */
            private V nodeValue;
    
            /**
             * 左节点引用
             */
            private BSTreeNode<K, V> left;
    
            /**
             * 右节点引用
             */
            private BSTreeNode<K, V> right;
    
            /**
             * 父节点引用
             */
            private BSTreeNode<K, V> parent;
    
            public BSTreeNode(K nodeKey, V nodeValue) {
        
                this.nodeKey = nodeKey;
                this.nodeValue = nodeValue;
    
            }
    
            @Override
            public String toString() {
        
                return "BSTreeNode{" +
                        "nodeKey=" + nodeKey +
                        '}';
            }
    
        }
    }

### 测试 ###

![在这里插入图片描述][a481e713dbe04389a9eb69011ddc41e7.png]

### 问题 ###

BST有个最大的问题，就是树的结构不容易平衡，如果我们存入的序列都是有序的，那不成了链表了，链表的时间复杂度肯定就不能达到O(Logn)，但是呢，我们让它平衡不就得了。所以啊，红黑树出现了，我们等一个失眠的夜，手写一下红黑树，让失眠的夜不再失眠。

[a481e713dbe04389a9eb69011ddc41e7.png]: https://img-blog.csdnimg.cn/a481e713dbe04389a9eb69011ddc41e7.png