算法导论之红黑树&区间树

实验要求

image.png

实验代码

区间树的很多操作是红黑树进行一点简单的修改，区间树中加入的max域 注意在插入和旋转的时候进行对max域进行维护与更新。

一点新学到的tricks

多用python的定向输出比较适合需要输出多个文件的时候。

一点问题

对于NIL的指针，处理的还不够巧妙，整个代码基本是算法导论照搬，但是NIL指针的定义和处理还需要修改和理解

代码

#USTC Donglai Ma

# The basic code come from 'Introduction to Algorithms'
import sys
class RBTreenode(object):
    def __init__(self,inter):
        nil = Inter(-1,-1)
        self.parent = None
        self.key = inter.low
        self.left = None
        self.right = None
        self.color = "black"
        self.max = 0

        # Inter for code x
        self.inter = inter





    # def printnode_inorder(self):
    #     # In-order traversal
    #     if self.left:
    #         self.left.print()
    #     print(self.key)
    #     if self.right:
    #         self.right.print()
    #
    #
class Inter:
    def __init__(self,low,high):
        self.low = low
        self.high = high


class RBTree:
    # Insert,Delete,Print,Left Rotate, Right Rotate
    def __init__(self):
        # Notice that the nil here use 0 to present
        nil = RBTreenode(Inter(-1,-1))
        self.nil = nil
        self.root = self.nil

# Left Rotate


def left_rotate(T, x):
    # Left Rotate

    y = x.right
    x.right = y.left
    if y.left != T.nil:
        y.left.parent = x
    y.parent = x.parent
    if x.parent == T.nil:
        T.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x
    x.parent = y

    # update the max
    y.max = x.max
    x.max = max(x.inter.high,x.left.max,x.right.max)


def right_rotate( T, x):
    # Right Rotate
    y = x.left
    x.left = y.right
    if y.right != T.nil:
        y.right.parent = x
    y.parent = x.parent
    if x.parent == T.nil:
        T.root = y
    elif x == x.parent.right:
        x.parent.right = y
    else:
        x.parent.left = y
    y.right = x
    x.parent = y
    # update the max
    x.max = y.max
    y.max = max(y.right.max,y.left.max,y.inter.high)


def rb_insert(T, z):
    # insert the node
    y = T.nil
    x = T.root
    while x != T.nil:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y == T.nil:
        T.root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
    z.left = T.nil
    z.right = T.nil
    z.color = 'red'
    # update the max of z
    z.max = max(z.inter.high,z.left.max,z.right.max)
    rb_insert_fixup(T, z)
    # update to root's  max
    while z.parent!=T.nil:
        z.parent.max = max(z.parent.max,z.max)
        z=z.parent



def rb_insert_fixup( T, z):

    while z.parent.color == 'red':
        if z.parent == z.parent.parent.left:
            y = z.parent.parent.right
            if y.color == 'red': # case 1
                z.parent.color = 'black'
                y.color = 'black'
                z.parent.parent.color = 'red'
                z = z.parent.parent
            else:
                if z == z.parent.right: #case 2
                    z = z.parent
                    left_rotate(T, z)
                z.parent.color = 'black' # case 3
                z.parent.parent.color = 'red'
                right_rotate(T,z.parent.parent)
        else:
            y = z.parent.parent.left
            if y.color == 'red':
                z.parent.color = 'black'
                y.color = 'black'
                z.parent.parent.color = 'red'
                z = z.parent.parent
            else:
                if z == z.parent.left:
                    z = z.parent
                    right_rotate(T, z)
                z.parent.color = 'black'
                z.parent.parent.color = 'red'
                left_rotate(T, z.parent.parent)
    T.root.color = 'black'


def rb_transplant(T, u, v):
    if u.parent == T.nil:
        T.root = v
    elif u == u.parent.left:
        u.parent.left = v
    else:
        u.parent.right = v
    v.parent = u.parent


def rb_delete(T, m):
    # delete the z node
    #z = search_tree(T.root,m)
    z = interval_search(T,m)
    y = z
    y_original_color = y.color
    if z.left == T.nil:
        x = z.right
        rb_transplant(T, z, z.right)
    elif z.right == T.nil:
        x = z.left
        rb_transplant(T, z, z.left)
    else:
        y = tree_minimum(T,z.right)
        y_original_color = y.color
        x = y.right
        if y.parent == z:
            x.parent = y
        else:
            rb_transplant(T, y, y.right)
            y.right = z.right
            y.right.parent = y
        rb_transplant(T, z, y)
        y.left = z.left
        y.left.parent = y
        y.color = z.color
    if y_original_color == 'black':
        rb_delete_fixup(T, x)


def rb_delete_fixup(T, x):
    while x != T.root and x.color == 'black':
        if x == x.parent.left:
            w = x.parent.right
            if w.color == 'red':
                w.color = 'black' #case 1
                x.parent.color = 'red'
                left_rotate(T, x.parent)
                w = x.parent.right
            if w.left.color == 'black' and w.right.color == 'black':
                w.color = 'red' #case 2
                x = x.parent
            else:
                if w.right.color == 'black':
                    w.left.color = 'black' # case 3
                    w.color = 'red'
                    right_rotate(T, w)
                    w = x.parent.right
                w.color = x.parent.color  # case 4
                x.parent.color = 'black'
                w.right.color = 'black'
                left_rotate(T, x.parent)
                x = T.root
        else:
            w = x.parent.left
            if w.color == 'red':
                w.color = 'black'
                x.parent.color = 'red'
                right_rotate(T, x.parent)
                w = x.parent.left
            if w.right.color == 'black' and w.left.color == 'black':
                w.color = 'red'
                x = x.parent
            else:
                if w.left.color == 'black':
                    w.right.color = 'black'
                    w.color = 'red'
                    left_rotate(T, w)
                    w = x.parent.left
                w.color = x.parent.color
                x.parent.color = 'black'
                w.left.color = 'black'
                right_rotate(T, x.parent)
                x = T.root
    x.color = 'black'


def tree_minimum(T,x):
    while x.left != T.nil:
        x = x.left
    return x

# def search_tree(A,x):
#    while x != A.key:
#        if x<A.key:
#            A = A.left
#        else:
#            A = A.right
#
#    return A


#Here we need to check the interval,i = interval
def search_tree(A,i):
    while i.low !=A.key:
        if i.low <A.key:
            A = A.left
        else:
            A = A.right
    return A

# Although it's interval , the key is interval.low and
#   I assume key is same which means the i must in the Tree






def interval_search(T,interval):
    x = T.root
    #not overlap
    while x!= T.nil and(x.inter.low >interval.high or x.inter.high<interval.low):
        if x.left!=T.nil and x.left.max>=interval.low:
            x=x.left
        else:
            x=x.right
    return x



def Insort(x):
    if x!= None:
        Insort(x.left)
        if x.key!=0:
            print('key:', x.key,'x.parent',x.parent.key)
        Insort(x.right)


#def preorder_sort(x):
    # if x!=None:
    #     if x.key!=0:print(x.key)
    #     preorder_sort(x.left)
    #     preorder_sort(x.right)


def inorder_sort(x):
    if x!= None:
        inorder_sort(x.left)
        if x.key!=-1:
            print(x.inter.low,x.inter.high,x.max)

        inorder_sort(x.right)

#def postorder_sort(x):
    # if x!= None:
    #     postorder_sort(x.left)
    #     postorder_sort(x.right)
    #     if x.key!=0:print(x.key)

# Generate the inputB
import numpy as np
import random
import time
# list = []



# list_left = [x for x in range(0,25)]
# for i in range (30,50):
#     list_left.append(i)
# random.shuffle(list_left)
# print(list_left)
# list = []
#
#
# for i in range(len(list_left)):
#     if list_left[i]<25:
#         list.append((list_left[i],random.randint(list_left[i]+1,25)))
#     else:
#         list.append((list_left[i],random.randint(list_left[i]+1,50)))
# print(list)
#
#
# np.savetxt("../inputB/random_interval_file.txt",list,fmt="%d")

# read the input
list_all= np.loadtxt("../inputB/random_interval_file.txt",dtype='int')
#print(list_all[1,1])
list_inter = []
for i in range(len(list_all)):
    m = Inter(list_all[i,0],list_all[i,1])
    list_inter.append(m)

T = RBTree()
for i in range(0,30):
   rb_insert(T,RBTreenode(list_inter[i]))

filename_inorder = str('../outputB/inorder.txt')
filename_delete_data = str('../outputB/delete_data.txt')
filename_search = str('../outputB/search.txt')
savedStdout = sys.stdout   #保存标准输出流
with open(filename_inorder, 'w+') as file:
    sys.stdout = file
    inorder_sort(T.root)
    file.close()


with open(filename_delete_data, 'w+') as file:
    sys.stdout = file
    list_delete = random.sample(list_inter,3)
    rb_delete(T,list_delete[0])
    rb_delete(T,list_delete[1])
    rb_delete(T,list_delete[2])
    print('The deleted node is')
    for i in range(3):

        print(list_delete[i].low,list_delete[i].high,'\n')

    print ('The final inorder is ')
    inorder_sort(T.root)
    file.close()


with open(filename_search, 'w+') as file:
    sys.stdout = file
    a = Inter(3,11)
    b = Inter(26,27)
    c = Inter(33,45)
    print('Search (3,11)')
    print(interval_search(T,a).inter.low,interval_search(T,a).inter.high)
    print('Search (26,27)')
    print(interval_search(T,b).inter.low,interval_search(T,b).inter.high)
    print('Search (33,45)')
    print(interval_search(T,c).inter.low,interval_search(T,c).inter.high)

    file.close()


sys.stdout = savedStdout #恢复标准输出流
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,463评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,868评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 161,213评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,666评论 1赞 290
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,759评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,725评论 1赞 294
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,716评论 3赞 415
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,484评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,928评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,233评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,393评论 1赞 345
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,073评论 5赞 340
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,718评论 3赞 324
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,308评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,538评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,338评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,260评论 2赞 352