1
我想在Python中構建2-3-4樹。到目前爲止，插入似乎正在處理高度3左右的節點。之後，數據似乎被丟棄而不是被插入到樹中。我不確定爲什麼會發生這種情況，並且已經多次檢查過我的代碼的兩倍和三倍。我在插入代碼附近評論了我從哪裏獲得插入算法。提前感謝您對我的問題的任何見解。234樹python
import re
class Node:
def __init__(self, newInfo = None, p = None, q = None,
r = None, s = None, parent = None):
#initilize parent/child links
self.children = [p, q, r, s]
self.parent = parent
#initialize data
self.info = [ newInfo, None, None ]
class TwoThreeFourTree:
def __init__(self):
self.root = Node()
# Built in sort sinks None types to front, which
# is opposite of how info was structured to work,
# Using this sort will push None values to back.
def sortNode(self, curr):
c = []
for i in curr.info:
if i is not None:
c.append(i)
c.sort()
for i in range(3-len(c)):
c.append(None)
return c
# Built in len counts None, this one doesn't.
def length(self, node):
i = 0
for info in node:
if info is not None:
i = i + 1
return i
def isLeaf(self, node):
for child in node.children:
if child is not None:
return False
return True
def isOrphan(self, node):
if node.parent is None:
return True
return False
def lookup(self, userStr, reg):
curr = self.root
while curr is not None:
#Two Node
if self.length(curr.info) is 1:
if re.match(reg, str(curr.info[0])) is not None:
return curr.info[0]
else:
if userStr < curr.info[0]:
curr = curr.children[0]
else:
curr = curr.children[1]
#Three Node
elif self.length(curr.info) is 2:
for item in curr.info:
if re.match(reg, str(item)) is not None:
return item
if userStr < curr.info[0]:
curr = curr.children[0]
elif userStr < curr.info[1]:
curr = curr.children[1]
else:
curr = curr.children[2]
#Four Node
elif self.length(curr.info) is 3:
for item in curr.info:
if item is not None:
if re.match(reg, str(item)) is not None:
return item
if userStr < curr.info[0]:
curr = curr.children[0]
elif userStr < curr.info[1]:
curr = curr.children[1]
elif userStr < curr.info[2]:
curr = curr.children[2]
else:
curr = curr.children[3]
def inorder(self, node, retlst = None):
if retlst is None:
retlst = []
if node.children[0]:
retlst = self.inorder(node.children[0], retlst)
retlst += [node.info[0]]
if node.children[1]:
retlst = self.inorder(node.children[1], retlst)
retlst += [node.info[1]]
if node.children[2]:
retlst = self.inorder(node.children[2], retlst)
retlst += [node.info[2]]
if node.children[3]:
retlst = self.inorder(node.children[3], retst)
return retlst
## Using Algorithm from: http://www.clear.rice.edu/comp212/01-fall/lectures/33/
def insert(self, info, node):
curr = node
if self.length(curr.info) == 0: # curr is empty
curr.info[0] = info
return True
elif self.length(curr.info) == 1: # curr is two node.
if self.isLeaf(curr):
curr.info[1] = info
curr.info = self.sortNode(curr)
return True
else:
if info < curr.info[0]:
self.insert(info, curr.children[0])
else:
self.insert(info, curr.children[1])
elif self.length(curr.info) == 2: # curr is 3 node
if self.isLeaf(curr):
curr.info[2] = info
curr.info = self.sortNode(curr)
return True
else:
if info < curr.info[0]:
self.insert(info, curr.children[0])
elif info < curr.info[1]:
self.insert(info, curr.children[1])
elif info > curr.info[2]:
self.insert(info, curr.children[2])
elif self.length(curr.info) == 3: # curr is 4 node
if self.isOrphan(curr): # curr has no parent
curr = Node(curr.info[1],
Node(curr.info[0], curr.children[0], curr.children[1]),
Node(curr.info[2], curr.children[2], curr.children[3]))
for child in curr.children:
if child is not None:
child.parent = curr
self.root = curr
self.insert(info, self.root)
else: #curr has a parent
if self.length(curr.parent.info) == 1: # Parent is Two Node:
if curr.parent.children[0] == curr:# cur is lst.
#If P = [curr, M, p-rst], then P becomes [[lst, X, mlst], Y, [mrst, Z, rst], M, p-rst].
curr.parent.info[1] = curr.info[1]
curr.parent.info = self.sortNode(curr.parent)
curr.parent.children[2] = curr.parent.children[1]
curr.parent.children[1] = Node(curr.info[2], curr.children[2], curr.children[3], None, None, curr.parent)
curr.parent.children[0] = Node(curr.info[0], curr.children[0], curr.children[1], None, None, curr.parent)
self.insert(info, self.root)
elif curr.parent.children[1] == curr: # curr is rst.
#If P = [p-lst, M, curr], then P becomes [p-lst, M, [lst, X, mlst], Y, [mrst, Z, rst]].
curr.parent.info[1] = curr.info[1]
curr.parent.info = self.sortNode(curr.parent)
curr.parent.children[2] = Node(curr.info[2], curr.children[2], curr.children[3], None, None, curr.parent)
curr.parent.children[1] = Node(curr.info[0], curr.children[0], curr.children[1], None, None, curr.parent)
self.insert(info, self.root)
elif self.length(curr.parent.info) == 2: # Parent is Three Node:
if curr.parent.children[0] == curr: # curr is lst
#If P = [curr, M1, p-mst, M2, p-rst], then P becomes [[lst, X, mlst], Y, [mrst, Z, rst], M1, p-mst, M2, p-rst].
curr.parent.info[2] = curr.info[1]
curr.parent.info = self.sortNode(curr.parent)
curr.parent.children[3] = curr.parent.children[2]
curr.parent.children[2] = curr.parent.children[1]
curr.parent.children[1] = Node(curr.info[2], curr.children[2], curr.children[3], None, None, curr.parent)
curr.parent.children[0] = Node(curr.info[0], curr.children[0], curr.children[1], None, None, curr.parent)
self.insert(info, self.root)
elif curr.parent.children[1] == curr: # curr is mst
#If P = [p-lst, M1, curr, M2, p-rst], then P becomes [p-lst, M1,[lst, X, mlst], Y, [mrst, Z, rst], M2, p-rst].
curr.parent.info[2] = curr.info[1]
curr.parent.info = self.sortNode(curr.parent)
curr.parent.children[3] = curr.parent.children[2]
curr.parent.children[2] = Node(curr.info[2], curr.children[2], curr.children[3], None, None, curr.parent)
curr.parent.children[1] = Node(curr.info[0], curr.children[0], curr.children[1], None, None, curr.parent)
self.insert(info, self.root)
elif curr.parent.children[2] == curr: # curr is rst
#If P = [p-lst, M1, p-mst, M2, curr], then P becomes [p-lst, M1, p-mst, M2, [lst, X, mlst], Y, [mrst, Z, rst]].
curr.parent.info[2] = curr.info[1]
curr.parent.info = self.sortNode(curr.parent)
curr.parent.children[3] = Node(curr.info[2], curr.children[2], curr.children[3], None, None, curr.parent)
curr.parent.children[2] = Node(curr.info[0], curr.children[0], curr.children[1], None, None, curr.parent)
self.insert(info, self.root)