2-3 дерево в Python


Я не смог найти реализацию учебника в 2-3 дерево в Python, поэтому я решила попробовать сделать свою.

class Node:
    def __init__(self, data, parent=None):
        self.nodeType = 2
        self.d1, self.d2, self.d3 = data, None, None
        self.c1, self.c2, self.c3, self.c4 = None, None, None, None
        self.parent = parent
    def push(self, data):
        if self.nodeType == 2:
            self.nodeType = 3
            self.d1, self.d2 = sorted([self.d1, data])
        elif self.nodeType == 3:
            self.nodeType = 4
            self.d1, self.d2, self.d3 = sorted([self.d1, self.d2, data])
    def split(self):
        # Case O, if there is nothing to do
        if self.nodeType < 4:
            return
        # Case I, splitting when there is no parent
        if self.parent == None:
            leftChild = Node(self.d1, self)
            rightChild = Node(self.d3, self)
            leftChild.c1, leftChild.c2 = self.c1, self.c2
            rightChild.c1, rightChild.c2 = self.c3, self.c4
            self.nodeType = 2
            self.d1, self.d2, self.d3 = self.d2, None, None
            self.c1, self.c2, self.c3, self.c4 = leftChild, rightChild, None, None
        # Case II, when parent is a 2-node
        elif self.parent.nodeType == 2:
            # subcase a: when the current node is the left child of the parent node
            if self == self.parent.c1:
                midChild = Node(self.d3, self.parent)
                midChild.c1, midChild.c2 = self.c3, self.c4
                self.parent.push(self.d2)
                self.parent.c1, self.parent.c2, self.parent.c3 = self.parent.c1, midChild, self.parent.c2
                self.nodeType = 2
                self.c1, self.c2, self.c3, self.c4 = self.c1, self.c2, None, None
                self.d1, self.d2, self.d3 = self.d1, None, None
            # subcase b: when the current node is the right child of the parent node
            elif self == self.parent.c2:
                midChild = Node(self.d1, self.parent)
                midChild.c1, midChild.c2 = self.c1, self.c2
                self.parent.push(self.d2)
                self.parent.c1, self.parent.c2, self.parent.c3 = self.parent.c1, midChild, self.parent.c2
                self.nodeType = 2
                self.c1, self.c2, self.c3, self.c4 = self.c3, self.c4, None, None
                self.d1, self.d2, self.d3 = self.d3, None, None
        # Case III, when parent is a 3-node
        elif self.parent.nodeType == 3:
            # subcase a: when the current node is the left child of the parent node
            if self == self.parent.c1:
                newNode = Node(self.d3, self.parent)
                newNode.c1, newNode.c2 = self.c3, self.c4
                self.parent.push(self.d2)
                self.parent.c1, self.parent.c2, self.parent.c3, self.parent.c4 = self.parent.c1, newNode, self.parent.c2, self.parent.c3
                self.nodeType = 2
                self.c1, self.c2, self.c3, self.c4 = self.c1, self.c2, None, None
                self.d1, self.d2, self.d3 = self.d1, None, None
            # subcase b: when the current node is the middle child of the parent node
            elif self == self.parent.c2:
                newNode = Node(self.d3, self.parent)
                newNode.c1, newNode.c2 = self.c3, self.c4
                self.parent.push(self.d2)
                self.parent.c1, self.parent.c2, self.parent.c3, self.parent.c4 = self.parent.c1, self.parent.c2, newNode, self.parent.c3
                self.nodeType = 2
                self.c1, self.c2, self.c3, self.c4 = self.c1, self.c2, None, None
                self.d1, self.d2, self.d3 = self.d1, None, None
            # subcase c: when the current node is the right node of the parent node
            elif self == self.parent.c3:
                newNode = Node(self.d1, self.parent)
                newNode.c1, newNode.c2 = self.c1, self.c2
                self.parent.push(self.d2)
                self.parent.c1, self.parent.c2, self.parent.c3, self.parent.c4 = self.parent.c1, self.parent.c2, newNode, self.parent.c3
                self.nodeType = 2
                self.c1, self.c2, self.c3, self.c4 = self.c3, self.c4, None, None
                self.d1, self.d2, self.d3 = self.d3, None, None
            # now recursively split the parent
            self.parent.split()
    def insert(self, data):
        # if this node is a leaf
        if self.c1 == None:
            self.push(data)
            self.split()
        # if this node is not a leaf, and a 2-node
        elif self.nodeType == 2:
            if data < self.d1:
                self.c1.insert(data)
            else:
                self.c2.insert(data)
        # if this node is a 3-node
        elif self.nodeType == 3:
            if data < self.d1:
                self.c1.insert(data)
            elif data > self.d3:
                self.c3.insert(data)
            else:
                self.c2.insert(data)
    def find(self, data):
        # if this node is a leaf
        if self.c1 == None:
            if data in [self.d1, self.d2, self.d3]:
                return True
            else:
                return False
        # if this node is not a leaf, and a 2-node
        elif self.nodeType == 2:
            if data < self.d1:
                self.c1.find(data)
            else:
                self.c2.find(data)
        # if this node is a 3-node
        elif self.nodeType == 3:
            if data < self.d1:
                self.c1.find(data)
            elif data > self.d3:
                self.c3.find(data)
            else:
                self.c2.find(data)

class TwoThreeTree:
    def __init__(self):
        self.isEmpty = True
        self.root = None
    def insert(self, data):
        if self.isEmpty:
            self.isEmpty = False
            self.root = Node(data)
        else:
            self.root.insert(data)
    def find(self, data):
        if self.isEmpty:
            return False
        else:
            self.root.find(data)

Общее мнение о стиле кодирования приветствуется. Я тоже ищу конкретные отзывы:

  • Это, кажется, много дел. Как я могу повторно использовать больше кода, чтобы сделать это более элегантно? Я также считаю, что умение организовать этот код более красиво означает, что я смогу обобщить на более общий B-дерева. Как я могу это сделать?


627
5
задан 25 февраля 2018 в 04:02 Источник Поделиться
Комментарии
1 ответ

Мои впечатления после прочтения вопрос:


  • Я уверен что есть статья в Википедии на 2-3 деревьев. Но ОП дал ссылку. :(

  • Нет док блок, описывающий 2-3 деревья

  • Не инвариант

  • Много, как вы говорите, "дела", закодированных в если/Элиф заявления, которые, вероятно, должны быть подклассами.

Покопавшись в:

Проверяем документы

У вас больше полей, чем это необходимо. 2-3 узлов дерева с 2 детьми и поле данных 1, или 3 детей в 2 данных областях. У вас есть self.d3 и self.c4 в свой инициализатор...

Собственный узел

У вас есть класс и класс узла. Переместите класс узел(ы) в дереве:

class TwoThreeTree:
'''Implement a 2-3 tree using pure Python 3.

See https://en.wikipedia.org/wiki/2-3_tree

'''
class _2node:
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right

def insert(self, data):
...

def __init__(self):
self.root = None

def is_empty(self):
return self.root is None

def insert(self, data):
if self.is_empty():
self.root = self._2node(data)
else:
self.root = self.root.insert(data)

Упростить и подкласс

Как только вы получили узлов внутри класса дерево, разделить их. Делает Python утка-типирование, так что им не нужно, чтобы общий предок (хотя они могут, если вы найдете достаточно поведение наследования).

class _2node:
def __init__(self, data, left=None, right=None):
...
def insert(self, ...):
...

class _3node:
def __init__(self, data1, data2=None, left=None, right=None):
...
def insert(self, ...):
...

Вы, возможно, пожелает добавить .parent ссылка, указывающая вверх по дереву, чтобы упростить разбиение кода.

Добавить инвариант

Напиши сам метод (или методы) называется invariant(). Утверждать, что вещи, которые вы находите, чтобы утверждать - Я думаю, что в статье Википедии есть несколько довольно серьезных кандидатов. Называйте это, когда вы собираетесь покинуть публичный метод, и где-нибудь вы чувствуете необходимость.

5
ответ дан 25 февраля 2018 в 05:02 Источник Поделиться