二叉搜索树基本操作的实现

不念不忘少年蓝@ 2022-06-02 02:46 215阅读 0赞

对线性表比较熟悉的读者会很清楚线性表的查找性能。无论是链式存储或是顺序存储，在最坏情况或是平均情况下都查需要线性时间。另外，对于堆和栈两种特殊的线性表甚至不提供对任一元素的查找接口。因此，若需要对象集合的组成可以高效地动态调整，又能高效的查找，则线性表很难胜任。

**高效率的动态修改和高效率的静态查找，是否能够兼顾？如果能，需要采取什么样的数据结构。**

笔者接下来的几篇博文，将回答这个问题。即采用树式结构—搜索树。

搜索树的数据结构的变种非常多，各具特色各有所长，也有各自的适用范围，笔者将仅可能的将所接触到的搜索树全部写入博文中。主要涉及到的如下图所述：  
![这里写图片描述][70]

本篇将树式查找的总体构思，基本算法以及数据结构，通过对二分查找策略的抽象与推广，定义并实现二叉搜索树。尽管读者可能看到本文实现的二叉搜索树与线性表的二分查找的效率没有明显的提示。但这种基本半线性的树形结构的这一总体构思，是所有高级搜索树的立足点。比如后续会涉及到到理想平衡和适度平衡等概念，并相应地引入和实现 AVL 树这一典型的平衡二叉搜索树。借助精巧的平衡调整算法，AVL 树可以保证，即便是在最坏情况下，单次动态修改和静态查找也均可以在 0 (logn）时间内完成。这样，以上关于兼高效率的动态修改和高效率的静态查找的问题，就有了答案。

### 二叉搜索树的特性 ###

若二叉树中各节点支持大小比较，则对于树结构做如下的限制：  
**任一节点r的左子树(如果存在)均小于节点r，右子树(如果存在)均大于节点r**  
如下图所示：  
![这里写图片描述][SouthEast]

如果对一颗二叉搜索树进行一次中序遍历，则可将该树转换为按严格大小排序的线性序列。

二叉搜索树的模版代码如下：

package searchTree;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    public class SearchTree {
        
        private TreeNode root;
    
        public SearchTree() {
            this.root = new TreeNode();
        }
    
        public SearchTree(Double data) {
            this.root = new TreeNode(data);
        }
    
        public SearchTree(TreeNode root) {
            this.root = root;
        }
    
        /**
         * 添加子节点
         * @throws Exception 
         */
        public TreeNode addNode(Double data) {
        }
    
        /**
         * 查找某个节点
         * @param 要查找的节点的值
         * @return
         */
        public TreeNode search(Double data) {
        }
    
        /**
         * 删除某个节点
         * @parent 要删除的节点的值
         *
         */
        public TreeNode delete(Double data) {
        }
    
       /**
        * 中序遍历中的后继节点 
        * @param 要查找后继节点的节点
        */
        public TreeNode nextForIn(TreeNode node) {
        }
    
       /**
        *中序遍历
        */
        public List<TreeNode> in() {
        }
    
        private void swap(TreeNode dataOne, TreeNode dataTwo) {
            Double tmp = dataOne.data;
            dataOne.data = dataTwo.data;
            dataTwo.data = tmp;
        }
    }

节点定义如下：

public class TreeNode {
            private Double data;
            private TreeNode parent;
            private TreeNode left;
            private TreeNode right;
    
            public TreeNode() {
    
            }
    
            public TreeNode(Double data) {
                this.data = data;
            }
    
            public TreeNode(Double data, TreeNode parent) {
                this.data = data;
                this.parent = parent;
            }
    
            public TreeNode(Double data, TreeNode parent, TreeNode left, TreeNode right) {
                this.data = data;
                this.parent = parent;
                this.left = left;
                this.right = right;
            }
    
            public Double getData() {
                return data;
            }
    
            public void setData(Double data) {
                this.data = data;
            }
    
            public TreeNode getParent() {
                return parent;
            }
    
            public void setParent(TreeNode parent) {
                this.parent = parent;
            }
    
            public TreeNode getLeft() {
                return left;
            }
    
            public void setLeft(TreeNode left) {
                this.left = left;
            }
    
            public TreeNode getRight() {
                return right;
            }
    
            public void setRight(TreeNode right) {
                this.right = right;
            }
    
            @Override
            public String toString() {
                Double leftData = left!=null? left.data: null;
                Double rightData = right!=null? right.data: null;
                Double parentData = parent!=null? parent.data: null;
                return "<data:" + data + ";left:" + leftData + ";right:" + rightData+";parent:" + parentData+">";
            }
        }

### 二叉搜索树的查找算法及实现 ###

二叉搜索树的查找的算法，亦采用了与二分法一致减而治之的思路与策略，其执行过程可描述为：  
**从树根出发，逐步地缩小查找范围，直到发现目标（成功）或缩小至空树（失败)**  
例如：在上图7.5中查找22的过程如下：

首先，经与根节点16比较确认目标更大，故深入右子树25递归查找。经比较发 现目标更小，故继续深入左子树19递归查找;经再次比较确认目标更大后， 深入右子树22递归查找; 最终在节点22处匹配，查找成功。

查找代码如下：

/**
         * 查找某个节点
         * @param 要查找的节点的值
         * @return TreeNode  如果返回值的data为空则查询失败
         */
        public TreeNode search(Double data) {
    
            TreeNode parent = null;
            TreeNode child = root;
            TreeNode res = null;
            do {            
                if (child.data.equals(data)) {
                    res = child;
                } else if (child.data > data) {
                    parent = child;
                    // 搜索左子树
                    child = child.left;
                } else if (child.data < data) {
                    parent = child;
                    // 搜索右子树
                    child = child.right;
                }
            } while (child != null && res==null);
    
            if(res == null) {
                res = new TreeNode(null, parent);
            }
            //返回对象还包含了该目标的parent.如果该节点未被查找到，即data为null，parent则为要插入该节点时的parent，此时这个parent一定是个叶子节点
            return res;
        }

**查询算法效率：**  
二叉树中的每一层，查找算法至多访问一个节点，且只需要常数时间，故总体所需时间正比于查找路径的长度，或最终返回节点的深度。在最差的情况下，规模为n的二叉树，深度也为n。此时二叉树退化为一条单链。此时查询需O(n)。此时，不难看出，要控制二叉搜索树的查找性能，需要控制二叉树搜索的高度。后续笔者介绍平衡二叉搜索树时，正是基于这种思路实现的。

### 二叉搜索树的插入算法及实现 ###

为在二叉搜索树中插入一个节点，须先按上述的search方法来找到该节点的目前是叶子节点的父节点，并根据该值与父节点的大小来决定作为其左孩子还是右孩子。  
如下图所示在二叉搜索树中插入40节点和55节点的过程：  
![这里写图片描述][SouthEast 1]  
**\_hot即为search(Double data)方法返回的节点parent**

代码实现：

/**
         * 添加子节点
         * @throws Exception 
         */
        public TreeNode addNode(Double data) {
            TreeNode parent = null;
            TreeNode inTree = this.search(data);
    
            if(inTree.data != null) {
                return inTree;
            }
    
            inTree.data = data;
            if(inTree.data < inTree.parent.data) {
                inTree.parent.left = inTree;
            }else if(inTree.data > inTree.parent.data) {
                inTree.parent.right = inTree;
            }
    
            return inTree;
        }

**插入算法效率：**

节点插入对新节点与新节点parent的关系维护消耗时间为O(1)，该方法的主要消耗还是在search()方法上，为O(n)。

### 二叉搜索树的删除算法及实现 ###

与插入一样，删除节点也需要先通过search方法判断是否存在与树中。然后再进行删除操作，删除操作相比于插入操作比较复杂。分两种情况考虑(即仅有一个孩子和两个孩子的情况)：

**单孩子情况**

单孩子情况比较简单，根据二叉搜索树的特性，某个节点的子树中的全部节点必是全部大小或小于该节点的。  
因此若被删除的节点仅有左孩子，则将该左孩子的parent指向被删除的节点的父节点即可(当然，被删除的节点的父节点的左孩子即为该左孩子)。同理若被删除的节点仅有右孩子，则将该右孩子的parent指向被删除的节点的父节点即可。

**双孩子情况**

双孩子的情况比较复杂，若要删除一个两个孩子都存在的节点，则首先需要找到该节点在中序遍历中的直接后继，根据中序遍历的特性，直接后续必须左孩子。将被删除的节点的数据data与该节点交换后，按上述单孩子情况将该直接后继删除即可。

图示如下，分别删除单孩子的69节点和具有双孩子的36节点：  
![这里写图片描述][SouthEast 2]

实现代码：

/**
         * 删除某个节点
         * @parent 要删除的节点的值
         *
         */
        public TreeNode delete(Double data) {
            TreeNode inTree = this.search(data);
            TreeNode next = null; //被删除节点的位置
    
            if(inTree.data == null) {
                return null;
            }
    
            TreeNode hot = inTree.parent;
    
            if(inTree.left == null) {
    
                //接替被删除的节点的子树
                if(hot.left == inTree) {
                    hot.left.setLeft(inTree.right);
                }else {
                    hot.right.setRight(inTree.right);
                }
    
                //开始孤立inTree
                inTree.right.parent = hot;
                inTree.parent = null;
                inTree.right = null;
    
                return inTree;
            }else if(inTree.right == null) {
    
                if(hot.left == inTree) {
                    hot.left.setLeft(inTree.left);
                }else { 
                    hot.right.setRight(inTree.left);
                }
    
                //开始孤立inTree
                inTree.left.parent = hot;
                inTree.parent = null;
                inTree.left = null;
    
                return inTree;
            }else {
    
                //当左右节点都存在时，先获取其在中序遍历中的直接后继，直接后继next一定没有左孩子
                next= this.nextForIn(inTree);
                swap(inTree, next);
                //如果其直接后继为其孩子(右孩子)，则被删除的节点之后的节点属于next的右孩子
                if(inTree == next.parent) {
                    next.parent.right = next.right;
                }else {
                //如果其直接后继不是其孩子，则是其右孩子的左子树的某个节点，则被删除的节点之后的节点属于next的左孩子
                    next.parent.left = next.right;
                }
    
                //开始孤立next (next无左孩子，也一定是next.parent.left)
                next.parent.left = next.right;
                if(next.right!=null) {
                  next.right.parent = next.parent;
                }
                next.parent = null;
                next.right = null;
    
    
                return next;
            }
        }

**删除算法效率：**

节点删除的关系维护消耗时间为O(1)，该方法的主要消耗还是在search()方法上，为O(n)。

通过分析查找，插入，删除这三个基本操作，不难看出，算法的瓶颈完全在于树的高度上，如果二叉树退化为一条单链。那么二叉树的效率就和线性表没什么区别了，笔者接下来的文章会介绍平衡二叉树，即严格控制树高的二叉搜索树，届时，查询性能会提升到O()

[70]: /images/20220602/91480f4f98934097b9ed5c3483198267.png
[SouthEast]: /images/20220602/454fe155baae4acc90d21f40dcda6357.png
[SouthEast 1]: /images/20220602/d292eaaf54354898a0abc0ceadd647af.png
[SouthEast 2]: /images/20220602/70cd9015457b45c187c077a171fdf0f3.png