SHARE
TWEET

Untitled

a guest Sep 17th, 2019 458 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class BinarySearchTreeNode: CustomStringConvertible {
  2.   public private(set) var value: Int
  3.   var left: BinarySearchTreeNode?
  4.   var right: BinarySearchTreeNode?
  5.   var parent:BinarySearchTreeNode?
  6.  
  7.   var leftCount = 0
  8.   var rightCount = 0
  9.  
  10.   var description: String {
  11.     return "Value: \(value); leftCount: \(leftCount); rightCount: \(rightCount)"
  12.   }
  13.  
  14.   init(value: Int) {
  15.     self.value = value
  16.   }
  17.  
  18. }
  19.  
  20. class BinarySearchTree {
  21.   private var root: BinarySearchTreeNode?
  22.  
  23.   init(rootValue value: Int) {
  24.     root = BinarySearchTreeNode(value: value)
  25.   }
  26.  
  27.   public func insert(value: Int) {
  28.     guard let tempRoot = self.root else {
  29.       self.root = BinarySearchTreeNode(value: value)
  30.       return
  31.     }
  32.    
  33.     func recursiveInsert(root: BinarySearchTreeNode?) {
  34.       guard let root = root else {
  35.         return
  36.       }
  37.      
  38.       if value <= root.value && root.left == nil {
  39.         root.left = BinarySearchTreeNode(value: value)
  40.         root.left?.parent = root
  41.       }
  42.       else if value > root.value && root.right == nil {
  43.         root.right = BinarySearchTreeNode(value: value)
  44.         root.right?.parent = root
  45.       }
  46.       else if value <= root.value {
  47.         recursiveInsert(root: root.left)
  48.       }
  49.       else {
  50.         recursiveInsert(root: root.right)
  51.       }
  52.      
  53.       if let left = root.left {
  54.         root.leftCount = left.leftCount + left.rightCount + 1
  55.       }
  56.      
  57.       if let right = root.right {
  58.         root.rightCount = right.leftCount + right.rightCount + 1
  59.       }
  60.     }
  61.    
  62.     recursiveInsert(root: tempRoot)
  63.   }
  64.  
  65.   public func print() {
  66.     func dfs(root: BinarySearchTreeNode?) {
  67.       guard let root = root else {
  68.         return
  69.       }
  70.      
  71.       dfs(root: root.left)
  72.       Swift.print(root)
  73.       dfs(root: root.right)
  74.     }
  75.    
  76.     dfs(root: root)
  77.   }
  78.  
  79.   public func find(value: Int) -> Bool {
  80.     return findNode(value: value) == nil ? false : true
  81.   }
  82.  
  83.   public func delete(value: Int) {
  84.     guard let nodeToDelete = findNode(value: value) else {
  85.       return
  86.     }
  87.    
  88.     if nodeToDelete.left == nil {
  89.       transplant(node: nodeToDelete.right, over: nodeToDelete)
  90.     }
  91.     else if (nodeToDelete.right == nil) {
  92.       transplant(node: nodeToDelete.left, over: nodeToDelete)
  93.     }
  94.     else {
  95.       guard let successorNode = treeMinimum(node: nodeToDelete.right!) else {
  96.         fatalError()
  97.       }
  98.      
  99.       if let successorParent = successorNode.parent, successorParent !== nodeToDelete {
  100.         transplant(node: successorNode.right, over: successorNode)
  101.         successorNode.right = nodeToDelete.right
  102.         successorNode.right?.parent = successorNode
  103.       }
  104.       transplant(node: successorNode, over: nodeToDelete)
  105.       successorNode.left = nodeToDelete.left
  106.       successorNode.left?.parent = successorNode
  107.     }
  108.    
  109.     updateChildrenCount(for: root)
  110.   }
  111.  
  112.   public func getRandomNode() -> Int? {
  113.     guard let root = root else {
  114.       return nil
  115.     }
  116.    
  117.     return getRandomNode(from: root)
  118.   }
  119.  
  120.   private func getRandomNode(from root: BinarySearchTreeNode?) -> Int? {
  121.     guard let root = root else {
  122.       return nil
  123.     }
  124.    
  125.     let totalCount = root.leftCount + root.rightCount
  126.     guard totalCount != 0 else {
  127.       return root.value
  128.     }
  129.    
  130.     let random = Int.random(in: 0..<totalCount)
  131.     if random < root.leftCount {
  132.       return getRandomNode(from: root.left)
  133.     }
  134.     else if random == root.leftCount {
  135.       return root.value
  136.     }
  137.     else {
  138.       return getRandomNode(from: root.right)
  139.     }
  140.   }
  141.  
  142.   private func findNode(value: Int) -> BinarySearchTreeNode? {
  143.     guard let root = root else {
  144.       return nil
  145.     }
  146.    
  147.     var q = [BinarySearchTreeNode]()
  148.     q.append(root)
  149.    
  150.     while !q.isEmpty {
  151.       let first = q.remove(at: 0)
  152.       if first.value == value {
  153.         return first
  154.       }
  155.      
  156.       if let left = first.left {
  157.         q.append(left)
  158.       }
  159.      
  160.       if let right = first.right {
  161.         q.append(right)
  162.       }
  163.     }
  164.     return nil
  165.   }
  166.  
  167.   private func treeMinimum(node: BinarySearchTreeNode) -> BinarySearchTreeNode? {
  168.     var temp = node
  169.     while temp.left != nil {
  170.       temp = temp.left!
  171.     }
  172.     return temp
  173.   }
  174.  
  175.   private func transplant(node: BinarySearchTreeNode?, over nodeToDelete: BinarySearchTreeNode) {
  176.     if nodeToDelete.parent == nil {
  177.       self.root = node
  178.     }
  179.     else if nodeToDelete === nodeToDelete.parent?.left {
  180.       nodeToDelete.parent?.left = node
  181.     }
  182.     else {
  183.       nodeToDelete.parent?.right = node
  184.     }
  185.    
  186.     if node != nil {
  187.       node?.parent = nodeToDelete.parent
  188.     }
  189.   }
  190.  
  191.   private func updateChildrenCount(for root: BinarySearchTreeNode?) {
  192.     guard let root = root else {
  193.       return
  194.     }
  195.    
  196.     if root.left == nil && root.right == nil {
  197.       return
  198.     }
  199.    
  200.     updateChildrenCount(for: root.left)
  201.     updateChildrenCount(for: root.right)
  202.    
  203.     if let left = root.left {
  204.       root.leftCount = left.leftCount + left.rightCount + 1
  205.     }
  206.    
  207.     if let right = root.right {
  208.       root.rightCount = right.leftCount + right.rightCount + 1
  209.     }
  210.   }
  211. }
  212.  
  213. let tree = BinarySearchTree(rootValue: 5)
  214. tree.insert(value: 3)
  215. tree.insert(value: 2)
  216. tree.insert(value: 1)
  217. tree.insert(value: 4)
  218. tree.insert(value: 6)
  219. tree.insert(value: 7)
  220. //tree.print()
  221. //tree.find(value: 3)
  222. //tree.find(value: 0)
  223. //tree.delete(value: 3)
  224. //tree.print()
  225. tree.getRandomNode()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top