算法:二叉排序树的删除节点策略及其图形化(二叉树查找)

二叉排序树(BST,Binary Sort Tree)具有这样的性质:对于二叉树中的任意节点,如果它有左子树或右子树,则该节点的数据成员大于左子树所有节点的数据成员,且小于右子树所有节点的数据成员。排序二叉树的中序遍历结果是从小到大排列的。

二叉排序树的查找和插入比较好理解,主要来看一下删除时的情况。

如果需要查找并删除如图8-6-8中的37, 51, 73,93这些在二叉排序树中是叶子的结点,那是很容易的,毕竟删除它们对整棵树来说,其他结点的结构并未受到影响。

对于要删除的结点只有左子树或只有右子树的情况,相对也比较好解决。那就是结点删除后,将它的左子树或右子树整个移动到删除结点的位置即可,可以理解为独子继承父业。比如图8-6-9,就是先删除35和99两结点,再删除58结点的变化图,最终,整个结构还是一个二叉排序树。

但是对于要删除的结点既有左子树又有右子树的情况怎么办呢?比如图8-6-10中的47结点若要删除了,它的两儿子和子孙们怎么办呢?

前人总结的比较好的方法就是,找到需要删除的结点p的直接前驱(或直接后继)s,用s来替换结点p,然后再删除此结点s,如图8-6-12所示。

注意:这里的前驱和后继是指中序遍历时的顺序。

Deletion

There are three possible cases to consider:

Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.

Deleting a node with one child: Remove the node and replace it with its child.

Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-

order predecessor node, R. Replace the value of N with the value of R, then delete R.

As with all binary trees, a node's in-order successor is the left-most child of its right subtree, and a node's in-order predecessor is the right-most 

child of its left subtree. In either case, this node will have zero or one children. Delete it according to one of the two simpler cases above.

下面来看代码:(参考《linux c 编程一站式学习》

/*************************************************************************
    > File Name: binarysearchtree.h
    > Author: Simba
    > Mail: dameng34@163.com
    > Created Time: Sat 29 Dec 2012 06:05:55 PM CST
 ************************************************************************/

#ifndef BST_H
#define BST_H

typedef struct node *link;
struct node
{
    unsigned char item;
    link left, right;
};

link search(link t, unsigned char key);
link insert(link t, unsigned char key);
link delete(link t, unsigned char key);
void print_tree(link t);

#endif
/*************************************************************************
    > File Name: binarysearchtree.c
    > Author: Simba
    > Mail: dameng34@163.com
    > Created Time: Sat 29 Dec 2012 06:08:08 PM CST
 ************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include "binarysearchtree.h"

static link make_node(unsigned char item)
{
    link p = malloc(sizeof(*p));
    p->item = item;
    p->left = p->right = NULL;
    return p;
}

static void free_node(link p)
{
    free(p);
}

link search(link t, unsigned char key)
{
    if (!t)
        return NULL;
    if (t->item > key)
        return search(t->left, key);
    if (t->item < key)
        return search(t->right, key);
    /* if (t->item == key) */
    return t;
}

link insert(link t, unsigned char key)
{
    if (!t)
        return make_node(key);
    if (t->item > key) /* insert to left subtree */
        t->left = insert(t->left, key);
    else /* if (t->item <= key), insert to right subtree */
        t->right = insert(t->right, key);
    return t;
}


link delete(link t, unsigned char key)
{
    link p;
    if (!t)
        return NULL;
    if (t->item > key) /* delete from left subtree */
        t->left = delete(t->left, key);
    else if (t->item < key) /* delete from right subtree */
        t->right = delete(t->right, key);
    else   /* if (t->item == key) */
    {
        if (t->left == NULL && t->right == NULL)
        {
            /* if t is a leaf node */
            free_node(t);
            t =  NULL;
        }
        else if (t->left)  /* if t has left subtree */
        {
            /* replace t with the rightmost node in left subtree */
            for (p = t->left; p->right; p = p->right);
            t->item = p->item; /* 将左子树下最靠右的节点值赋予想要删除的节点 */
            t->left = delete(t->left, t->item); 
        }
        
        else  /* if t has right subtree */
        {
            /* replace t with the leftmost node in right subtree */
            for (p = t->right; p->left; p = p->left);
            t->item = p->item;
            t->right = delete(t->right, t->item);
        }
    }
    return t;
}

void print_tree(link t)
{
    if (t)
    {
        printf("(");
        printf("%d", t->item);
        print_tree(t->left);
        print_tree(t->right);
        printf(")");
    }
    else
        printf("()");
}
/*************************************************************************
    > File Name: main2.c
    > Author: Simba
    > Mail: dameng34@163.com
    > Created Time: Sat 29 Dec 2012 06:22:57 PM CST
 ************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include "binarysearchtree.h"

#define RANGE 100
#define N 6

void print_item(link p)
{
    printf("%d", p->item);
}

int main(void)
{
    int i, key;
    link root = NULL;
    srand(time(NULL));
    for (i = 0; i < N; i++)
    {
        root = insert(root, rand() % RANGE); /* 第一次循环root从NULL变成根节点值,接下去
                                                的循环虽然迭代root,但在插入节点过程中root的值始终不变 */
        printf("root = 0x%x\n", (unsigned int)root);
    }

    printf("\t\\tree");
    print_tree(root);
    printf("\n\n");

    while (root)
    {
        key = rand() % RANGE;
        if (search(root, key))
        {
            printf("delete %d in tree\n", key);
            root = delete(root, key); /* root虽然迭代,但返回的仍是先前的值,即根节点的值保持不变
                                         直到全部节点被删除,root变成NULL即0x0 */
            printf("root = 0x%x\n", (unsigned int)root);

            printf("\t\\tree");
            print_tree(root); /* 传递给函数的一直是根节点的值,直到树清空,root变成NULL */
            printf("\n\n");
        }
    }
    return 0;
}

输出为:

如果我们使用了The Tree Preprocessor,可以将以括号展示的排序二叉树转换成树形展示,如下图

以前此工具可以在 http://www.essex.ac.uk/linguistics/clmt/latex4ling/trees/tree/ 下载,现已找不到链接,我将其上传到csdn,需要的可以去下载。

http://download.csdn.net/detail/simba888888/5334093

最后提一下,我们希望构建出来的二叉排序树是比较平衡的,即其深度与完全二叉树相同,那么查找的时间复杂度研究度O(logn),近似于折半查找,

但如果出现构造的树严重不平衡,如完全是左斜树或者右斜树,那么查找时间复杂度为O(n),近似于顺序查找。那如何让二叉排序树平衡呢?

事实上还有一种平衡二叉树(AVL树),也是一种二叉排序树,其中每个结点的左子树和右子树的高度差至多等于1。

补充:delete() 在《data structure and algorithm analysis in c》 中的实现,个人觉得比较清晰,也挺好理解的,如下:

link FindMin(link T)
{
    if (T != NULL)
        while (T->left != NULL)
            T = T->left;

    return T;
}

link delete(unsigned char X, link T)
{
    link tmp;
    if (T == NULL)
    {
        printf("Tree is empty!\n");
        return NULL;
    }

    if (X < T->key) //go left
        T->left = delete(X, T->left);
    else if (X > T->key) // go right
        T->right = delete(X, T->right);

    /* found elem to be deleted*/
    else if (T->left && T->right) //have two children
    {
        // replace with smallest in right subtree
        tmp = FindMin(T->right);
        T->key = tmp->key;
        T->right = delete(T->key, T->right);
    }
    else //one or zero children
    {
        tmp = T;
        if (T->left == NULL)
            T = T->right;
        else if (T->right == NULL)
            T = T->left;
        free(tmp);
    }

    return T;
}

参考:

《大话数据结构》

《linux c 编程一站式学习》

《Data Structures》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏MasiMaro 的技术博文

PE解析器的编写(四)——数据目录表的解析

在PE结构中最重要的就是区块表和数据目录表,上节已经说明了如何解析区块表,下面就是数据目录表,在数据目录表中一般只关心导入表,导出表和资源这几个部分,但是资源实...

752
来自专栏coder修行路

Go基础--终端操作和文件操作

终端操作 操作终端相关的文件句柄常量 os.Stdin:标准输入 os.Stdout:标准输出 os.Stderr:标准错误输出 关于终端操作的代码例子: pa...

2766
来自专栏抠抠空间

Django之ORM字段和参数

字段 常用字段 ---- AutoField                                                          ...

2766
来自专栏Spark学习技巧

textFile构建RDD的分区及compute计算策略

1,textFile A),第一点,就是输入格式,key,value类型及并行度的意义。 def textFile( path: String, mi...

1957
来自专栏后台架构

Sphinx源码学习笔记(二):查询关键词

 继续上一篇索引创建流程完成,学习理解一下查询关键词的逻辑处理流程。

2376
来自专栏小灰灰

Java之写文件

java之写文件 上一篇写了java读取文件的各种操作姿势,这里也补一个写文件的工具类,比较简单 1. 读写类介绍 (和上一篇差不多) java读写文件的I...

1776
来自专栏difcareer的技术笔记

Android Linker学习笔记[转]

Linker是Android系统动态库so的加载器/链接器,要想轻松地理解Android linker的运行机制,我们需要先熟悉ELF的文件结构,再了解ELF文...

1174
来自专栏乐沙弥的世界

MySQL auto_increment_increment,auto_increment_offset 用法

    MySQL中对于表上ID自增列可以在创建表的时候来指定列上的auto_increment属性;等同于SQL server中的identity属性;Ora...

653
来自专栏岑玉海

hbase源码系列(九)StoreFile存储格式

从这一章开始要讲Region Server这块的了,但是在讲Region Server这块之前得讲一下StoreFile,否则后面的不好讲下去,这块是基础,Re...

3345
来自专栏别先生

一脸懵逼学习oracle

oracle的默认用户:system,sys,scott; 1:查看登录的用户名:show user; 2:查看数据字典:dba_users; 3:创建新...

1607

扫码关注云+社区