Binary Search Tree
Tree
Binary Search Tree

Node
  1. #!/usr/bin/python
  2. """ A model containing Node class """
  3.  
  4. __author__ = "Lin Chen"
  5. __version__ = "0.1"
  6.  
  7. class Node:
  8. """Single node in the binary search tree"""
  9.  
  10. def __init__(self, data):
  11. """Initialize a Node
  12. Args:
  13. data : data saved in the node
  14. """
  15. self._data = data
  16. self._left = None
  17. self._right = None
  18. self._parent = None
  19.  
  20. @property
  21. def data(self):
  22. return self._data
  23.  
  24. @data.setter
  25. def data(self, d):
  26. self._data = d
  27.  
  28. @data.deleter
  29. def data(self):
  30. del self._data
  31.  
  32. @property
  33. def left(self):
  34. return self._left
  35.  
  36. @left.setter
  37. def left(self, n):
  38. self._left = n
  39.  
  40. @left.deleter
  41. def left(self):
  42. del self._left
  43.  
  44. @property
  45. def right(self):
  46. return self._right
  47.  
  48. @right.setter
  49. def right(self, n):
  50. self._right = n
  51.  
  52. @right.deleter
  53. def right(self):
  54. del self._right
  55.  
  56. @property
  57. def parent(self):
  58. return self._parent
  59.  
  60. @parent.setter
  61. def parent(self, n):
  62. self._parent = n
  63.  
  64. @parent.deleter
  65. def parent(self):
  66. del self._parent
  67.  
  68. def __str__(self):
  69. return str(self._data)
BST
  1. #!/usr/bin/python
  2. """ A model containing Binary Search Tree"""
  3.  
  4. from NodeModule import Node
  5.  
  6. class BST(object):
  7. """Class of binary search tree"""
  8.  
  9. def __init__(self):
  10. """Initialize a binary search tree
  11. """
  12. self._root = None
  13.  
  14. @property
  15. def root(self):
  16. return self._root
  17.  
  18. @root.setter
  19. def root(self, n):
  20. self._root = n
  21.  
  22. @root.deleter
  23. def root(self):
  24. del self._root
  25.  
  26. def isEmpty(self):
  27. return (self._root is None)
  28.  
  29. def size(self):
  30. return self.getSize(self._root)
  31.  
  32. def getSize(self, n):
  33. if n is None:
  34. return 0
  35.  
  36. return 1 + self.getSize(n.left) + self.getSize(n.right)
  37.  
  38. def height(self):
  39. return self.getHeight(self._root)
  40.  
  41. def getHeight(self, n):
  42. if n is None:
  43. return 0
  44. if n.left is None and n.right is None:
  45. return 1
  46.  
  47. l = self.getHeight(n.left)
  48. r = self.getHeight(n.right)
  49.  
  50. h = 1+l if l > r else 1+r
  51.  
  52. return h
  53.  
  54. def inorderWalk(self):
  55. """Print elements in ascending order, O(n)"""
  56. if self._root is not None:
  57. self.printLDR(self._root)
  58. print
  59.  
  60. def printLDR(self, n):
  61. if n is None:
  62. return
  63. self.printLDR(n.left)
  64. print('<'+str(n)+'>'),
  65. self.printLDR(n.right)
  66.  
  67. def preWalk(self):
  68. """Print element in pre-order, O(n)"""
  69. if self._root is not None:
  70. self.printDLR(self._root)
  71. print
  72.  
  73. def printDLR(self, n):
  74. if n is None:
  75. return
  76. print('<'+str(n)+'>'),
  77. self.printDLR(n.left)
  78. self.printDLR(n.right)
  79.  
  80. def postWalk(self):
  81. """Print element in pre-order, O(n)"""
  82. if self._root is not None:
  83. self.printLRD(self._root)
  84. print
  85.  
  86. def printLRD(self, n):
  87. if n is None:
  88. return
  89. self.printLRD(n.left)
  90. self.printLRD(n.right)
  91. print('<'+str(n)+'>'),
  92.  
  93. def search(self, v):
  94. """Search if a value has been saved in the binary search tree
  95. Returns:
  96. Node, return the node containing the value if find it in tree, None otherwise"""
  97. if self._root is not None:
  98. return self.searchTree(self._root, v)
  99.  
  100. def searchTree(self, n, v):
  101. if n is None or v == n.data:
  102. return n
  103. if v < n.data:
  104. return self.searchTree(n.left, v)
  105. else:
  106. return self.searchTree(n.right, v)
  107.  
  108. def min(self):
  109. """Return node containing minimum value in the binary search tree"""
  110. n = self.getMin(self._root)
  111. return n
  112.  
  113. def getMin(self, n):
  114. if n is None or n.left is None:
  115. return n
  116. return self.getMin(n.left)
  117.  
  118. def max(self):
  119. """Return node containing maximum value in the binary search tree"""
  120. n = self.getMax(self._root)
  121. return n
  122.  
  123. def getMax(self, n):
  124. if n is None or n.right is None:
  125. return n
  126. return self.getMax(n.right)
  127.  
  128. def successor(self, v):
  129. """Return the node with the smallest key greater than v"""
  130. n = self.search(v)
  131. if n is None:
  132. return None
  133.  
  134. return self.getSuccessor(n)
  135.  
  136. def getSuccessor(self, n):
  137. if n.right is not None:
  138. return self.getMin(n.right)
  139. y = n.parent
  140. while (y is not None) and (n is y.right):
  141. n = y
  142. y = y.parent
  143. return y
  144.  
  145. def predecessor(self, v):
  146. """Return the node with the largest key less than v"""
  147. n = self.search(v)
  148. if n is None:
  149. return None
  150.  
  151. return self.getPredecessor(n)
  152.  
  153. def getPredecessor(self, n):
  154. if n.left is not None:
  155. return self.getMax(n.left)
  156. y = n.parent
  157. while (y is not None) and (n is y.left):
  158. n = y
  159. y = y.parent
  160. return y
  161.  
  162. def insert(self, v):
  163. if self.search(v) is not None:
  164. return
  165.  
  166. p = None
  167. current = self._root
  168.  
  169. while current is not None:
  170. p = current
  171. current = p.left if v < p.data else p.right
  172.  
  173. n = Node(v)
  174. n.parent = p
  175.  
  176. if p is None:
  177. self._root = n
  178. else:
  179. if v < p.data:
  180. p.left = n
  181. else:
  182. p.right = n
  183.  
  184. def transplant(self, u, v):
  185. """Replaces the subtree rooted at node u with the subtree rooted at node v"""
  186. if u.parent is None:
  187. self._root = v
  188. elif u == u.parent.left:
  189. u.parent.left = v
  190. else:
  191. u.parent.right = v
  192. if v is not None:
  193. v.parent = u.parent
  194.  
  195. def delete(self, e):
  196. """Delete the node which contains data e"""
  197. z = self.search(e)
  198.  
  199. if z is None:
  200. return;
  201.  
  202. if z.left is None:
  203. self.transplant(z, z.right)
  204. elif z.right is None:
  205. self.transplant(z, z.left)
  206. else:
  207. y = self.getMin(z.right)
  208. if y.parent != z:
  209. self.transplant(y, y.right)
  210. y.right = z.right
  211. y.right.parent = y
  212. self.transplant(z, y)
  213. y.left = z.left
  214. y.left.parent = y
Successor
  • Node has right child
  • Node has no right child
  • Predecessor
  • Node has left child
  • Node has no left child
  • Transplant

    Delete
  • Node has no children, remove it by modifying its parent to replac the node with None as its child
  • Node has just one child, take the node's position in the tree by modifying the node's parent to replace the node by the node's child
  • Node has two children, find the node's successor. Have the successor take the node's position in the tree. The rest of the ndoe's original right subtree becomes the successor's new right subtree, and the node's left subtree becomes the successor's new left substree
  • Node has only right child, or has no child
  • Node has only left child
  • Node has two children
  • BSTTest
    1. #!/usr/bin/python
    2.  
    3. from BSTModule import BST
    4.  
    5. def main():
    6. t = BST();
    7.  
    8. # Create tree
    9. t.insert(8);
    10. t.insert(3);
    11. t.insert(10);
    12. t.insert(1);
    13. t.insert(6);
    14. t.insert(14);
    15. t.insert(4);
    16. t.insert(7);
    17. t.insert(13);
    18. t.insert(15);
    19.  
    20. # Display tree
    21. t.inorderWalk()
    22. t.preWalk()
    23. t.postWalk()
    24.  
    25. # size
    26. print 'Size: ', t.size()
    27.  
    28. # height
    29. print 'Height: ', t.height()
    30.  
    31. # search
    32. print(t.search(7)) # 7
    33. print(t.search(20)) # None
    34.  
    35. # min
    36. print(t.min()) # 1
    37.  
    38. # max
    39. print(t.max()) # 15
    40.  
    41. # successor
    42. print(t.successor(3)) # 4
    43. print(t.successor(7)) # 8
    44. print(t.successor(8)) # 10
    45. print(t.successor(15)) # None
    46.  
    47. # predecessor
    48. print(t.predecessor(13)) # 10
    49. print(t.predecessor(10)) # 8
    50. print(t.predecessor(8)) # 7
    51. print(t.predecessor(1)) # None
    52.  
    53. # delete
    54. t.delete(3);
    55. t.inorderWalk();
    56.  
    57. if __name__ == '__main__':
    58. main()
    Reference