In the last article Swift implementation -tree (Tree), BaniryTree(binary Tree), BinarySearchTree(BinarySearchTree), we through the value type (that is, enumeration type), to achieve the basic structure of the BinarySearchTree, and search, insert and other functions, now we through the class method, To create a more perfect binary search tree, this is also for the red black tree and other structures to sit down, because the last article has a basic introduction to binary search tree, here is not to say, there is not clear, you can go to the last article to see, the code directly below

Basic implementation

class ClassBinarySearchTree<T: Comparable> {
    private(set) var value: T
    private(set) var parent: ClassBinarySearchTree?
    private(set) var leftChild: ClassBinarySearchTree?
    private(set) var rightChild: ClassBinarySearchTree?
    
    /// Whether the node is the root node
    var isRoot: Bool {
        return parent == nil
    }
    /// whether it is a leaf node
    var isLeaf: Bool {
        return leftChild == nil && rightChild == nil
    }
    var isLeftChild: Bool {
        returnparent? .leftChild ===self
    }
    var isRightChild: Bool {
        returnparent? .rightChild ===self
    }
    
    var hasLeftChild: Bool {
        returnleftChild ! =nil
    }
    
    var hasRightChild: Bool {
        returnrightChild ! =nil
    }
    
    var hasAnyChild: Bool {
        return hasLeftChild || hasRightChild
    }
    
    var hasBothChildren: Bool {
        return hasLeftChild && hasRightChild
    }
    
    var count: Int {
        return(leftChild? .count ?? 0) + 1+ (rightChild? .count ?? 0)}init(_ value: T) {
        self.value = value
    }
}
Copy the code

Above is an implementation of a node in a tree that has references to its parent, left child, and right child. It also has some ancillary functions

insert

func insert(_ node: ClassBinarySearchTree) {
        / / 1
        if node.value > self.value {
            / / 2
            guard let right = rightChild else {
                self.rightChild = node
                node.parent = self
                return
            }
            right.insert(node)
        }else {
            guard let left = leftChild else {
                self.leftChild = node
                node.parent = self
                return
            }
            left.insert(node)
        }
    }
Copy the code
  • 1. If the value inserted is greater than the current value, the value should be inserted into the right subtree
  • 2. If there is no right subtree, create a number with the inserted value and make it the same as the left side of the right subtree

Binary search tree inserts are much easier to insert than binary search trees with enumeration types. See ### search for details in the previous article

func search(_ value: T) -> ClassBinarySearchTree? {
        if value == self.value {
            return self
        }else if value > self.value {
            return self.rightChild? .search(value) }else {
            return self.leftChild? .search(value) } }Copy the code

Search also by recursive references, in dealing with a tree structure, a lot of operation can be realized by recursion, and more simple and convenient, later to write a summary about recursive application, interested can also look at his book illustration algorithm, chapters of “divide and conquer” feeling explanation is very clear and interesting # # # to delete Because after remove nodes, The binary search tree is still maintained, so the operation is somewhat complex, which is divided into the following cases: Assumed to be removed is T in the tree node z 1, if z is a leaf node, directly deleted, corresponding children refers to the parent node is nil 2, if z is only one child, then remove the z, with the child instead of z z, namely to develop children’s parent, and so on. 3, z z has two subtrees around, you will need to find the subsequent z node, The successor must be in the right subtree, and the node with no left children is the smallest node in the right subtree, assuming that this node is y, we need to replace y with the subtree of y, and then replace Z with y

Simple summary is that if there is a right subtree, find the smallest node from right subtree y, instead of to the deleted node z, delete y, at the same time from the right subtree of y, find the smallest node y1 to replace y, cycling In the process, if there is no right subtree, only left subtree, then from the left subtree is to find the largest node y, cycling

Right to right, not right to left

extension ClassBinarySearchTree {
    //1
    private func reconnectParentToNode(node: ClassBinarySearchTree?) {
        if let parent = parent {
            if isLeftChild {
                parent.leftChild = node
            } else{ parent.rightChild = node } } node? .parent = parent } //2 private func minNode() -> ClassBinarySearchTree { var node = selfwhile let left = node.leftChild {
            node = left
        }
        return node
    }
    //3
    private func maxNode() -> ClassBinarySearchTree {
        var node = self
        while let right = node.rightChild {
            node = right
        }
        return node
    }
}
//4
extension ClassBinarySearchTree: CustomStringConvertible {
    var description: String {
        let value = self.value
        letleft: String = self.leftChild? .description ??"Empty"
        letright: String = self.rightChild? .description ??"Empty"
        
        return "\(value) " + "[\(value) left child \(left)]"  + "[\(value) child \(right)]"}}Copy the code

Here are some of the auxiliary methods

  • 1 This method is to delete itself and replace itself with a new node
  • 2 Find the smallest child node
  • 3 Search for the largest child node
  • 4 Convenient debugging
var replaceMent: ClassBinarySearchTree?
        if let right = rightChild {
            replaceMent = right.minNode()
        }else if let left = leftChild {
            replaceMent = left.maxNode()
        }else {
            replaceMent = nil
        }
        
        let _= replaceMent? .remove() replaceMent? .leftChild = leftChild replaceMent? .rightChild = rightChild rightChild? .parent = replaceMent leftChild? .parent = replaceMent reconnectParentToNode(node: replaceMent) parent =nil
        leftChild = nil
        rightChild = nil
        return replaceMent
Copy the code
  • Get the precursor, the successor
func predecessor(a) -> ClassBinarySearchTree? {
        if let left = leftChild {
            return left.maxNode()
        }else {
            var node = self
            while let parent = node.parent {
                if parent.value < node.value {
                    return parent
                }
                node = parent
            }
        }
        return nil
    }
    
    func successor(a) -> ClassBinarySearchTree? {
        if let right = rightChild {
            return right.minNode()
        }else {
            var node = self
            while let parent = node.parent {
                if parent.value > node.value {
                    return parent
                }
                node = parent
            }
        }
        return nil
    }
Copy the code

Take middle-order traversal as an example, the precursor of a node may not be the left child of the node, and the successor may not be the right child of the node. If the node has a left subtree, then the precursor must be the largest node in the left subtree; if there is no left subtree, then the precursor must be the smallest node in the parent node. The same goes for the next.