RubyLouvre / algorithmbook

没有经过整理的知识才是徒然浪费时间,伤透脑筋!
109 stars 67 forks source link

替罪羊树 #9

Open RubyLouvre opened 6 years ago

RubyLouvre commented 6 years ago
        class Node {
            constructor(data) {
                this.size = 1
                this.data = data;
                this.left = null;
                this.right = null;
                this.parent = null;
                this.disposed = false;
            }
            update() {
                var leftSize = this.left ? this.left.size : 0
                var rightSize = this.right ? this.right.size : 0
                this.size = leftSize + rightSize + (this.disposed ? 0 : 1)
            }

        };

        class Scapegoat {
            constructor() {
                this.root = null;
                this._size = 0;
            }
            size() {
                return this.root ? this.root.size : 0
            }
            find(data) {
                var node = this.root;
                while (node) {
                    var diff = data - node.data
                    if (diff == 0) {
                        break
                    } else if (diff < 0) {
                        node = node.left;
                    } else {
                        node = node.right;
                    }
                }
                if (node && !node.disposed) {
                    return node
                }
                return null
            }
            insert(data) {
                if (!this.root) {
                    this.root = new Node(data)
                    this._size = 1
                } else {
                    var node = this.root,
                        parent = null,
                        paths = []

                    while (node) {
                        parent = node;
                        paths.push(node)
                        var diff = data - node.data
                        if (diff == 0) {
                            return
                        } else if (diff < 0) {
                            node = node.left
                        } else {
                            node = node.right
                        }
                    }
                    var node = new Node(data)
                    this._size++;
                    node.parent = parent;
                    if (diff < 0) {
                        parent.left = node
                    } else {
                        parent.right = node;
                    }
                    var badNode
                    for (var i = paths.length - 1; i >= 0; i--) {
                        node = paths[i]
                        node.size++;
                        if (!this.isBalance(node)) {
                            badNode = node;
                        }
                    }
                    if (badNode) {
                        this.rebuild(badNode);
                    }
                }
                return true
            }
            inOrder(node, array) { //中序遍历
                if (node) {
                    this.inOrder(node.left, array);
                    if (!node.disposed) {
                        array.push(node) // 构建序列 
                    }
                    this.inOrder(node.right, array);
                    node.left = node.right = null; //清空孩子!!!
                }
            }
            rebuild(node) {
                var parent = node.parent;
                var array = [];
                this.inOrder(node, array)
                var child = this.divide(array, 0, array.length)
                //设置新子树的根的属性
                child.parent = parent;
                if (!parent) {
                    this.root = child;
                } else {
                    if (parent.left == node) {
                        parent.left = child;
                    } else {
                        parent.right = child;
                    }
                }
            }
            divide(array, l, r) {
                if (l >= r) return null;
                var mid = (l + r) >> 1;
                var node = array[mid];
                var child = this.divide(array, l, mid);
                if (child) {
                    child.parent = node;
                    node.left = child;
                }
                child = this.divide(array, mid + 1, r);
                if (child) {
                    child.parent = node;
                    node.right = child;
                }
                node.update() // 自底向上维护,先维护子树 
                return node
            }
            isBalance(node) {
                // 左子树大小 < alpha * 根大小 并且 右子树大小 < alpha * 根大小
                // alpha越小,树越稠密,插入效率低,查询效率高;
                // alpha越大,树越稀疏,插入效率高,查询效率低;
                var alpha = 0.65;
                var size = node.size * alpha
                var leftSize = node.left && node.left.size || 0
                var rightSize = node.right && node.right.size || 0
                return leftSize < size && rightSize < size;
            }
            remove(data) {
                var node = this.find(data);
                if (node && !node.disposed) {
                    this._size--;
                    node.disposed = true;
                    node.size--;
                    var p = node.parent
                    while (p) {
                        p.update()
                        p = p.parent;
                    }
                }
            }
            toString(printNode) {
                printNode = printNode || function (n) {
                    return n.data
                };
                var out = [];
                printRow(this.root, '', true, function (v) {
                    return out.push(v);
                }, printNode);
                return out.join('');
            };
        }

        function printRow(root, prefix, isTail, out, printNode) {
            if (root) {
                out(("" + prefix + (isTail ? '└── ' : '├── ') + (printNode(root)) + "\n"));
                var indent = prefix + (isTail ? '    ' : '│   ');
                if (root.left) {
                    printRow(root.left, indent, false, out, printNode);
                }
                if (root.right) {
                    printRow(root.right, indent, true, out, printNode);
                }
            }
        }
        var tree = new Scapegoat(); // 30, 20, 60, 55, 54, 53, 52, 51, 56
        [10, 50, 40, 30, 20, 60, 55, 54, 53, 52, 51, 56].forEach(function (el, i) {
            tree.insert(el)
            console.log(tree + "")
        })
        console.log("delete...")
        tree.remove(60)
        console.log(tree + "")

        console.log(tree)

image

RubyLouvre commented 6 years ago

学习资料 https://zhuanlan.zhihu.com/p/21263304

RubyLouvre commented 5 years ago
          class Node {
                constructor(data) {
                    this.size = 1;
                    this.data = data;
                    this.left = null;
                    this.right = null;
                    this.parent = null;
                    this.disposed = false;
                }
                maintain() {
                  this.size = this.disposed ? 0 : 1
                  if(this.left){
                    this.size += this.left.size
                  }
                  if(this.right){
                    this.size += this.right.size
                  }
                }
            }

            class Scapegoat {
                constructor() {
                    this.root = null;
                }

                find(data) {
                    var node = this.root;
                    while (node) {
                        var diff = data - node.data;
                        if (diff == 0) {
                            break;
                        } else if (diff < 0) {
                            node = node.left;
                        } else {
                            node = node.right;
                        }
                    }
                    if (node && !node.disposed) {
                        return node;
                    }
                    return null;
                }
                insert(data) {
                    if (!this.root) {
                        this.root = new Node(data);
                        this._size = 1;
                    } else {
                        var node = this.root,
                            parent = null;
                        while (node) {
                            parent = node;
                            var diff = data - node.data;
                            if (diff == 0) {
                                return;
                            } else if (diff < 0) {
                                node = node.left;
                            } else {
                                node = node.right;
                            }
                        }
                        var node = new Node(data);
                        node.parent = parent;
                        if (diff < 0) {
                            parent.left = node;
                        } else {
                            parent.right = node;
                        }
                        var badNode;
                        while (parent) {
                            parent.size++;
                            if (!this.isBalance(parent)) {
                                badNode = parent;
                                break;
                            }
                            parent = parent.parent;
                        }
                        if (badNode) {
                            this.rebuild(badNode);
                        }
                    }
                    return true;
                }

                rebuild(node) {
                    var parent = node.parent;
                    var array = [];
                    function inOrder(node) {
                        //中序遍历
                        if (node) {
                            inOrder(node.left);
                            if (!node.disposed) {
                                array.push(node); // 构建序列
                            }
                            inOrder(node.right);
                            node.left = node.right = null; //清空孩子!!!
                        }
                    }
                    inOrder(node);
                    var child = this.divide(array, 0, array.length);
                    //设置新子树的根的属性
                    child.parent = parent;
                    if (!parent) {
                        this.root = child;
                    } else {
                        if (parent.left == node) {
                            parent.left = child;
                        } else {
                            parent.right = child;
                        }
                    }
                }
                divide(array, l, r) {
                    if (l >= r) return null;
                    var mid = (l + r) >> 1;
                    var node = array[mid];
                    var child = this.divide(array, l, mid);
                    if (child) {
                        child.parent = node;
                        node.left = child;
                    }
                    child = this.divide(array, mid + 1, r);
                    if (child) {
                        child.parent = node;
                        node.right = child;
                    }
                    node.maintain(); // 自底向上维护,先维护子树
                    return node;
                }
                isBalance(node) {
                    // 左子树大小 < alpha * 根大小 并且 右子树大小 < alpha * 根大小
                    // alpha越小,树越稠密,插入效率低,查询效率高;
                    // alpha越大,树越稀疏,插入效率高,查询效率低;
                    var alpha = 0.65;
                    var size = node.size * alpha;
                    var leftSize = (node.left && node.left.size) || 0;
                    var rightSize = (node.right && node.right.size) || 0;
                    return leftSize < size && rightSize < size;
                }
                remove(data) {
                    var node = this.find(data);
                    if (node && !node.disposed) {
                        node.disposed = true;
                        node.size--;
                        var p = node.parent;
                        while (p) {
                            p.maintain();
                            p = p.parent;
                        }
                    }
                }
                toString(printNode) {
                    printNode =
                        printNode ||
                        function(n) {
                            return n.data;
                        };
                    var out = [];
                    printRow(
                        this.root,
                        "",
                        true,
                        function(v) {
                            return out.push(v);
                        },
                        printNode
                    );
                    return out.join("");
                }
            }

            function printRow(root, prefix, isTail, out, printNode) {
                if (root) {
                    out(
                        "" +
                            prefix +
                            (isTail ? "└── " : "├── ") +
                            printNode(root) +
                            "\n"
                    );
                    var indent = prefix + (isTail ? "    " : "│   ");
                    if (root.left) {
                        printRow(root.left, indent, false, out, printNode);
                    }
                    if (root.right) {
                        printRow(root.right, indent, true, out, printNode);
                    }
                }
            }
            var tree = new Scapegoat(); // 30, 20, 60, 55, 54, 53, 52, 51, 56
            [10, 50, 40, 30, 20, 60, 55, 54, 53, 52, 51, 56].forEach(function(
                el,
                i
            ) {
                tree.insert(el);
                console.log(tree + "");
            });
            console.log("delete...");
            tree.remove(60);
            console.log(tree + "");

            console.log(tree);