データ構造とアルゴリズムJavaScript記述(8):二叉ルックアップツリー(BST)

ツリーを検索
二叉ルックアップツリー(BST):特殊な二叉ツリーで、比較的小さい値は左ノードに保存され、大きな値は右ノードに保存されます.
実装:

class Node {

    constructor(data) {
        // Node                
        this.data = data
        this.left = null
        this.right = null
    }

    toString() {
        return this.data.toString()
    }
}

class BST {

    constructor() {
        this.root = null
    }

    //         
    insert(...datalist) {
        for (let data of datalist) {
            const node = new Node(data)
            if (this.root === null) {
                this.root = node
            } else {
                let current = this.root
                let parent
                while(true) {
                    parent = current
                    if (data < current.data) {
                        current = current.left
                        if (current === null) {
                            parent.left = node
                            break
                        }
                    } else {
                        current = current.right
                        if (current === null) {
                            parent.right = node
                            break
                        }
                    }
                }
            }
        }
    }

    //     ：    ->     ->    
    preOrder() {
        const order = node => {
            if (node !== null) {
                console.log(`${node.data} `)
                order(node.left)
                order(node.right)
            }
        }
        order(this.root)
    }

    //     ：    ->     ->    
    inOrder() {
        const order = node => {
            if (node !== null) {
                order(node.left)
                console.log(`${node.data} `)
                order(node.right)
            }
        }
        order(this.root)
    }

    //     ：    ->     ->    
    postOrder() {
        const order = node => {
            if (node !== null) {
                order(node.left)
                order(node.right)
                console.log(`${node.data} `)
            }
        }
        order(this.root)
    }

    //      
    findMin() {
        let current = this.root
        while(current.left !== null) {
            current = current.left
        }
        return current.data
    }

    //      
    findMax() {
        let current = this.root
        while(current.right !== null) {
            current = current.right
        }
        return current.data
    }

    //      
    find(data) {
        let current = this.root
        while(current !== null) {
            if (data === current.data) {
                return current
            } else if (data < current.data) {
                current = current.left
            } else if (data > current.data) {
                current = current.right
            }
        }
    }

    //      
    find(data) {
        let current = this.root
        while(current !== null) {
            if (data === current.data) {
                return current
            } else if (data < current.data) {
                current = current.left
            } else if (data > current.data) {
                current = current.right
            }
        }
        return null
    }

    //      
    remove(data) {
        const findMin = node => {
            let current = node
            while(current.left !== null) {
                current = current.left
            }
            return current
        }
        const removeNode = (node, data) => {
            if (node === null) {
                return null
            }
            if (data === node.data) {
                //         
                if (node.left === null &&
                        node.right === null) {
                    return null
                }
                //          
                if (node.left === null) {
                    return node.right
                }
                //          
                if (node.right === null) {
                    return node.left
                }
                //          
        //           ，            
                const tempNode = findMin(node.right)
                //                 
                node.data = tempNode.data
                //          
                node.right = removeNode(node.right, tempNode.data)
                return node
            } else if (data < node.data) {
                //                
                node.left = removeNode(node.left, data)
                return node
            } else {
                //                
                node.right = removeNode(node.right, data)
                return node
            }
        }
        this.root = removeNode(this.root, data)
    }

    //   BST      
    count() {
        let arr = []
        const order = node => {
            if (node !== null) {
                order(node.left, arr)
                order(node.right, arr)
                arr.push(node.data)
            }
        }
        order(this.root)
        return arr.length
    }

    //   BST     
    edgesCount() {
        let count = 0
        const edgesCount = node => {
            if (node.left !== null && node.right !== null) {
                count++
                edgesCount(node.left)
                count++
                edgesCount(node.right)
            } else if (node.left !== null) {
                count++
                edgesCount(node.left)
            } else if (node.right !== null) {
                count++
                edgesCount(node.right)
            }
        }
        edgesCount(this.root)
        return count
    }
}

// test
const bst = new BST()
bst.insert(23,16,99,30,18,3,120,45)
console.log(bst.count())    // 8
bst.preOrder() // 23 16 3 18 99 30 45 120
bst.inOrder() // 3 16 18 23 30 45 99 120
bst.postOrder() // 3 18 16 45 30 120 99 23
bst.remove(99)
console.log(bst.count())    // 7
console.log(bst.findMin())  // 3
console.log(bst.findMax())  // 120
console.log(bst.find(30))       // Node {data: 30, left: null, right: Node}
console.log(bst.edgesCount())   // 6