https://github.com/raywenderlich/swift-algorithm-club/tree/master/Binary%20Search%20Tree
Deleting nodes
Removing nodes is easy. After removing a node, we replace the node with either its biggest child on the left or its smallest child on the right. That way the tree is still sorted after the removal. In the following example, 10 is removed and replaced with either 9 (Figure 2) or 11 (Figure 3).
Binary Search tree implementation in Swift
import UIKit
var str = "Hello, playground"
//Question : What is binary search tree
/*Binary Search Tree is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.*/
//Question : What is binary search tree
/*Binary Search Tree is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.*/
//help link :https://www.journaldev.com/21454/swift-binary-search-tree
class Node<T> {
var data:T
var leftNode:Node? = nil
var rightNode:Node? = nil
init(data:T, leftNode:Node?, rightNode:Node?) {
self.data = data
self.leftNode = leftNode
self.rightNode = rightNode
}
}
class BST<T: Comparable & CustomStringConvertible>{
var rootnode:Node<T>?
func addNode(_ value:T){
let node = Node(data: value, leftNode: nil, rightNode: nil)
if let rootNode = self.rootnode{
self.insert(rootNode, newNode:node)
}else{
self.rootnode = node
}
}
func insert(_ rootNode:Node<T>, newNode:Node<T>){
if(rootNode.data > newNode.data){
if let leftNode = rootNode.leftNode{
self.insert(leftNode, newNode: newNode)
}else{
rootNode.leftNode = newNode
}
}else{
if let rightNode = rootNode.rightNode{
self.insert(rightNode, newNode: newNode)
}else{
rootNode.rightNode = newNode
}
}
}
private func inorder(_ node:Node<T>?){
guard let _ = node else{return}
self.inorder(node?.leftNode)
print("\(node!.data)", terminator: " ")
self.inorder(node?.rightNode)
}
func printTree() {
self.inorder(self.rootnode)
}
}
extension BST{
func search(value:T){
self.search(self.rootnode, value)
}
private func search(_ root:Node<T>?, _ element:T){
guard let rootNode = root else {
print("Node is not available:\(element)")
return
}
print("current root node\(rootNode.data)")
if(element > rootNode.data){
self.search(rootNode.rightNode, element)
}else if(element > rootNode.data){
self.search(rootNode.leftNode, element)
}else{
print("NODE VALUE AVAILABLE :\(rootNode.data)")
}
}
func delete(value:T){
rootnode = self.delete(rootnode, value)
}
func delete(_ root:Node<T>?, _ key:T)-> Node<T>?{
// base case
if(root == nil){
return root
}
// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if(key < root!.data){
root?.leftNode = delete(root?.leftNode, key)
// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
}else if(key > root!.data){
root?.rightNode = delete(root?.rightNode, key)
}
// if key is same as root's key, then This is the node
// to be deleted
else{
// node with only one child or no child
if root?.leftNode == nil{
return root?.rightNode
}
else if root?.rightNode == nil{
return root?.leftNode
}
// node with two children: Get the inorder successor (smallest
// in the right subtree)
root?.data = (minValue(root?.rightNode))!
root?.rightNode = delete(root?.rightNode, (root?.data)!)
}
return root
}
public func minValue(_ node: Node<T>?) -> T? {
var tempNode = node
while let next = tempNode?.leftNode {
tempNode = next
}
return tempNode?.data
}
}
let numList:Array<Int> = [8,2,10,9,11,1,7]
var root = BST<Int>()
for number in numList{
root.addNode(number)
}
root.printTree()
//root.search(value: 11)
//root.delete(value: 1)
//root.printTree()
No comments:
Post a Comment