python平衡查找树AVL

本文阅读 1 分钟
首页 Python笔记 正文
  1. # 构建二叉查找树(非平衡)
  2. class TreeNode:
  3. def __init__(self, key, val, left = None, right = None, parent = None):
  4. self.key = key
  5. self.payload = val
  6. self.leftChild = left
  7. self.rightChild = right
  8. self.parent= parent
  9. def hasLeftChild(self):
  10. return self.leftChild
  11. def hasRightChild(self):
  12. return self.rightChild
  13. def isLeftChild(self):
  14. return self.parent and self.parent.leftChild == self
  15. def isRightChild(self):
  16. return self.parent and self.parent.rightChild == self
  17. def isRoot(self):
  18. return not self.parent
  19. def isLeaf(self):
  20. return not (self.rightChild or self.leftChild)
  21. def hasAnyChildren(self):
  22. return self.rightChild or self.leftChild
  23. def hasBothChildren(self):
  24. return self.rightChild and self.leftChild
  25. def replaceNodeData(self, key, value, lc, rc):
  26. self.key = key
  27. self.payload = value
  28. self.leftChild = lc
  29. self.rightChild = rc
  30. if self.hasLeftChild():
  31. self.leftChild.parent = self
  32. if self.hasRightChild():
  33. self.rightChild.parent = self
  34. class BinarySearchTree:
  35. def __init__(self):
  36. self.root = None
  37. self.size = 0
  38. def length(self):
  39. return self.size
  40. def __len__(self):
  41. return self.size
  42. def __iter__(self):
  43. return self.root.__iter__()
  44. def put(self, key, val):
  45. if self.root:
  46. self._put(key, val, self.root)
  47. else:
  48. self.root = TreeNode(key, val)
  49. self.size = self.size + 1
  50. def _put(self, key, val, currentNode):
  51. if key < currentNode.key:
  52. if currentNode.hasLeftChild():
  53. self._put(key, val, currentNode.leftChild)
  54. else:
  55. currentNode.leftChild = TreeNode(key, val, parent=currentNode)
  56. self.updateBalance(currentNode.leftChild)
  57. else:
  58. if currentNode.hasRightChild():
  59. self._put(key, val, currentNode.rightChild)
  60. else:
  61. currentNode.rightChild = TreeNode(key, val, parent=currentNode)
  62. self.updateBalance(currentNode.rightChild)
  63. def updateBalance(self, node):
  64. if node.balanceFactor > 1 or node.balanceFactor < -1:
  65. self.rebalance(node)
  66. return
  67. if node.parent != None:
  68. if node.isLeftChild():
  69. node.parent.balanceFactor += 1
  70. elif node.isRightChild():
  71. node.parent.balanceFactor -= 1
  72. if node.parent.balanceFactor != 0:
  73. self.updateBalance(node.parent)
  74. def rotateLeft(self, rotRoot):
  75. newRoot = rotRoot.rightChild
  76. rotRoot.rightChild = newRoot.leftChild
  77. if newRoot.leftChild != None:
  78. newRoot.leftChild.parent = rotRoot
  79. newRoot.parent = rotRoot.parent
  80. if rotRoot.isRoot():
  81. self.root = newRoot
  82. else:
  83. if rotRoot.isLeftChild():
  84. rotRoot.parent.leftChild = newRoot
  85. else:
  86. rotRoot.parent.rightChild = newRoot
  87. newRoot.leftChild = rotRoot
  88. rotRoot.parent = newRoot
  89. rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0)
  90. newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0)
  91. def rotateRight(self, rotRoot):
  92. newRoot = rotRoot.leftChild
  93. rotRoot.leftChild = newRoot.rightChild
  94. if newRoot.rightChild != None:
  95. newRoot.rightChild.parent = rotRoot
  96. newRoot.parent = rotRoot.parent
  97. if rotRoot.isRoot():
  98. self.root = newRoot
  99. else:
  100. if rotRoot.isRightChild():
  101. rotRoot.parent.rightChild = newRoot
  102. else:
  103. rotRoot.parent.rightChild = newRoot
  104. newRoot.rightChild = rotRoot
  105. rotRoot.parent = newRoot
  106. rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0)
  107. newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0)
  108. def rebalance(self, node):
  109. if node.balanceFactor < 0:
  110. if node.rightChild.balanceFactor > 0:
  111. self.rotateRight(node.rightChild)
  112. self.rotateLeft(node)
  113. else:
  114. self.rotateLeft(node)
  115. elif node.balanceFactor > 0:
  116. if node.leftChild.balanceFactor < 0:
  117. self.rotateLeft(node.leftChild)
  118. self.rotateRight(node)
  119. else:
  120. self.rotateRight(node)
  121. def __setitem__(self, k, v):
  122. self.put(k, v)
  123. def get(self, key):
  124. if self.root:
  125. res = self._get(key, self.root)
  126. if res:
  127. return res.payload
  128. else:
  129. return None
  130. else:
  131. return None
  132. def _get(self, key, currentNode):
  133. if not currentNode:
  134. return None
  135. elif currentNode.key == key:
  136. return currentNode
  137. elif key < currentNode.key:
  138. return self._get(key, currentNode.leftChild)
  139. else:
  140. return self._get(key, currentNode.rightChild)
  141. def __getitem__(self, key):
  142. return self.get(key)
  143. def __contains__(self, key):
  144. if self._get(key, self.root):
  145. return True
  146. else:
  147. return False
  148. def delete(self, key):
  149. if self.size > 1:
  150. nodeToRemove = self._get(key, self.root)
  151. if nodeToRemove:
  152. self.remove(nodeToRemove)
  153. self.size -= 1
  154. else:
  155. raise KeyError('Error, key not in tree')
  156. elif self.size == 1 and self.root.key == key:
  157. self.root = None
  158. self.size = self.size - 1
  159. else:
  160. raise KeyError('Error, key not in tree')
  161. def __delitem__(self, key):
  162. self.delete(key)
  163. def spliceOut(self):
  164. if self.isLeaf():
  165. if self.isLeftChild():
  166. self.parent.leftChild = None
  167. else:
  168. self.parent.rightChild = None
  169. elif self.hasAnyChildren():
  170. if self.hasLeftChild():
  171. if self.isLeftChild():
  172. self.parent.leftChild = self.leftChild
  173. else:
  174. self.parent.rightChild = self.leftChild
  175. self.leftChild.parent = self.parent
  176. else:
  177. if self.isLeftChild():
  178. self.parent.leftChild = self.rightChild
  179. else:
  180. self.parent.rightChild = self.rightChild
  181. self.rightChild.parent = self.parent
  182. def findSuccessor(self):
  183. succ = None
  184. if self.hasRightChild():
  185. succ = self.rightChild.findMin()
  186. else:
  187. if self.parent:
  188. if self.isLeftChild():
  189. succ = self.parent
  190. else:
  191. self.parent.rightChild = None
  192. succ = self.parent.findSuccessor()
  193. self.parent.rightChild = self
  194. return succ
  195. def findMin(self):
  196. current = self
  197. while current.hasLeftChild():
  198. current = current.leftChild
  199. return current
  200. def remove(self, currentNode):
  201. if currentNode.isLeaf(): # leaf
  202. if currentNode == currentNode.parent.leftChild:
  203. currentNode.parent.leftChild = None
  204. else:
  205. currentNode.parent.rightChild = None
  206. elif currentNode.hasBothChildren(): # interior
  207. succ = currentNode.findSuccessor()
  208. succ.spliceOut()
  209. currentNode.key = succ.key
  210. currentNode.payload = succ.payload
  211. else: # this node has one child
  212. if currentNode.hasLeftChild():
  213. if currentNode.isLeftChild():
  214. currentNode.leftChild.parent = currentNode.parent
  215. currentNode.parent.leftChild = currentNode.leftChild
  216. elif currentNode.isRightChild():
  217. currentNode.leftChild.parent = currentNode.parent
  218. currentNode.parent.rightChild = currentNode.leftChild
  219. else:
  220. currentNode.replaceNodeData(currentNode.leftChild.key,
  221. currentNode.leftChild.payload,
  222. currentNode.leftChild.leftChild,
  223. currentNode.leftChild.rightChild)
  224. else:
  225. if currentNode.isLeftChild():
  226. currentNode.rightChild.parent = currentNode.parent
  227. currentNode.parent.leftChild = currentNode.rightChild
  228. elif currentNode.isRightChild():
  229. currentNode.rightChild.parent = currentNode.parent
  230. currentNode.parent.rightChild = currentNode.rightChild
  231. else:
  232. currentNode.replaceNodeData(currentNode.rightChild.key,
  233. currentNode.rightChild.payload,
  234. currentNode.rightChild.leftChild,
  235. currentNode.rightChild.rightChild)
  236. mytree = BinarySearchTree()
  237. mytree[3]="red"
  238. mytree[4]="blue"
  239. mytree[6]="yellow"
  240. mytree[2]="at"
  241. print(mytree[6])
  242. print(mytree[2])
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

python链表及常见操作
« 上一篇 01-21
python三种方法检测变位词Anagram
下一篇 » 01-21

发表评论