Java实现二分查找树及其相关操作

二分查找树(Binary Search Tree)的基本操作有搜索、求最大值、求最小值、求前驱、求后继、插入及删除。

对二分查找树的进行基本操作所花费的时间与树的高度成比例。例如有n个节点的完全二叉树,对它进行的基本操作的时间复杂度为O(logn)。然而,如果树是一个有n个节点的线性的链,则在这种情况下的时间复杂度为O(n)。

1、什么是二分查找树

二分查找树是一种有组织的二叉树。我们可以通过链接节点表示这样一棵树。每个节点包含键(key),数据(data),左子节点(left),右子节点(right),父节点(parent)这五种属性。

如果一个节点没有父节点或某个子结点,则其对应的属性的值为null。

创建一个Node.java文件,用如下代码表示节点:

public class Node {
    public int key;
    public int data;
    public Node left;
    public Node right;
    public Node parent;

    public Node(){}

    public Node(int key) {
        this.key = key;
    }
}

创建一个BinarySearchTree.java文件,用如下代码表示二分查找树:

public class BinarySearchTree {
    public Node root;
}

接下来,会逐步补充代码。

对于存储在二分查找树中的键,必须满足下面这个条件(二分查找树特点)

对于二叉树中的任一节点n,如果left是n左子树中的任何一个节点,有left.key <= n.key;如果right是n右子树中的任一节点,则有n.key<=right.key。

如果我们中序遍历二分查找树,能升序打印出所有的键(key)。

可在BinarySearchTree.java文件中加上如下代码实现中序遍历:

private void innerWalk(Node node) {
        if(node != null) {
            innerWalk(node.left);
            System.out.print(node.key + " ");
            innerWalk(node.right);
        }
    }

    public void innerWalk() {
        this.innerWalk(this.root);
        System.out.println();
    }

2、查询二分查找树

2.1、搜索

在二分查找树中搜索键为key的结点,如果找到,则返回该结点,否则,返回null。可利用二分查找树的特性来查找。

可在BinarySearchTree.java文件中加上如下代码实现搜索:

public Node search(int key) {
        Node pointer = this.root;
        while (pointer != null && pointer.key != key) {
            pointer = key < pointer.key ? pointer.left : pointer.right;
        }
        return pointer;
    }

2.2、最小值与最大值

求键最小的节点,可根据二叉树的特点,从根结点开始,遍历跟踪其左子节点,直到最后一个。

可在Node.java文件中加上如下代码实现:

 public Node minimum() {
        Node pointer = this;
        while(pointer.left != null){
            pointer = pointer.left;
        }
        return pointer;
    }

在BinarySearchTree.java文件中加上如下代码:

public Node minimum() {
        return this.root.minimum();
    }

求键最大的节点,可根据二叉树的特点,从根结点开始,遍历跟踪其右子节点,直到最后一个。

可在Node.java文件中加上如下代码实现:

 public Node maximum() {
        Node pointer = this;
        while(pointer.right != null) {
            pointer = pointer.right;
        }
        return pointer;
    }

在BinarySearchTree.java文件中加上如下代码:

public Node minimum() {
        return this.root.maximum();
    }

2.3、前驱与后继

给定一个二分查找树中的节点,有时我们需要发现它在树中所有结点按键升序排序的情况下的直接后继(后面第一个)。

如果树中所有的键是不同的,结点n的直接后继是大于n.key的最小结点。

如果该结点有右节点,则其直接后继是其右子树键最小的那个结点。如果该结点则判断该结点是其父节点的左子节点还是其右子节点。

如果是左子节点,则返回其父节点。如果是右子节点,判断其父节点的其父节点的父节点的左子节点还是右子节点,以此类推。

如果找不到,则返回null。

可在Node.java文件中加上如下实现代码:

public Node successor() {
        Node pointer = this;
        if (pointer.right != null)
            return pointer.right.minimum();
        Node parentPointer = pointer.parent;
        while (parentPointer != null && parentPointer.right == pointer) {
            pointer = parentPointer;
            parentPointer = parentPointer.parent;
        }
        return pointer;
    }

一个节点的直接前继是指树中所有结点按键升序排序的情况下,该节点的前面第一个。求直接前继的与求直接后继是对称的。

可在Node.java文件中加上如下实现代码:

 public Node predecessor() {
        Node pointer = this;
        if (pointer.left != null)
            return pointer.left.maximum();
        Node parentPointer = pointer.parent;
        while (parentPointer != null && parentPointer.left == pointer) {
            pointer = parentPointer;
            parentPointer = parentPointer.parent;
        }
        return pointer;
    }

3、插入与删除

插入与删除会导致二分查找树发生改变,但必须保持其特点。

3.1、插入

在树中找到一个键(key)最接近要插入结点键(key)的结点,且有可以插入的位置,然后插入合适的位置。

可在BinarySearchTree.java文件中加上如下实现代码:

 public void insert(Node node) {
        Node pointer = this.root;
        Node parentPointer = null;
        while (pointer != null) {
            parentPointer = pointer;
            pointer = node.key < pointer.key ? pointer.left : pointer.right;
        }
        node.parent = parentPointer;
        if (parentPointer == null)
            this.root = node;
        else if (node.key < parentPointer.key) {
            parentPointer.left = node;
        } else {
            parentPointer.right = node;
        }
    }

3.2、删除

删除节点后,我门要保持二分查找树的特点。

如果要删除节点没有任何子节点,直接可以删除它,不用做任何处理。

如果要删除节点只有一个左子树,可以用左子树的根节点代替要删除节点,也可以用左子树中键(key)最大的节点来代替要删除节点。

如果要删除结点只有一个右子树,可以用右子树的根节点代替要删除节点,也可以用右子树中键(key)最小的结点来代替要删除结点。

如果要删除结点既有左子树,又有右子树,可以用左子树中键(key)最大的结点代替要删除结点,也可以用右子树中键最小的结点代替要删除结点。

假设要从二分查找树tree中删除节点node,一种删除方法的具体步骤如下:

  • 如果node没有左子节点,然后我们可以用node的右子节node.right点代替node,node.right可能是或可能不是null。
  • 如果node只有左子节点node.left,则我们用node.left代替node。
  • 如果node有左子节点node.left和右子节点node.right。我么要发现node的直接后继s(node右子树中键最小的结点,它没有左子节点),s在node右子树中,然后用s代替node。这里要考虑下面两种情况:

如果s是node的右子节点,可以用s代替node。
否则,用s的右子节点代替s,然后再用s代替node。

由于我们需要在二分查找树中替换子树的方法,可以先写一个替换子树的方法。

可在BinarySearchTree.java文件中加上如下实现代码:

/**
     * 用子树node2代替代替子树node1
     *
     * @param node1
     * @param node2
     */
    private void transplant(Node node1, Node node2) {
        if (node1.parent == null) {
            this.root = node2;
        } else if (node1.parent.left == node1) {
            node1.parent.left = node2;
        } else {
            node1.parent.right = node2;
        }

        if (node2 != null)
            node2.parent = node1.parent;
        node1.parent = null;
    }

接下来解释删除节点操作的代码实现。

可在BinarySearchTree.java文件中加上如下实现代码:

 public void delete(Node node) {
        if (node.left == null) {
            this.transplant(node, node.right);
        } else if (node.right == null) {
            this.transplant(node, node.left);
        } else {
            Node successor = node.successor();
            if (successor.parent != node) {
                this.transplant(successor, successor.right);
                successor.right = node.right;
                successor.right.parent = successor;
            }
            this.transplant(node, successor);
            successor.left = node.left;
            successor.left.parent = successor;
        }
    }

4、完整代码

Node.java文件

public class Node {
    public int key;
    public int data;
    public Node left;
    public Node right;
    public Node parent;

    public Node() {
    }

    public Node(int key) {
        this.key = key;
    }

    public Node minimum() {
        Node pointer = this;
        while (pointer.left != null)
            pointer = pointer.left;
        return pointer;
    }

    public Node maximum() {
        Node pointer = this;
        while (pointer.right != null)
            pointer = pointer.right;
        return pointer;
    }

    public Node successor() {
        Node pointer = this;
        if (pointer.right != null)
            return pointer.right.minimum();
        Node parentPointer = pointer.parent;
        while (parentPointer != null && parentPointer.right == pointer) {
            pointer = parentPointer;
            parentPointer = parentPointer.parent;
        }
        return pointer;
    }

    public Node predecessor() {
        Node pointer = this;
        if (pointer.left != null)
            return pointer.left.maximum();
        Node parentPointer = pointer.parent;
        while (parentPointer != null && parentPointer.left == pointer) {
            pointer = parentPointer;
            parentPointer = parentPointer.parent;
        }
        return pointer;
    }
}

BinarySearchTree.java文件

public class BinarySearchTree {
    public Node root;

    private void innerWalk(Node node) {
        if (node != null) {
            innerWalk(node.left);
            System.out.print(node.key + " ");
            innerWalk(node.right);
        }
    }

    public void innerWalk() {
        this.innerWalk(this.root);
        System.out.println();
    }

    public Node search(int key) {
        Node pointer = this.root;
        while (pointer != null && pointer.key != key) {
            pointer = key < pointer.key ? pointer.left : pointer.right;
        }
        return pointer;
    }

    public Node minimum() {
        return this.root.minimum();
    }

    public Node maximum() {
        return this.root.maximum();
    }

    public void insert(Node node) {
        Node pointer = this.root;
        Node parentPointer = null;
        while (pointer != null) {
            parentPointer = pointer;
            pointer = node.key < pointer.key ? pointer.left : pointer.right;
        }
        node.parent = parentPointer;
        if (parentPointer == null)
            this.root = node;
        else if (node.key < parentPointer.key) {
            parentPointer.left = node;
        } else {
            parentPointer.right = node;
        }
    }

    /**
     * 用子树node2代替代替子树node1
     *
     * @param node1
     * @param node2
     */
    private void transplant(Node node1, Node node2) {
        if (node1.parent == null) {
            this.root = node2;
        } else if (node1.parent.left == node1) {
            node1.parent.left = node2;
        } else {
            node1.parent.right = node2;
        }

        if (node2 != null)
            node2.parent = node1.parent;
        node1.parent = null;
    }

    public void delete(Node node) {
        if (node.left == null) {
            this.transplant(node, node.right);
        } else if (node.right == null) {
            this.transplant(node, node.left);
        } else {
            Node successor = node.successor();
            if (successor.parent != node) {
                this.transplant(successor, successor.right);
                successor.right = node.right;
                successor.right.parent = successor;
            }
            this.transplant(node, successor);
            successor.left = node.left;
            successor.left.parent = successor;
        }
    }
}

5、演示

演示代码

public class Test01 {
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);

        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(n3);
        bst.insert(n4);
        bst.insert(n2);
        bst.insert(n1);
        bst.insert(n5);

        System.out.println("bst.minimum().key: " + bst.minimum().key);
        System.out.println("bst.maximum().key: " + bst.maximum().key);
        System.out.println("n3.successor().key: " + n3.successor().key);
        System.out.println("n3.predecessor().key: " + n3.predecessor().key);
        System.out.println("bst.search(4).key: " + bst.search(4).key);

        System.out.print("tree: ");
        bst.innerWalk();
        System.out.print("delete n3: ");
        bst.delete(n3);
        bst.innerWalk();
        System.out.print("delete n2: ");
        bst.delete(n2);
        bst.innerWalk();
        System.out.print("delete n1: ");
        bst.delete(n1);
        bst.innerWalk();
        System.out.print("delete n4: ");
        bst.delete(n4);
        bst.innerWalk();
        System.out.print("delete n5: ");
        bst.delete(n5);
        bst.innerWalk();
    }
}

结果

bst.minimum().key: 1
bst.maximum().key: 5
n3.successor().key: 4
n3.predecessor().key: 2
bst.search(4).key: 4
tree: 1 2 3 4 5
delete n3: 1 2 4 5
delete n2: 1 4 5
delete n1: 4 5
delete n4: 5
delete n5:

到此这篇关于Java实现二分查找树及其相关操作的文章就介绍到这了,更多相关java二分查找树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java 中冒泡、二分、快速算法详解

    1.冒泡算法的原理: 冒泡排序算法的一般性策略:搜索整个值列,比较相邻元素,如果两者的相对次序不对,则交换它们,其结果是最大值"想水泡一样"移动到值列的最后一个位置上,这也是它在最终完成排序的值列中合适的位置.然后再次搜索值列,将第二大的值移动至倒数第二个位置上,重复该过程,直至将所有元素移动到正确的位置上. 下面是两个Java冒泡算法程序 2.冒泡代码如下: public class BubbleSort { public static void bubbleSort(int[] a

  • java实现二分法的完整代码

    二分法查找,顾名思义就是要将数据每次都分成两份然后再去找到你想要的数据,我们可以这样去想,二分法查找很类似与我们平时玩的猜价格游戏,当你报出一个价格时裁判会告诉你价格相对于真实值的高低,倘若是低了那我们一定会再说出一个略高的价格,反之亦然.在二分法查找时要求传入的数据必须已经有序,假设现在为升序,然后每次将所寻找的值与中间值(数组左边界+(右边界-左边界)/2)作比较,大了则去寻找中间值左侧数据,小则寻找中间值右侧数据. 二分法查找比较局限性的就是只能操作一个已经排序了的数组. 方法一 下面为一

  • java算法之二分查找法的实例详解

    java算法之二分查找法的实例详解 原理 假定查找范围为一个有序数组(如升序排列),要从中查找某一元素,如果该元素在此数组中,则返回其索引,否则返回-1.通过数组长度可取出中间位置元素的索引,将其值与目标值比较,如果中间位置元素值大于目标值,则在左部分进行查找,如果中间位置值小于目标值,则在右部分进行查找,如此循环,直到结束.二分查找算法之所以快是因为它没有遍历数组的每个元素,而仅仅是查找部分元素就能找到目标或确定其不存在,当然前提是查找范围为有序数组. Java的简单实现 package me

  • java实现二分法查找出数组重复数字

    本文实例为大家分享了java实现二分法查找出数组重复数字的具体代码,供大家参考,具体内容如下 package offer; /** * 二分查找的思想来找到数组中重复的数字,时间复杂度在o(nlogn)-o(n^2) */ public class FindDuplicate3 { public static void main(String[] args) { int numbers[] = {0,1,2,3,4,4,6,7};//数组中的数 大小从0 到 numbers.length-1 f

  • Java实现的两种常见简单查找算法示例【快速查找与二分查找】

    本文实例讲述了Java实现的两种常见简单查找算法.分享给大家供大家参考,具体如下: 前言: 查找是指从一批记录当中找出满足制定条件的某一记录的过程. 在平常的程序的编写当中很多时候时用得上的,这里简单介绍两个查找算法 1. 快速查找: 这个是相当简单的,以数组举例,就用一个for循环去查找数组中需要查找的数据 例子: public static boolean quickSearch(int a[], int x) { boolean f = false; int length = a.leng

  • Java实现二分查找树及其相关操作

    二分查找树(Binary Search Tree)的基本操作有搜索.求最大值.求最小值.求前驱.求后继.插入及删除. 对二分查找树的进行基本操作所花费的时间与树的高度成比例.例如有n个节点的完全二叉树,对它进行的基本操作的时间复杂度为O(logn).然而,如果树是一个有n个节点的线性的链,则在这种情况下的时间复杂度为O(n). 1.什么是二分查找树 二分查找树是一种有组织的二叉树.我们可以通过链接节点表示这样一棵树.每个节点包含键(key),数据(data),左子节点(left),右子节点(ri

  • LintCode-排序列表转换为二分查找树分析及实例

    给出一个所有元素以升序排序的单链表,将它转换成一棵高度平衡的二分查找树 您在真实的面试中是否遇到过这个题? 分析:就是一个简单的递归,只是需要有些链表的操作而已 代码: /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } * Defin

  • 两种java实现二分查找的方式

    目录 1.二分查找算法思想 2.二分查找图示说明 3.二分查找优缺点 3.java代码实现 3.1 使用递归实现 3.1 不使用递归实现(while循环) 3.3 测试 4.时间复杂度 5.空间复杂度 起初在数据结构中学习递归时实现二分查找,实际上不用递归也可以实现,毕竟递归是需要开辟额外的空间的来辅助查询.本文就介绍两种方法 1.二分查找算法思想 有序的序列,每次都是以序列的中间位置的数来与待查找的关键字进行比较,每次缩小一半的查找范围,直到匹配成功. 一个情景:将表中间位置记录的关键字与查找

  • java 算法二分查找和折半查找

     java 算法二分查找与折半查找 折半查找 :首先数组是已经排好序的 实例代码: package com.hao.myrxjava; /** * 折半查找 :首先数组是已经排好序的 * * @author zhanghaohao * @date 2017/5/15 */ public class HalfDivision { /** * 循环实现 * * @param array 排好序的数组 * @param value 查找的值 * @return value在array的位置 */ pu

  • Java实现二分查找算法实例分析

    本文实例讲述了Java实现二分查找算法.分享给大家供大家参考.具体如下: 1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合

  • Java实现二分查找的变种

    本文实例为大家分享了Java实现二分查找的变种,供大家参考,具体内容如下 普通二分查找: 先回顾一下普通的二分查找 注意:二分查找有这样一个问题:当数组中数有重复时,比如 {3,3,3,3} 这个数组,二分查找3时,返回的是arr[1],也就是说二分查找并不会返回3第一次出现的位置0. public class BinarySearch { public static <T extends Comparable<? super T>> int search(T arr[], T v

  • 简介二分查找算法与相关的Python实现示例

    二分查找Binary Search的思想: 以有序表表示静态查找表时,查找函数可以用二分查找来实现. 二分查找(Binary Search)的查找过程是:先确定待查记录所在的区间,然后逐步缩小区间直到找到或找不到该记录为止. 1二分查找的时间复杂度是O(log(n)),最坏情况下的时间复杂度是O(n). 假设 low 指向区间下界,high 指向区间上界,mid 指向区间的中间位置,则 mid  = (low + high) / 2; 具体过程: 1.先将关键字与 mid 指向的元素比较,如果相

  • Java数据结构学习之树

    一.树 1.1 概念 与线性表表示的一一对应的线性关系不同,树表示的是数据元素之间更为复杂的非线性关系. 直观来看,树是以分支关系定义的层次结构. 树在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可以用树的形象来表示. 简单来说,树表示的是1对多的关系. 定义(逻辑结构): 树(Tree)是n( n>=0 )个结点的有限集合,没有结点的树称为空树,在任意一颗非空树中: 有且仅有一个特定的称为根(root)的结点 . 当n>1的时,其余结点可分为 m( m>0 ) 个互不相交的

  • C语言编程中实现二分查找的简单入门实例

    架设有一个数组 v 已经按升序排列了,数组 v 有 n=20 个元素.数组中有个元素 x,如何知道 x 位于该数组的第几位呢? 解决这个问题的一个普遍方法就是二分查找法.下面是程序: #include <stdio.h> int binsearch(int x, int v[], int n); main() { int i, result, n; int wait; int x = 17; // 需要查找的数值 int v[19]; // 定义一个数组 // 给数组赋值 for(i = 0;

  • Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)

    目录 1.查找概述 2.顺序查找 3.二分查找 3.1 二分查找概述 3.2 二分查找实现 4.插值查找 4.1 插值查找概述 4.2 插值查找实现 5.斐波那契查找 5.1 斐波那契查找概述 5.2 斐波那契查找实现 5.3 总结 1.查找概述 查找表: 所有需要被查的数据所在的集合,我们给它一个统称叫查找表.查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合. 查找(Searching): 根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录).

随机推荐