文档章节

图解:二叉搜索树算法(BST)

泥瓦匠BYSocket
 泥瓦匠BYSocket
发布于 2016/07/16 10:48
字数 2053
阅读 85
收藏 5

摘要: 原创出处:www.bysocket.com 泥瓦匠BYSocket 希望转载,保留摘要,谢谢! “岁月极美,在于它必然的流逝” “春花 秋月 夏日 冬雪” — 三毛

一、树 & 二叉树

是由节点和边构成,储存元素的集合。节点分根节点、父节点和子节点的概念。 如图:树深=4; 5是根节点;同样8与3的关系是父子节点关系。

1

二叉树binary tree,则加了“二叉”(binary),意思是在树中作区分。每个节点至多有两个子(child),left child & right child。二叉树在很多例子中使用,比如二叉树表示算术表达式。 如图:1/8是左节点;2/3是右节点; 2

二、二叉搜索树 BST

顾名思义,二叉树上又加了个搜索的限制。其要求:每个节点比其左子树元素大,比其右子树元素小。 如图:每个节点比它左子树的任意节点大,而且比它右子树的任意节点小

3

三、BST Java实现

直接上代码,对应代码分享在 Github 主页 BinarySearchTree.java

package org.algorithm.tree;
/*
 * Copyright [2015] [Jeff Lee]
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 * 二叉搜索树(BST)实现
 *
 * Created by bysocket on 16/7/7.
 */
public class BinarySearchTree {
    /**
     * 根节点
     */
    public static TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }

    /**
     * 查找
     *      树深(N) O(lgN)
     *      1. 从root节点开始
     *      2. 比当前节点值小,则找其左节点
     *      3. 比当前节点值大,则找其右节点
     *      4. 与当前节点值相等,查找到返回TRUE
     *      5. 查找完毕未找到,
     * @param key
     * @return
     */
    public TreeNode search (int key) {
        TreeNode current = root;
        while (current != null
                && key != current.value) {
            if (key < current.value )
                current = current.left;
            else
                current = current.right;
        }
        return current;
    }

    /**
     * 插入
     *      1. 从root节点开始
     *      2. 如果root为空,root为插入值
     *      循环:
     *      3. 如果当前节点值大于插入值,找左节点
     *      4. 如果当前节点值小于插入值,找右节点
     * @param key
     * @return
     */
    public TreeNode insert (int key) {
        // 新增节点
        TreeNode newNode = new TreeNode(key);
        // 当前节点
        TreeNode current = root;
        // 上个节点
        TreeNode parent  = null;
        // 如果根节点为空
        if (current == null) {
            root = newNode;
            return newNode;
        }
        while (true) {
            parent = current;
            if (key < current.value) {
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    return newNode;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return newNode;
                }
            }
        }
    }

    /**
     * 删除节点
     *      1.找到删除节点
     *      2.如果删除节点左节点为空 , 右节点也为空;
     *      3.如果删除节点只有一个子节点 右节点 或者 左节点
     *      4.如果删除节点左右子节点都不为空
     * @param key
     * @return
     */
    public TreeNode delete (int key) {
        TreeNode parent  = root;
        TreeNode current = root;
        boolean isLeftChild = false;
        // 找到删除节点 及 是否在左子树
        while (current.value != key) {
            parent = current;
            if (current.value > key) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }

            if (current == null) {
                return current;
            }
        }

        // 如果删除节点左节点为空 , 右节点也为空
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            }
            // 在左子树
            if (isLeftChild == true) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
        // 如果删除节点只有一个子节点 右节点 或者 左节点
        else if (current.right == null) {
            if (current == root) {
                root = current.left;
            } else if (isLeftChild) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }

        }
        else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        }
        // 如果删除节点左右子节点都不为空
        else if (current.left != null && current.right != null) {
            // 找到删除节点的后继者
            TreeNode successor = getDeleteSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return current;
    }

    /**
     * 获取删除节点的后继者
     *      删除节点的后继者是在其右节点树种最小的节点
     * @param deleteNode
     * @return
     */
    public TreeNode getDeleteSuccessor(TreeNode deleteNode) {
        // 后继者
        TreeNode successor = null;
        TreeNode successorParent = null;
        TreeNode current = deleteNode.right;

        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }

        // 检查后继者(不可能有左节点树)是否有右节点树
        // 如果它有右节点树,则替换后继者位置,加到后继者父亲节点的左节点.
        if (successor != deleteNode.right) {
            successorParent.left = successor.right;
            successor.right = deleteNode.right;
        }

        return successor;
    }

    public void toString(TreeNode root) {
        if (root != null) {
            toString(root.left);
            System.out.print("value = " + root.value + " -> ");
            toString(root.right);
        }
    }
}

/**
 * 节点
 */
class TreeNode {

    /**
     * 节点值
     */
    int value;

    /**
     * 左节点
     */
    TreeNode left;

    /**
     * 右节点
     */
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
        left  = null;
        right = null;
    }
}

1. 节点数据结构 首先定义了节点的数据接口,节点分左节点和右节点及本身节点值。如图

4

代码如下:

/**
 * 节点
 */
class TreeNode {

    /**
     * 节点值
     */
    int value;

    /**
     * 左节点
     */
    TreeNode left;

    /**
     * 右节点
     */
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
        left  = null;
        right = null;
    }
}

  2. 插入 插入,和删除一样会引起二叉搜索树的动态变化。插入相对删处理逻辑相对简单些。如图插入的逻辑:

5

a. 从root节点开始 b.如果root为空,root为插入值 c.循环: d.如果当前节点值大于插入值,找左节点 e.如果当前节点值小于插入值,找右节点 代码对应:

/**
     * 插入
     *      1. 从root节点开始
     *      2. 如果root为空,root为插入值
     *      循环:
     *      3. 如果当前节点值大于插入值,找左节点
     *      4. 如果当前节点值小于插入值,找右节点
     * @param key
     * @return
     */
    public TreeNode insert (int key) {
        // 新增节点
        TreeNode newNode = new TreeNode(key);
        // 当前节点
        TreeNode current = root;
        // 上个节点
        TreeNode parent  = null;
        // 如果根节点为空
        if (current == null) {
            root = newNode;
            return newNode;
        }
        while (true) {
            parent = current;
            if (key < current.value) {
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    return newNode;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return newNode;
                }
            }
        }
    }

  3.查找 其算法复杂度 : O(lgN),树深(N)。如图查找逻辑:

6

a.从root节点开始 b.比当前节点值小,则找其左节点 c.比当前节点值大,则找其右节点 d.与当前节点值相等,查找到返回TRUE e.查找完毕未找到 代码对应:

/**
     * 查找
     *      树深(N) O(lgN)
     *      1. 从root节点开始
     *      2. 比当前节点值小,则找其左节点
     *      3. 比当前节点值大,则找其右节点
     *      4. 与当前节点值相等,查找到返回TRUE
     *      5. 查找完毕未找到,
     * @param key
     * @return
     */
    public TreeNode search (int key) {
        TreeNode current = root;
        while (current != null
                && key != current.value) {
            if (key < current.value )
                current = current.left;
            else
                current = current.right;
        }
        return current;
    }

4. 删除 首先找到删除节点,其寻找方法:删除节点的后继者是在其右节点树种最小的节点。如图删除对应逻辑:7

结果为: 8

a.找到删除节点 b.如果删除节点左节点为空 , 右节点也为空; c.如果删除节点只有一个子节点 右节点 或者 左节点 d.如果删除节点左右子节点都不为空 代码对应见上面完整代码。   案例测试代码如下,BinarySearchTreeTest.java

package org.algorithm.tree;
/*
 * Copyright [2015] [Jeff Lee]
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 * 二叉搜索树(BST)测试案例 {@link BinarySearchTree}
 *
 * Created by bysocket on 16/7/10.
 */
public class BinarySearchTreeTest {

    public static void main(String[] args) {
        BinarySearchTree b = new BinarySearchTree();
        b.insert(3);b.insert(8);b.insert(1);b.insert(4);b.insert(6);
        b.insert(2);b.insert(10);b.insert(9);b.insert(20);b.insert(25);

        // 打印二叉树
        b.toString(b.root);
        System.out.println();

        // 是否存在节点值10
        TreeNode node01 = b.search(10);
        System.out.println("是否存在节点值为10 => " + node01.value);
        // 是否存在节点值11
        TreeNode node02 = b.search(11);
        System.out.println("是否存在节点值为11 => " + node02);

        // 删除节点8
        TreeNode node03 = b.delete(8);
        System.out.println("删除节点8 => " + node03.value);
        b.toString(b.root);


    }
}

运行结果如下:

value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 8 -> value = 9 -> value = 10 -> value = 20 -> value = 25 -> 
是否存在节点值为10 => 10
是否存在节点值为11 => null
删除节点8 => 8
value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 9 -> value = 10 -> value = 20 -> value = 25 ->

四、小结

与偶尔吃一碗“老坛酸菜牛肉面”一样的味道,品味一个算法,比如BST,的时候,总是那种说不出的味道。 树,二叉树的概念 BST算法 相关代码分享在 Github 主页

如以上文章或链接对你有帮助的话,别忘了在文章结尾处评论哈~ 你也可以点击页面右边“分享”悬浮按钮哦,让更多的人阅读这篇文章。

© 著作权归作者所有

共有 人打赏支持
泥瓦匠BYSocket

泥瓦匠BYSocket

粉丝 884
博文 149
码字总数 192697
作品 4
杭州
程序员
私信 提问
验证二叉搜索树

原题   Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows:   The left subtree of a node contains only nodes with k......

一贱书生
2016/12/20
0
0
4 张 GIF 图帮助你理解二叉查找树

二叉查找树(Binary Search Tree),也称二叉搜索树,是指一棵空树或者具有下列性质的二叉树: 1.任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 2.任意节点的右子树不...

桃子红了呐
2017/02/27
0
0
4 张 GIF 图帮助你理解二叉树搜索算法

二叉查找树(Binary Search Tree),也称二叉搜索树,是指一棵空树或者具有下列性质的二叉树: 任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 任意节点的右子树不空,...

HenrySun
2016/08/06
15
0
数据结构MOOC|二叉搜索树BST

课程内容来自:http://www.icourse163.org/learn/ZJU-93001?tid=1002654021#/learn/content?type=detail&id=1003620986 二叉搜索树(BST,Binary Search Tree) 也称二叉排序树或二叉查找树,......

darlingwood2013
2018/05/30
0
0
二叉排序树(Binary Sort Tree)

1、定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树: ① 若它的左子树非空,则左子树上所有...

野渡书生
2016/04/28
96
0

没有更多内容

加载失败,请刷新页面

加载更多

rabbitmq

灰暗
27分钟前
0
0
Flink

flink HA部署 flink搭建,采用分布式部署方式,分别为A,B,C三个节点。其中A为master;A,B,C为worker。 本文使用的用户是hadoop用户(自己新建) 先决条件 Java 1.8.x or higher scala 自己使用...

-九天-
54分钟前
2
0
数据中台和传统数仓的区别

中台系统把业务层同性的算法能力,服务能力,业务能力高度集成,有效组织 ,动态规划。更好的帮助上层业务。 今天就让我们看看关于数据中台的问答吧。 1 Q : 什么是数据中台? A : 数据中台是...

hblt-j
55分钟前
4
0
Java在什么时候会出现内存泄漏

在Java中,内存泄漏就是存在一些被分配的对象,这些对象有下面两个特点,首先,这些对象是可达的,即在有向图中,存在通路可以与其相连;其次,这些对象是无用的,即程序以后不会再使用这些对...

群星纪元
58分钟前
2
0
android 打开摄像头

private SurfaceHolder mHolder; private SurfaceView mSurfaceView; private Camera mCamera; mSurfaceView = (SurfaceView) this.findViewById(R.id.camsurfaceView1); mHolder = mSurface......

jingshishengxu
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部