RBTree

2020-04-18

字数统计: 3.9k字 | 阅读时长≈ 24分钟

RBTree

根据参考文献实现了一下区间树，key 为区间的起点，实现了插入、删除和查找功能，记录一下代码：

IntervalTree.py

from datetime import datetime
import unittest


class Interval(object):
    def __init__(self, id: str, name: str, start: str, end: str) -> None:
        self.id = id
        self.name = name
        self.start = datetime.strptime(start, "%H:%M")
        self.end = datetime.strptime(end, "%H:%M")


class IntervalTreeNode(object):
    def __init__(self, interval: Interval) -> None:
        # key is interval.start
        self.interval = interval
        self.maxrange = interval.end
        self.parent = None
        self.color = "R"
        self.left = None
        self.right = None


def insert(root: IntervalTreeNode, newnode: IntervalTreeNode) -> IntervalTreeNode:
    '''
    Insert an interval into the tree and auto-update maxrange.
    '''
    interval = newnode.interval

    # Case 1: tree is empty.
    if root is None:
        print("Case 1.")
        root = newnode
        root.color = "B"
        # root.maxrange = root.interval.end
        return root
    position = search_insert_position(root, interval)

    # Case 2: already updated value during the search.
    if position is None:
        update_maxrange(root)
        print("Case 2.")
        return root
    
    # Case 3: position is black.
    if position.color == 'B':
        print("Case 3.")
        if interval.start < position.interval.start:
            position.left = newnode
        else:
            position.right = newnode
        newnode.parent = position
        update_maxrange(root)
        return root
    
    # Case 4: position is red.
    else:
        print("Case 4.", end=' ')
        # Case 4.1: uncle exists and is red
        if position == position.parent.left and position.parent.right and position.parent.right.color == 'R':
            print("Case 4.1.l")
            if interval.start < position.interval.start:
                position.left = newnode
            else:
                position.right = newnode
            newnode.parent = position

            pp = position.parent
            s = position.parent.right
            pp.color = 'R'
            s.color = 'B'
            position.color = 'B'
            if pp == root:
                pp.color = 'B'
            if pp.parent is None or pp.parent.color == 'B':
                update_maxrange(root)
                return root
            else:
                if pp == pp.parent.left:
                    pp.parent.left = None
                else:
                    pp.parent.right = None
                pp.parent = None
                return insert(root, pp)
        elif position == position.parent.right and position.parent.left and position.parent.left.color == 'R':
            print("Case 4.1.r")
            if interval.start < position.interval.start:
                position.left = newnode
            else:
                position.right = newnode
            newnode.parent = position

            pp = position.parent
            s = position.parent.left
            pp.color = 'R'
            s.color = 'B'
            position.color = 'B'
            if pp == root:
                pp.color = 'B'
            if pp.parent is None or pp.parent.color == 'B':
                update_maxrange(root)
                return root
            else:
                if pp == pp.parent.left:
                    pp.parent.left = None
                else:
                    pp.parent.right = None
                pp.parent = None
                return insert(root, pp)

        # Case 4.2: uncle is not red (then it must be null), and position is its parent's left child.
        elif position == position.parent.left:
            # Case 4.2.1: newnode is position's left child.
            if newnode.interval.start < position.interval.start:
                print("Case 4.2.1.")
                position.left = newnode
                newnode.parent = position
                position.color = 'B'
                position.parent.color = 'R'
                flag = position.parent == root
                right_shift(position.parent)
                if flag:
                    update_maxrange(position)
                    return position
                else:
                    update_maxrange(root)
                    return root
            # Case 4.2.2: newnode is position's right child.
            else:
                print("Case 4.2.2.")
                position.right = newnode
                newnode.parent = position
                left_shift(position)
                newnode.color = 'B'
                newnode.parent.color = 'R'
                flag = newnode.parent == root
                right_shift(newnode.parent)
                if flag:
                    update_maxrange(newnode)
                    return newnode
                else:
                    update_maxrange(root)
                    return root
        # Case 4.3: uncle is not red (then it must be null), and position is its parent's right child.
        elif position == position.parent.right:
            # Case 4.3.1: newnode is position's right child.
            if newnode.interval.start > position.interval.start:
                print("Case 4.3.1.")
                position.right = newnode
                newnode.parent = position
                position.color = 'B'
                position.parent.color = 'R'
                flag = position.parent == root
                left_shift(position.parent)
                if flag:
                    update_maxrange(position)
                    return position
                else:
                    update_maxrange(root)
                    return root
            # Case 4.3.2: newnode is position's left child.
            else:
                print("Case 4.3.2")
                position.left = newnode
                newnode.parent = position
                right_shift(position)
                newnode.color = 'B'
                newnode.parent.color = 'R'
                flag = newnode.parent == root
                left_shift(newnode.parent)
                if flag:
                    update_maxrange(newnode)
                    return newnode
                else:
                    update_maxrange(root)
                    return root
                

def insert_noupdate(root: IntervalTreeNode, newnode: IntervalTreeNode) -> IntervalTreeNode:
    '''
    Insert an interval into the tree and do not update maxrange.
    '''
    interval = newnode.interval

    # Case 1: tree is empty.
    if root is None:
        print("Case 1.")
        root = newnode
        root.color = "B"
        # root.maxrange = root.interval.end
        return root
    position = search_insert_position(root, interval)

    # Case 2: already updated value during the search.
    if position is None:
        print("Case 2.")
        return root

    # Case 3: position is black.
    if position.color == 'B':
        print("Case 3.")
        if interval.start < position.interval.start:
            position.left = newnode
        else:
            position.right = newnode
        newnode.parent = position
        return root

    # Case 4: position is red.
    else:
        print("Case 4.", end=' ')
        # Case 4.1: uncle exists and is red
        if position == position.parent.left and position.parent.right and position.parent.right.color == 'R':
            print("Case 4.1.l")
            if interval.start < position.interval.start:
                position.left = newnode
            else:
                position.right = newnode
            newnode.parent = position

            pp = position.parent
            s = position.parent.right
            pp.color = 'R'
            s.color = 'B'
            position.color = 'B'
            if pp == root:
                pp.color = 'B'
            if pp.parent is None or pp.parent.color == 'B':
                return root
            else:
                if pp == pp.parent.left:
                    pp.parent.left = None
                else:
                    pp.parent.right = None
                pp.parent = None
                return insert(root, pp)
        elif position == position.parent.right and position.parent.left and position.parent.left.color == 'R':
            print("Case 4.1.r")
            if interval.start < position.interval.start:
                position.left = newnode
            else:
                position.right = newnode
            newnode.parent = position

            pp = position.parent
            s = position.parent.left
            pp.color = 'R'
            s.color = 'B'
            position.color = 'B'
            if pp == root:
                pp.color = 'B'
            if pp.parent is None or pp.parent.color == 'B':
                return root
            else:
                if pp == pp.parent.left:
                    pp.parent.left = None
                else:
                    pp.parent.right = None
                pp.parent = None
                return insert(root, pp)

        # Case 4.2: uncle is not red (then it must be null), and position is its parent's left child.
        elif position == position.parent.left:
            # Case 4.2.1: newnode is position's left child.
            if newnode.interval.start < position.interval.start:
                print("Case 4.2.1.")
                position.left = newnode
                newnode.parent = position
                position.color = 'B'
                position.parent.color = 'R'
                flag = position.parent == root
                right_shift(position.parent)
                if flag:
                    return position
                else:
                    return root
            # Case 4.2.2: newnode is position's right child.
            else:
                print("Case 4.2.2.")
                position.right = newnode
                newnode.parent = position
                left_shift(position)
                newnode.color = 'B'
                newnode.parent.color = 'R'
                flag = newnode.parent == root
                right_shift(newnode.parent)
                if flag:
                    return newnode
                else:
                    return root
        # Case 4.3: uncle is not red (then it must be null), and position is its parent's right child.
        elif position == position.parent.right:
            # Case 4.3.1: newnode is position's right child.
            if newnode.interval.start > position.interval.start:
                print("Case 4.3.1.")
                position.right = newnode
                newnode.parent = position
                position.color = 'B'
                position.parent.color = 'R'
                flag = position.parent == root
                left_shift(position.parent)
                if flag:
                    return position
                else:
                    return root
            # Case 4.3.2: newnode is position's left child.
            else:
                print("Case 4.3.2")
                position.left = newnode
                newnode.parent = position
                right_shift(position)
                newnode.color = 'B'
                newnode.parent.color = 'R'
                flag = newnode.parent == root
                left_shift(newnode.parent)
                if flag:
                    return newnode
                else:
                    return root


def search_insert_position(node: IntervalTreeNode, interval: Interval) -> IntervalTreeNode:
    if node is None:
        return None
    if node.interval.start == interval.start:
        # Update value and return None
        node.maxrange = max(node.maxrange, interval.end)
        node.interval = interval
        return None
    if node.interval.start > interval.start:
        if node.left is None:
            return node
        return search_insert_position(node.left, interval)
    else:
        if node.right is None:
            return node
        return search_insert_position(node.right, interval)


def update_maxrange(node: IntervalTreeNode) -> None:
    if node is None:
        return
    if node.left is None and node.right is None:
        node.maxrange = node.interval.end
        return
    if node.left is None or node.right is None:
        if node.right is not None:
            update_maxrange(node.right)
            node.maxrange = max(node.right.maxrange, node.interval.end)
            return
        elif node.left is not None:
            update_maxrange(node.left)
            node.maxrange = max(node.left.maxrange, node.interval.end)
            return
    update_maxrange(node.left)
    update_maxrange(node.right)
    node.maxrange = max(node.right.maxrange, node.interval.end)
    node.maxrange = max(node.left.maxrange, node.maxrange)
    return


def delete(root: IntervalTreeNode, id: str) -> IntervalTreeNode:
    '''
    Delete class using id in tree.
    '''
    del_node = search_delete_position(root, id)
    print("Delete node: " + del_node.interval.id + " " + del_node.interval.name + " " + del_node.interval.start.strftime(
        "%H:%M") + " " + del_node.interval.end.strftime("%H:%M") + " " + del_node.color)

    # Id not found.
    if del_node is None:
        return root

    # Replace the information and delete replace_node.
    del_node = replace_node = find_real_delete_position(root, del_node)
    print("Replace node: " + replace_node.interval.id + " " + replace_node.interval.name + " " + replace_node.interval.start.strftime("%H:%M") + " " + replace_node.interval.end.strftime("%H:%M") + " " + replace_node.color)
    
    # position.interval = replace_node.interval
    
    # Case 1: replace_node is red, just delete the replace_node.
    if replace_node.color == "R":
        print("Case 1.")
        if replace_node.parent.left == replace_node:
            replace_node.parent.left = None
            del del_node
            update_maxrange(root)
            return root
        else:
            replace_node.parent.right = None
            del del_node
            update_maxrange(root)
            return root
    
    # Case 2: replace_node is black.
    while replace_node.color == 'B' and replace_node != root:
        if replace_node.parent.left == replace_node:
            # Case 2.1: replace_node is its parent's left child.
            if replace_node.parent.right.color == 'R':
                print("Case 2.1.1.")
                # Case 2.1.1: replace_node's sibling is red.
                sibling = replace_node.parent.right
                replace_node.parent.color = 'R'
                sibling.color = 'B'
                if replace_node.parent == root:
                    root = left_shift(replace_node.parent)
                else:
                    left_shift(replace_node)
                # Do 2.1.2.3.
                continue
            else:
                # Case 2.1.2: replace_node's sibling is black.
                sibling = replace_node.parent.right
                parent = replace_node.parent
                if sibling.right and sibling.right.color == 'R':
                    # Case 2.1.2.1: sibling's right child is red.
                    print("Case 2.1.2.1.")
                    sibling.color = parent.color
                    sibling.right.color = 'B'
                    parent.color = 'B'
                    if parent == root:
                        root = left_shift(parent)
                    else:
                        left_shift(parent)
                    break
                if sibling.left and sibling.left.color == 'R':
                    # Case 2.1.2.2: sibling's left child is red.
                    print("Case 2.1.2.2.")
                    sibling.color = 'R'
                    sibling.left.color = 'B'
                    right_shift(sibling)
                    # Do 2.1.2.1
                    newsibling = replace_node.parent.right
                    newsibling.color = parent.color
                    newsibling.right.color = 'B'
                    parent.color = 'B'
                    if parent == root:
                        root = left_shift(parent)
                    else:
                        left_shift(parent)
                    break
                if (sibling.left is None and sibling.right is None) or (sibling.left.color == 'B' and sibling.right.color == 'B'):
                    # Case 2.1.2.3: sibling's left child and sibling's right child are all black.
                    print("Case 2.1.2.3.")
                    sibling.color = 'R'
                    # TODO: set new replace_node.
                    if parent.color == 'R':
                        parent.color = 'B'
                        break
                    else:
                        replace_node = replace_node.parent
                        continue
        else:
            # Case 2.2: replace_node is its parent's right child.
            sibling = replace_node.parent.left
            parent = replace_node.parent
            if sibling.color == 'R':
                # Case 2.2.1: sibling is red.
                print("Case 2.2.1.")
                sibling.color = 'B'
                parent.color = 'R'
                if parent == root:
                    root = right_shift(parent)
                else:
                    right_shift(parent)
                # Do 2.2.2.3.
                continue
            else:
                # Case 2.2.2: sibling is black.
                if sibling.left and sibling.left.color == 'R':
                    # Case 2.2.2.1: sibling's left child is red.
                    print("Case 2.2.2.1.")
                    sibling.color = parent.color
                    sibling.left.color = 'B'
                    parent.color = 'B'
                    if parent == root:
                        root = right_shift(parent)
                    else:
                        right_shift(parent)
                    break
                if sibling.right and sibling.right.color == 'R':
                    # Case 2.2.2.2: sibling's left child is red.
                    print("Case 2.2.2.2.")
                    sibling.color = 'R'
                    sibling.right.color = 'B'
                    left_shift(sibling)
                    # Do 2.2.2.1
                    newsibling = replace_node.parent.left
                    newsibling.color = parent.color
                    newsibling.left.color = 'B'
                    parent.color = 'B'
                    if parent == root:
                        root = right_shift(parent)
                    else:
                        right_shift(parent)
                    break
                if (not sibling.left and not sibling.right) or (sibling.left.color == 'B' and sibling.right.color == 'B'):
                    # Case 2.2.2.3: sibling's left child and sibling's right child are all black.
                    print("Case 2.2.2.3.")
                    sibling.color = 'R'
                    if parent.color == 'R':
                        parent.color = 'B'
                        break
                    else:
                        replace_node = parent
                        continue
    parent = del_node.parent
    if parent.left == del_node:
        parent.left = None
    else:
        parent.right = None
    del del_node
    update_maxrange(root)
    return root


def search_delete_position(node: IntervalTreeNode, id: str) -> IntervalTreeNode:
    if node is None:
        return None
    if node.interval.id == id:
        return node
    else:
        tmp = search_delete_position(node.left, id)
        if tmp:
            return tmp
        else:
            return search_delete_position(node.right, id)


def find_real_delete_position(root: IntervalTreeNode, node: IntervalTreeNode) -> IntervalTreeNode:
    # Case 1: node has no child.
    if node.left is None and node.right is None:
        return node
    
    # Case 2: node has one child.
    if node.left is None or node.right is None:
        if node.left is not None:
            node.interval = node.left.interval
            return find_real_delete_position(root, node.left)
        else:
            node.interval = node.right.interval
            return find_real_delete_position(root, node.right)
    
    # Case 3: node has two children.
    successor = inorder_traversal(root, node)
    assert successor is not None
    node.interval = successor.interval
    return find_real_delete_position(root, successor)


def inorder_traversal(root: IntervalTreeNode, node: IntervalTreeNode) -> IntervalTreeNode:
    stack = []
    res = []
    prev = None
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if prev == node:
            return root
        prev = root
        root = root.right
    return None


def search(root: IntervalTreeNode, start: str, end: str) -> None:
    '''
    Search all classes' name in [start, end].
    '''
    if root is None:
        return
    start_time = datetime.strptime(start, "%H:%M")
    end_time = datetime.strptime(end, "%H:%M")
    x = root
    if x.maxrange < start_time:
        return
    if is_overlap(x.interval.start, x.interval.end, start_time, end_time):
        print("Found overlap: " + x.interval.id + " " +
              x.interval.name + " " + x.interval.start.strftime("%H:%M") + " " + x.interval.end.strftime("%H:%M"))
    if x.left is not None and x.left.maxrange >= start_time:
        search(x.left, start, end)
    if x.right is not None and x.right.maxrange >= start_time:
        search(x.right, start, end)


def is_overlap(start1: datetime, end1: datetime, start2: datetime, end2: datetime) -> bool:
    return start1 <= end2 and start2 <= end1


def left_shift(node: IntervalTreeNode) -> IntervalTreeNode:
    parent = node.parent
    rt = node.right
    if parent and parent.left == node:
        parent.left = rt
    elif parent and parent.right == node:
        parent.right = rt
    rt.parent = parent
    node.parent = rt
    node.right = rt.left
    rt.left = node
    return rt


def right_shift(node: IntervalTreeNode) -> IntervalTreeNode:
    parent = node.parent
    lf = node.left
    if parent and parent.left == node:
        parent.left = lf
    elif parent and parent.right == node:
        parent.right = lf
    lf.parent = parent
    node.parent = lf
    node.left = lf.right
    lf.right = node
    return lf


def print_tree(root: IntervalTreeNode, level: int = 1) -> None:
    if root is None:
        return
    maxrange = str(None) if root.maxrange is None else root.maxrange.strftime("%H:%M")
    print("| "*level + " --> " + root.interval.id + " " + root.interval.name + " " + root.interval.start.strftime("%H:%M") + " " + root.interval.end.strftime("%H:%M") + " " + root.color + " " + maxrange)
    print_tree(root.left, level + 1)
    print_tree(root.right, level + 1)

test.py

from IntervalTree import *
import unittest


class TreeTest(unittest.TestCase):
    def insert_test1(self):
        interval = Interval("000001", "Math", "9:00", "10:00")
        root = insert(None, IntervalTreeNode(interval))
        # print_tree(root)
        interval = Interval("000002", "Chinese", "7:00", "11:00")
        root = insert(root, IntervalTreeNode(interval))
        # print_tree(root)
        interval = Interval("000003", "Music", "11:00", "12:00")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000004", "PE", "5:00", "6:00")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000005", "Math II", "6:00", "5:00")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000006", "English", "13:00", "14:00")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000007", "English II", "12:00", "13:30")
        root = insert(root, IntervalTreeNode(interval))
        update_maxrange(root)
        print_tree(root)
        return

    def insert_test2(self):
        interval = Interval("000001", "Math", "9:41", "10:00")
        root = insert(None, IntervalTreeNode(interval))
        interval = Interval("000002", "Chinese", "9:38", "11:00")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000003", "Music", "9:31", "12:00")
        root = insert(root, IntervalTreeNode(interval))
        # print_tree(root)
        interval = Interval("000004", "PE", "9:12", "10:00")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000005", "Math II", "9:19", "15:00")
        root = insert(root, IntervalTreeNode(interval))
        # print_tree(root)
        interval = Interval("000006", "English", "9:08", "21:00")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000007", "English II", "12:00", "12:30")
        root = insert(root, IntervalTreeNode(interval))
        # update_maxrange(root)
        print_tree(root)
        return

    def shift_test(self):
        interval = Interval("000001", "Math", "9:00", "11:00")
        root = insert(None, IntervalTreeNode(interval))
        interval = Interval("000002", "PE", "10:00", "11:00")
        root.left = IntervalTreeNode(interval)
        interval = Interval("000003", "Chinese", "8:00", "12:00")
        root.right = IntervalTreeNode(interval)
        interval = Interval("000004", "Music", "13:00", "14:00")
        root.right.left = IntervalTreeNode(interval)
        print(" ")
        print_tree(root)
        root = left_shift(root)
        print_tree(root)
        print(" ")
        root = right_shift(root)
        print_tree(root)
        return

    def delete_test1(self):
        interval = Interval("000001", "Math", "9:41", "10:00")
        root = insert(None, IntervalTreeNode(interval))
        interval = Interval("000002", "Chinese", "9:38", "11:00")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000003", "Music", "9:31", "12:00")
        root = insert(root, IntervalTreeNode(interval))
        # print_tree(root)
        interval = Interval("000004", "PE", "9:12", "10:00")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000005", "Math II", "9:19", "15:00")
        root = insert(root, IntervalTreeNode(interval))
        # print_tree(root)
        interval = Interval("000006", "English", "9:08", "21:00")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000007", "English II", "9:45", "12:30")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000008", "Chinese II", "9:20", "12:30")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000009", "Chinese III", "9:07", "12:30")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000010", "Math III", "9:06", "12:30")
        root = insert(root, IntervalTreeNode(interval))
        # update_maxrange(root)
        print_tree(root)
        delete(root, "000004")
        delete(root, "000010")
        # update_maxrange(root)
        print_tree(root)
        return

    def delete_test_2_1_1(self):
        interval = Interval("000001", "Math", "9:38", "10:00")
        root = insert(None, IntervalTreeNode(interval))

        interval = Interval("000003", "Chinese", "9:41", "11:00")
        node = IntervalTreeNode(interval)
        root.right = node
        node.parent = root
        node.color = 'R'

        interval = Interval("000002", "Music", "9:31", "12:00")
        node = IntervalTreeNode(interval)
        root.left = node
        node.parent = root
        node.color = 'B'

        interval = Interval("000004", "Music II", "9:39", "12:00")
        node = IntervalTreeNode(interval)
        root.right.left = node
        node.parent = root.right
        node.color = 'B'

        interval = Interval("000005", "Music III", "9:42", "12:00")
        node = IntervalTreeNode(interval)
        root.right.right = node
        node.parent = root.right
        node.color = 'B'

        print_tree(root)
        root = delete(root, "000002")
        print_tree(root)

    def delete_test_2_1_2(self):
        # interval = Interval("000001", "Math", "9:38", "10:00")
        # root = insert(None, IntervalTreeNode(interval))

        # interval = Interval("000003", "Chinese", "9:41", "11:00")
        # node = IntervalTreeNode(interval)
        # root.right = node
        # node.parent = root
        # node.color = 'B'

        # interval = Interval("000002", "Music", "9:31", "12:00")
        # node = IntervalTreeNode(interval)
        # root.left = node
        # node.parent = root
        # node.color = 'B'

        # interval = Interval("000004", "Music II", "9:39", "12:00")
        # node = IntervalTreeNode(interval)
        # root.right.left = node
        # node.parent = root.right
        # node.color = 'R'

        # interval = Interval("000005", "Music III", "9:42", "12:00")
        # node = IntervalTreeNode(interval)
        # root.right.right = node
        # node.parent = root.right
        # node.color = 'R'

        # print_tree(root)
        # root = delete(root, "000002")
        # print_tree(root)
        interval = Interval("000001", "Math", "9:38", "10:00")
        root = insert(None, IntervalTreeNode(interval))

        interval = Interval("000003", "Chinese", "9:41", "11:00")
        node = IntervalTreeNode(interval)
        root.right = node
        node.parent = root
        node.color = 'B'

        interval = Interval("000002", "Music", "9:31", "12:00")
        node = IntervalTreeNode(interval)
        root.left = node
        node.parent = root
        node.color = 'B'

        interval = Interval("000004", "Music II", "9:39", "12:00")
        node = IntervalTreeNode(interval)
        root.right.left = node
        node.parent = root.right
        node.color = 'R'

        print_tree(root)
        root = delete(root, "000002")
        print_tree(root)

        # interval = Interval("000001", "Math", "9:38", "10:00")
        # root = insert(None, IntervalTreeNode(interval))

        # interval = Interval("000003", "Chinese", "9:41", "11:00")
        # node = IntervalTreeNode(interval)
        # root.right = node
        # node.parent = root
        # node.color = 'B'

        # interval = Interval("000002", "Music", "9:31", "12:00")
        # node = IntervalTreeNode(interval)
        # root.left = node
        # node.parent = root
        # node.color = 'B'

        # interval = Interval("000004", "Music II", "9:39", "12:00")
        # node = IntervalTreeNode(interval)
        # root.right.left = node
        # node.parent = root.right
        # node.color = 'B'

        # interval = Interval("000005", "Music III", "9:42", "12:00")
        # node = IntervalTreeNode(interval)
        # root.right.right = node
        # node.parent = root.right
        # node.color = 'B'

        # print_tree(root)
        # root = delete(root, "000002")
        # print_tree(root)

    def delete_test_2_2_1(self):
        interval = Interval("000001", "Math", "9:38", "10:00")
        root = insert(None, IntervalTreeNode(interval))

        interval = Interval("000003", "Chinese", "9:41", "11:00")
        node = IntervalTreeNode(interval)
        root.right = node
        node.parent = root
        node.color = 'B'

        interval = Interval("000002", "Music", "9:31", "12:00")
        node = IntervalTreeNode(interval)
        root.left = node
        node.parent = root
        node.color = 'R'

        interval = Interval("000004", "Music II", "9:39", "12:00")
        node = IntervalTreeNode(interval)
        root.left.left = node
        node.parent = root.left
        node.color = 'B'

        interval = Interval("000005", "Music III", "9:42", "12:00")
        node = IntervalTreeNode(interval)
        root.left.right = node
        node.parent = root.left
        node.color = 'B'

        print_tree(root)
        root = delete(root, "000003")
        print_tree(root)

    def delete_test_2_2_2(self):
        # interval = Interval("000001", "Math", "9:38", "10:00")
        # root = insert(None, IntervalTreeNode(interval))

        # interval = Interval("000003", "Chinese", "9:41", "11:00")
        # node = IntervalTreeNode(interval)
        # root.right = node
        # node.parent = root
        # node.color = 'B'

        # interval = Interval("000002", "Music", "9:31", "12:00")
        # node = IntervalTreeNode(interval)
        # root.left = node
        # node.parent = root
        # node.color = 'B'

        # interval = Interval("000004", "Music II", "9:39", "12:00")
        # node = IntervalTreeNode(interval)
        # root.left.left = node
        # node.parent = root.left
        # node.color = 'R'

        # interval = Interval("000005", "Music III", "9:42", "12:00")
        # node = IntervalTreeNode(interval)
        # root.left.right = node
        # node.parent = root.left
        # node.color = 'R'

        # print_tree(root)
        # root = delete(root, "000003")
        # print_tree(root)

        # interval = Interval("000001", "Math", "9:38", "10:00")
        # root = insert(None, IntervalTreeNode(interval))

        # interval = Interval("000003", "Chinese", "9:41", "11:00")
        # node = IntervalTreeNode(interval)
        # root.right = node
        # node.parent = root
        # node.color = 'B'

        # interval = Interval("000002", "Music", "9:31", "12:00")
        # node = IntervalTreeNode(interval)
        # root.left = node
        # node.parent = root
        # node.color = 'B'

        # interval = Interval("000004", "Music II", "9:39", "12:00")
        # node = IntervalTreeNode(interval)
        # root.left.right = node
        # node.parent = root.left
        # node.color = 'R'

        # print_tree(root)
        # root = delete(root, "000003")
        # print_tree(root)

        interval = Interval("000001", "Math", "9:38", "10:00")
        root = insert(None, IntervalTreeNode(interval))

        interval = Interval("000003", "Chinese", "9:41", "11:00")
        node = IntervalTreeNode(interval)
        root.right = node
        node.parent = root
        node.color = 'B'

        interval = Interval("000002", "Music", "9:31", "12:00")
        node = IntervalTreeNode(interval)
        root.left = node
        node.parent = root
        node.color = 'B'

        interval = Interval("000004", "Music II", "9:39", "12:00")
        node = IntervalTreeNode(interval)
        root.left.left = node
        node.parent = root.left
        node.color = 'B'

        interval = Interval("000005", "Music III", "9:42", "12:00")
        node = IntervalTreeNode(interval)
        root.left.right = node
        node.parent = root.left
        node.color = 'B'

        print_tree(root)
        root = delete(root, "000003")
        print_tree(root)


    def search_test(self):
        interval = Interval("000001", "Math", "9:41", "10:00")
        root = insert(None, IntervalTreeNode(interval))
        interval = Interval("000002", "Chinese", "9:38", "11:00")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000003", "Music", "9:31", "12:00")
        root = insert(root, IntervalTreeNode(interval))
        # print_tree(root)
        interval = Interval("000004", "PE", "9:12", "10:00")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000005", "Math II", "9:19", "15:00")
        root = insert(root, IntervalTreeNode(interval))
        # print_tree(root)
        interval = Interval("000006", "English", "9:08", "21:00")
        root = insert(root, IntervalTreeNode(interval))
        interval = Interval("000007", "English II", "12:00", "12:30")
        root = insert(root, IntervalTreeNode(interval))
        # update_maxrange(root)
        print_tree(root)
        search(root, "15:01", "16:00")
        return

if __name__ == "__main__":
    unittest.TextTestRunner().run(TreeTest("search_test"))
    # unittest.TextTestRunner().run(TreeTest("shift_test"))

参考文献

[1] 30 张图带你彻底理解红黑树

[2] 红黑树 C++ 实现

打赏

版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！