Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
data-footstone
Advanced tools
data-footstone - npm Package Compare versions
Comparing version 0.1.8 to 0.1.11
@@ -23,6 +23,3 @@ 'use strict'; | ||
| exports.loseloseHashFn = hashMap.loseloseHashFn; | ||
| exports.AVLTree = tree.AVLTree; | ||
| exports.BaseTree = tree.BaseTree; | ||
| exports.BinarySearchTree = tree.BinarySearchTree; | ||
| exports.RedBackTree = tree.RedBackTree; | ||
| exports.order = order; | ||
@@ -29,0 +26,0 @@ exports.Fifo = store.Fifo; |
| 'use strict'; | ||
| class BaseTree { | ||
| // class BaseTree<T> implements BT<T> { | ||
| // // root: BTN<T> | null | ||
| // // constructor() { | ||
| // // this.root = null | ||
| // // } | ||
| // // createNode(v: T) { | ||
| // // return { | ||
| // // value: v, | ||
| // // left: null, | ||
| // // right: null, | ||
| // // } | ||
| // // } | ||
| // // 先父节点，再左节点，再右节点 | ||
| // _preOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // cb(node.value) | ||
| // this._preOrderTraverse(cb, node.left) | ||
| // this._preOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // // 整体从左到右依次操作 | ||
| // _inOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // this._inOrderTraverse(cb, node.left) | ||
| // cb(node.value) | ||
| // this._inOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // // 先左节点，再右节点，再父节点 | ||
| // _postOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // this._postOrderTraverse(cb, node.left) | ||
| // this._postOrderTraverse(cb, node.right) | ||
| // cb(node.value) | ||
| // } | ||
| // } | ||
| // // _findMinNode(node: BTN<T> | null) { | ||
| // // let cur = node | ||
| // // while (cur && cur.left) { | ||
| // // cur = cur.left | ||
| // // } | ||
| // // return cur | ||
| // // } | ||
| // // 不应该在这里搞这样的逻辑 | ||
| // _remove(node: BTN<T>, value: T) { | ||
| // if (!node) { | ||
| // return null | ||
| // } | ||
| // if (value < node.value) { | ||
| // node.left = this._remove(node.left, value) | ||
| // return node | ||
| // } else if (value > node.value) { | ||
| // node.right = this._remove(node.right, value) | ||
| // return node | ||
| // } else { | ||
| // // 有0个节点 | ||
| // if (!node.left && !node.right) { | ||
| // node = null | ||
| // return node | ||
| // } | ||
| // // 有1个节点 | ||
| // if (!node.left) { | ||
| // node = node.right | ||
| // return node | ||
| // } else if (!node.right) { | ||
| // node = node.left | ||
| // return node | ||
| // } | ||
| // // 有2个节点 | ||
| // let t = this._findMinNode(node.right) | ||
| // node.value = t.value | ||
| // node.right = this._remove(node.right, t.value) | ||
| // return node | ||
| // } | ||
| // } | ||
| // 返回节点的高度。 | ||
| // heightNode(node: BTN<T>): N { | ||
| // return node | ||
| // ? Math.max(this.heightNode(node.left), this.heightNode(node.right)) + 1 | ||
| // : -1 | ||
| // } | ||
| // // 待测试 | ||
| // shortPathNodeLength(node = null, deep = 0) { | ||
| // if (!node) { | ||
| // return deep | ||
| // } else { | ||
| // let queue = new Queue<BTN<T>>() | ||
| // queue.enqueue(node) | ||
| // let len = queue.size() | ||
| // while (len) { | ||
| // let i = 0 | ||
| // while (i < len) { | ||
| // let n = queue.dequeue() | ||
| // if (!n.left && !n.right) { | ||
| // return deep | ||
| // } else { | ||
| // n.left && queue.enqueue(n.left) | ||
| // n.right && queue.enqueue(n.right) | ||
| // } | ||
| // i++ | ||
| // } | ||
| // deep++ | ||
| // len = queue.size() | ||
| // } | ||
| // } | ||
| // } | ||
| // } | ||
| class BinarySearchTree { | ||
| constructor() { | ||
@@ -14,77 +121,22 @@ this.root = null; | ||
| } | ||
| // 先父节点，再左节点，再右节点 | ||
| _preOrderTraverse(cb, node) { | ||
| if (node) { | ||
| cb(node.value); | ||
| this._preOrderTraverse(cb, node.left); | ||
| this._preOrderTraverse(cb, node.right); | ||
| _insertNode(node, newNode) { | ||
| if (newNode.value < node.value) { | ||
| // if (!node.left) { | ||
| // node.left = newNode | ||
| // } else { | ||
| // this._insertNode(node.left, newNode) | ||
| // } | ||
| node.left ? this._insertNode(node.left, newNode) : (node.left = newNode); | ||
| } | ||
| } | ||
| // 整体从左到右依次操作 | ||
| _inOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._inOrderTraverse(cb, node.left); | ||
| cb(node.value); | ||
| this._inOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| // 先左节点，再右节点，再父节点 | ||
| _postOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._postOrderTraverse(cb, node.left); | ||
| this._postOrderTraverse(cb, node.right); | ||
| cb(node.value); | ||
| } | ||
| } | ||
| _findMinNode(node) { | ||
| let cur = node; | ||
| while (cur && cur.left) { | ||
| cur = cur.left; | ||
| } | ||
| return cur; | ||
| } | ||
| _remove(node, value) { | ||
| if (!node) { | ||
| return null; | ||
| } | ||
| if (value < node.value) { | ||
| node.left = this._remove(node.left, value); | ||
| return node; | ||
| } | ||
| else if (value > node.value) { | ||
| node.right = this._remove(node.right, value); | ||
| return node; | ||
| } | ||
| else { | ||
| // 有0个节点 | ||
| if (!node.left && !node.right) { | ||
| node = null; | ||
| return node; | ||
| } | ||
| // 有1个节点 | ||
| if (!node.left) { | ||
| node = node.right; | ||
| return node; | ||
| } | ||
| else if (!node.right) { | ||
| node = node.left; | ||
| return node; | ||
| } | ||
| // 有2个节点 | ||
| let t = this._findMinNode(node.right); | ||
| node.value = t.value; | ||
| node.right = this._remove(node.right, t.value); | ||
| return node; | ||
| node.right | ||
| ? this._insertNode(node.right, newNode) | ||
| : (node.right = newNode); | ||
| // if (!node.right) { | ||
| // node.right = newNode | ||
| // } else { | ||
| // this._insertNode(node.right, newNode) | ||
| // } | ||
| } | ||
| } | ||
| heightNode(node) { | ||
| return node | ||
| ? Math.max(this.heightNode(node.left), this.heightNode(node.right)) + 1 | ||
| : -1; | ||
| } | ||
| } | ||
| class BinarySearchTree extends BaseTree { | ||
| constructor() { | ||
| super(); | ||
| } | ||
| insert(v) { | ||
@@ -99,20 +151,2 @@ let node = this.createNode(v); | ||
| } | ||
| _insertNode(node, newNode) { | ||
| if (newNode.value < node.value) { | ||
| if (!node.left) { | ||
| node.left = newNode; | ||
| } | ||
| else { | ||
| this._insertNode(node.left, newNode); | ||
| } | ||
| } | ||
| else { | ||
| if (!node.right) { | ||
| node.right = newNode; | ||
| } | ||
| else { | ||
| this._insertNode(node.right, newNode); | ||
| } | ||
| } | ||
| } | ||
| // 是否存在 | ||
@@ -136,6 +170,27 @@ search(v) { | ||
| } | ||
| _preOrderTraverse(cb, node) { | ||
| if (node) { | ||
| cb(node.value); | ||
| this._preOrderTraverse(cb, node.left); | ||
| this._preOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _inOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._inOrderTraverse(cb, node.left); | ||
| cb(node.value); | ||
| this._inOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _postOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._postOrderTraverse(cb, node.left); | ||
| this._postOrderTraverse(cb, node.right); | ||
| cb(node.value); | ||
| } | ||
| } | ||
| traverse(cb, order = 'inOrder') { | ||
| switch (order) { | ||
| case 'preOrder': | ||
| this._inOrderTraverse(cb, this.root); | ||
| this._preOrderTraverse(cb, this.root); | ||
| break; | ||
@@ -152,3 +207,6 @@ case 'inOrder': | ||
| let cur = this.root; | ||
| while (cur && cur.left) { | ||
| if (!cur) { | ||
| return undefined; | ||
| } | ||
| while (cur.left) { | ||
| cur = cur.left; | ||
@@ -160,3 +218,6 @@ } | ||
| let cur = this.root; | ||
| while (cur && cur.right) { | ||
| if (!cur) { | ||
| return undefined; | ||
| } | ||
| while (cur.right) { | ||
| cur = cur.right; | ||
@@ -166,82 +227,62 @@ } | ||
| } | ||
| remove(v) { | ||
| this.root = this._remove(this.root, v); | ||
| findMinNode(node) { | ||
| if (!node) { | ||
| return null; | ||
| } | ||
| let cur = node; | ||
| while (cur.left) { | ||
| cur = cur.left; | ||
| } | ||
| return cur; | ||
| } | ||
| } | ||
| class AVLTree extends BinarySearchTree { | ||
| constructor() { | ||
| super(); | ||
| findMaxNode(node) { | ||
| if (!node) { | ||
| return null; | ||
| } | ||
| let cur = node; | ||
| while (cur.right) { | ||
| cur = cur.right; | ||
| } | ||
| return cur; | ||
| } | ||
| insert(v) { | ||
| this._insertNode(this.root, this.createNode(v)); | ||
| } | ||
| _insertNode(node, newNode) { | ||
| _remove(node, value) { | ||
| if (!node) { | ||
| node = newNode; | ||
| return null; | ||
| } | ||
| else if (newNode.value < node.value) { | ||
| node.left = this._insertNode(node.left, newNode); | ||
| if (node.left) { | ||
| // 是否需要平衡 | ||
| if (this.heightNode(node.left) - this.heightNode(node.right) > 1) { | ||
| if (newNode.value < node.left.value) { | ||
| node = this._rotationLL(node); | ||
| } | ||
| else { | ||
| node = this._rotationLR(node); | ||
| } | ||
| } | ||
| } | ||
| if (value < node.value) { | ||
| node.left = this._remove(node.left, value); | ||
| return node; | ||
| } | ||
| else if (newNode.value > node.value) { | ||
| node.right = this._insertNode(node.right, newNode); | ||
| if (node.right) { | ||
| // 是否需要平衡 | ||
| if (this.heightNode(node.right) - this.heightNode(node.left) > 1) { | ||
| if (newNode.value > node.right.value) { | ||
| node = this._rotationRR(node); | ||
| } | ||
| else { | ||
| node = this._rotationRL(node); | ||
| } | ||
| } | ||
| else if (value > node.value) { | ||
| node.right = this._remove(node.right, value); | ||
| return node; | ||
| } | ||
| else { | ||
| // 有0个节点 | ||
| if (!node.left && !node.right) { | ||
| node = null; | ||
| return node; | ||
| } | ||
| // 有1个节点 | ||
| if (!node.left) { | ||
| node = node.right; | ||
| return node; | ||
| } | ||
| else if (!node.right) { | ||
| node = node.left; | ||
| return node; | ||
| } | ||
| // 有2个节点 | ||
| let t = this.findMinNode(node.right); | ||
| node.value = t.value; | ||
| node.right = this._remove(node.right, t.value); | ||
| return node; | ||
| } | ||
| return node; | ||
| } | ||
| // 向左的单旋转 | ||
| _rotationRR(node) { | ||
| let t = node.right; | ||
| node.right = t.left; | ||
| t.left = node; | ||
| return t; | ||
| remove(v) { | ||
| this.root = this._remove(this.root, v); | ||
| } | ||
| // 向右的单旋转 | ||
| _rotationLL(node) { | ||
| let t = node.left; | ||
| node.left = t.right; | ||
| t.right = node; | ||
| return t; | ||
| } | ||
| // 向右的双旋转 | ||
| _rotationLR(node) { | ||
| node.left = this._rotationRR(node.left); | ||
| return this._rotationLL(node); | ||
| } | ||
| // 向左的双旋转 | ||
| _rotationRL(node) { | ||
| node.right = this._rotationLL(node.right); | ||
| return this._rotationRR(node); | ||
| } | ||
| } | ||
| class RedBackTree extends BinarySearchTree { | ||
| constructor() { | ||
| super(); | ||
| } | ||
| } | ||
| exports.AVLTree = AVLTree; | ||
| exports.BaseTree = BaseTree; | ||
| exports.BinarySearchTree = BinarySearchTree; | ||
| exports.RedBackTree = RedBackTree; | ||
| //# sourceMappingURL=tree.js.map |
@@ -5,3 +5,3 @@ export { Stack } from './stack.js'; | ||
| export { HashMap, djb2HashFn, loseloseHashFn } from './hashMap.js'; | ||
| export { AVLTree, BaseTree, BinarySearchTree, RedBackTree } from './tree.js'; | ||
| export { BinarySearchTree } from './tree.js'; | ||
| import * as order from './order.js'; | ||
@@ -8,0 +8,0 @@ export { order }; |
@@ -1,2 +0,109 @@ | ||
| class BaseTree { | ||
| // class BaseTree<T> implements BT<T> { | ||
| // // root: BTN<T> | null | ||
| // // constructor() { | ||
| // // this.root = null | ||
| // // } | ||
| // // createNode(v: T) { | ||
| // // return { | ||
| // // value: v, | ||
| // // left: null, | ||
| // // right: null, | ||
| // // } | ||
| // // } | ||
| // // 先父节点，再左节点，再右节点 | ||
| // _preOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // cb(node.value) | ||
| // this._preOrderTraverse(cb, node.left) | ||
| // this._preOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // // 整体从左到右依次操作 | ||
| // _inOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // this._inOrderTraverse(cb, node.left) | ||
| // cb(node.value) | ||
| // this._inOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // // 先左节点，再右节点，再父节点 | ||
| // _postOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // this._postOrderTraverse(cb, node.left) | ||
| // this._postOrderTraverse(cb, node.right) | ||
| // cb(node.value) | ||
| // } | ||
| // } | ||
| // // _findMinNode(node: BTN<T> | null) { | ||
| // // let cur = node | ||
| // // while (cur && cur.left) { | ||
| // // cur = cur.left | ||
| // // } | ||
| // // return cur | ||
| // // } | ||
| // // 不应该在这里搞这样的逻辑 | ||
| // _remove(node: BTN<T>, value: T) { | ||
| // if (!node) { | ||
| // return null | ||
| // } | ||
| // if (value < node.value) { | ||
| // node.left = this._remove(node.left, value) | ||
| // return node | ||
| // } else if (value > node.value) { | ||
| // node.right = this._remove(node.right, value) | ||
| // return node | ||
| // } else { | ||
| // // 有0个节点 | ||
| // if (!node.left && !node.right) { | ||
| // node = null | ||
| // return node | ||
| // } | ||
| // // 有1个节点 | ||
| // if (!node.left) { | ||
| // node = node.right | ||
| // return node | ||
| // } else if (!node.right) { | ||
| // node = node.left | ||
| // return node | ||
| // } | ||
| // // 有2个节点 | ||
| // let t = this._findMinNode(node.right) | ||
| // node.value = t.value | ||
| // node.right = this._remove(node.right, t.value) | ||
| // return node | ||
| // } | ||
| // } | ||
| // 返回节点的高度。 | ||
| // heightNode(node: BTN<T>): N { | ||
| // return node | ||
| // ? Math.max(this.heightNode(node.left), this.heightNode(node.right)) + 1 | ||
| // : -1 | ||
| // } | ||
| // // 待测试 | ||
| // shortPathNodeLength(node = null, deep = 0) { | ||
| // if (!node) { | ||
| // return deep | ||
| // } else { | ||
| // let queue = new Queue<BTN<T>>() | ||
| // queue.enqueue(node) | ||
| // let len = queue.size() | ||
| // while (len) { | ||
| // let i = 0 | ||
| // while (i < len) { | ||
| // let n = queue.dequeue() | ||
| // if (!n.left && !n.right) { | ||
| // return deep | ||
| // } else { | ||
| // n.left && queue.enqueue(n.left) | ||
| // n.right && queue.enqueue(n.right) | ||
| // } | ||
| // i++ | ||
| // } | ||
| // deep++ | ||
| // len = queue.size() | ||
| // } | ||
| // } | ||
| // } | ||
| // } | ||
| class BinarySearchTree { | ||
| constructor() { | ||
@@ -12,77 +119,22 @@ this.root = null; | ||
| } | ||
| // 先父节点，再左节点，再右节点 | ||
| _preOrderTraverse(cb, node) { | ||
| if (node) { | ||
| cb(node.value); | ||
| this._preOrderTraverse(cb, node.left); | ||
| this._preOrderTraverse(cb, node.right); | ||
| _insertNode(node, newNode) { | ||
| if (newNode.value < node.value) { | ||
| // if (!node.left) { | ||
| // node.left = newNode | ||
| // } else { | ||
| // this._insertNode(node.left, newNode) | ||
| // } | ||
| node.left ? this._insertNode(node.left, newNode) : (node.left = newNode); | ||
| } | ||
| } | ||
| // 整体从左到右依次操作 | ||
| _inOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._inOrderTraverse(cb, node.left); | ||
| cb(node.value); | ||
| this._inOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| // 先左节点，再右节点，再父节点 | ||
| _postOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._postOrderTraverse(cb, node.left); | ||
| this._postOrderTraverse(cb, node.right); | ||
| cb(node.value); | ||
| } | ||
| } | ||
| _findMinNode(node) { | ||
| let cur = node; | ||
| while (cur && cur.left) { | ||
| cur = cur.left; | ||
| } | ||
| return cur; | ||
| } | ||
| _remove(node, value) { | ||
| if (!node) { | ||
| return null; | ||
| } | ||
| if (value < node.value) { | ||
| node.left = this._remove(node.left, value); | ||
| return node; | ||
| } | ||
| else if (value > node.value) { | ||
| node.right = this._remove(node.right, value); | ||
| return node; | ||
| } | ||
| else { | ||
| // 有0个节点 | ||
| if (!node.left && !node.right) { | ||
| node = null; | ||
| return node; | ||
| } | ||
| // 有1个节点 | ||
| if (!node.left) { | ||
| node = node.right; | ||
| return node; | ||
| } | ||
| else if (!node.right) { | ||
| node = node.left; | ||
| return node; | ||
| } | ||
| // 有2个节点 | ||
| let t = this._findMinNode(node.right); | ||
| node.value = t.value; | ||
| node.right = this._remove(node.right, t.value); | ||
| return node; | ||
| node.right | ||
| ? this._insertNode(node.right, newNode) | ||
| : (node.right = newNode); | ||
| // if (!node.right) { | ||
| // node.right = newNode | ||
| // } else { | ||
| // this._insertNode(node.right, newNode) | ||
| // } | ||
| } | ||
| } | ||
| heightNode(node) { | ||
| return node | ||
| ? Math.max(this.heightNode(node.left), this.heightNode(node.right)) + 1 | ||
| : -1; | ||
| } | ||
| } | ||
| class BinarySearchTree extends BaseTree { | ||
| constructor() { | ||
| super(); | ||
| } | ||
| insert(v) { | ||
@@ -97,20 +149,2 @@ let node = this.createNode(v); | ||
| } | ||
| _insertNode(node, newNode) { | ||
| if (newNode.value < node.value) { | ||
| if (!node.left) { | ||
| node.left = newNode; | ||
| } | ||
| else { | ||
| this._insertNode(node.left, newNode); | ||
| } | ||
| } | ||
| else { | ||
| if (!node.right) { | ||
| node.right = newNode; | ||
| } | ||
| else { | ||
| this._insertNode(node.right, newNode); | ||
| } | ||
| } | ||
| } | ||
| // 是否存在 | ||
@@ -134,6 +168,27 @@ search(v) { | ||
| } | ||
| _preOrderTraverse(cb, node) { | ||
| if (node) { | ||
| cb(node.value); | ||
| this._preOrderTraverse(cb, node.left); | ||
| this._preOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _inOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._inOrderTraverse(cb, node.left); | ||
| cb(node.value); | ||
| this._inOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _postOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._postOrderTraverse(cb, node.left); | ||
| this._postOrderTraverse(cb, node.right); | ||
| cb(node.value); | ||
| } | ||
| } | ||
| traverse(cb, order = 'inOrder') { | ||
| switch (order) { | ||
| case 'preOrder': | ||
| this._inOrderTraverse(cb, this.root); | ||
| this._preOrderTraverse(cb, this.root); | ||
| break; | ||
@@ -150,3 +205,6 @@ case 'inOrder': | ||
| let cur = this.root; | ||
| while (cur && cur.left) { | ||
| if (!cur) { | ||
| return undefined; | ||
| } | ||
| while (cur.left) { | ||
| cur = cur.left; | ||
@@ -158,3 +216,6 @@ } | ||
| let cur = this.root; | ||
| while (cur && cur.right) { | ||
| if (!cur) { | ||
| return undefined; | ||
| } | ||
| while (cur.right) { | ||
| cur = cur.right; | ||
@@ -164,79 +225,62 @@ } | ||
| } | ||
| remove(v) { | ||
| this.root = this._remove(this.root, v); | ||
| findMinNode(node) { | ||
| if (!node) { | ||
| return null; | ||
| } | ||
| let cur = node; | ||
| while (cur.left) { | ||
| cur = cur.left; | ||
| } | ||
| return cur; | ||
| } | ||
| } | ||
| class AVLTree extends BinarySearchTree { | ||
| constructor() { | ||
| super(); | ||
| findMaxNode(node) { | ||
| if (!node) { | ||
| return null; | ||
| } | ||
| let cur = node; | ||
| while (cur.right) { | ||
| cur = cur.right; | ||
| } | ||
| return cur; | ||
| } | ||
| insert(v) { | ||
| this._insertNode(this.root, this.createNode(v)); | ||
| } | ||
| _insertNode(node, newNode) { | ||
| _remove(node, value) { | ||
| if (!node) { | ||
| node = newNode; | ||
| return null; | ||
| } | ||
| else if (newNode.value < node.value) { | ||
| node.left = this._insertNode(node.left, newNode); | ||
| if (node.left) { | ||
| // 是否需要平衡 | ||
| if (this.heightNode(node.left) - this.heightNode(node.right) > 1) { | ||
| if (newNode.value < node.left.value) { | ||
| node = this._rotationLL(node); | ||
| } | ||
| else { | ||
| node = this._rotationLR(node); | ||
| } | ||
| } | ||
| } | ||
| if (value < node.value) { | ||
| node.left = this._remove(node.left, value); | ||
| return node; | ||
| } | ||
| else if (newNode.value > node.value) { | ||
| node.right = this._insertNode(node.right, newNode); | ||
| if (node.right) { | ||
| // 是否需要平衡 | ||
| if (this.heightNode(node.right) - this.heightNode(node.left) > 1) { | ||
| if (newNode.value > node.right.value) { | ||
| node = this._rotationRR(node); | ||
| } | ||
| else { | ||
| node = this._rotationRL(node); | ||
| } | ||
| } | ||
| else if (value > node.value) { | ||
| node.right = this._remove(node.right, value); | ||
| return node; | ||
| } | ||
| else { | ||
| // 有0个节点 | ||
| if (!node.left && !node.right) { | ||
| node = null; | ||
| return node; | ||
| } | ||
| // 有1个节点 | ||
| if (!node.left) { | ||
| node = node.right; | ||
| return node; | ||
| } | ||
| else if (!node.right) { | ||
| node = node.left; | ||
| return node; | ||
| } | ||
| // 有2个节点 | ||
| let t = this.findMinNode(node.right); | ||
| node.value = t.value; | ||
| node.right = this._remove(node.right, t.value); | ||
| return node; | ||
| } | ||
| return node; | ||
| } | ||
| // 向左的单旋转 | ||
| _rotationRR(node) { | ||
| let t = node.right; | ||
| node.right = t.left; | ||
| t.left = node; | ||
| return t; | ||
| remove(v) { | ||
| this.root = this._remove(this.root, v); | ||
| } | ||
| // 向右的单旋转 | ||
| _rotationLL(node) { | ||
| let t = node.left; | ||
| node.left = t.right; | ||
| t.right = node; | ||
| return t; | ||
| } | ||
| // 向右的双旋转 | ||
| _rotationLR(node) { | ||
| node.left = this._rotationRR(node.left); | ||
| return this._rotationLL(node); | ||
| } | ||
| // 向左的双旋转 | ||
| _rotationRL(node) { | ||
| node.right = this._rotationLL(node.right); | ||
| return this._rotationRR(node); | ||
| } | ||
| } | ||
| class RedBackTree extends BinarySearchTree { | ||
| constructor() { | ||
| super(); | ||
| } | ||
| } | ||
| export { AVLTree, BaseTree, BinarySearchTree, RedBackTree }; | ||
| export { BinarySearchTree }; | ||
| //# sourceMappingURL=tree.js.map |
| { | ||
| "name": "data-footstone", | ||
| "version": "0.1.8", | ||
| "version": "0.1.11", | ||
| "description": "data structure", | ||
@@ -75,3 +75,3 @@ "author": "feigebaobei <18515195415@163.com>", | ||
| }, | ||
| "gitHead": "67722bbb00b8a6f85c274ae41c4209b5d1c628b2" | ||
| "gitHead": "3c32fa18edb1159d85dee53f1428ee2459a7ec18" | ||
| } |
@@ -9,3 +9,8 @@ import { Stack } from './stack'; | ||
| import { HashMap, djb2HashFn, loseloseHashFn } from './hashMap'; | ||
| import { BaseTree, BinarySearchTree, AVLTree, RedBackTree } from './tree'; | ||
| import { | ||
| // BaseTree, | ||
| BinarySearchTree, | ||
| // AVLTree, | ||
| // RedBackTree, | ||
| } from './tree'; | ||
| import * as order from './order'; | ||
@@ -16,2 +21,7 @@ import { Lru, Fifo, Lfu } from './store'; | ||
| // PMap, | ||
| HashMap, djb2HashFn, loseloseHashFn, BaseTree, BinarySearchTree, AVLTree, RedBackTree, order, Lru, Fifo, Lfu, }; | ||
| HashMap, djb2HashFn, loseloseHashFn, | ||
| // BaseTree, | ||
| BinarySearchTree, | ||
| // AVLTree, | ||
| // RedBackTree, | ||
| order, Lru, Fifo, Lfu, }; |
@@ -1,2 +0,109 @@ | ||
| class BaseTree { | ||
| // class BaseTree<T> implements BT<T> { | ||
| // // root: BTN<T> | null | ||
| // // constructor() { | ||
| // // this.root = null | ||
| // // } | ||
| // // createNode(v: T) { | ||
| // // return { | ||
| // // value: v, | ||
| // // left: null, | ||
| // // right: null, | ||
| // // } | ||
| // // } | ||
| // // 先父节点，再左节点，再右节点 | ||
| // _preOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // cb(node.value) | ||
| // this._preOrderTraverse(cb, node.left) | ||
| // this._preOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // // 整体从左到右依次操作 | ||
| // _inOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // this._inOrderTraverse(cb, node.left) | ||
| // cb(node.value) | ||
| // this._inOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // // 先左节点，再右节点，再父节点 | ||
| // _postOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // this._postOrderTraverse(cb, node.left) | ||
| // this._postOrderTraverse(cb, node.right) | ||
| // cb(node.value) | ||
| // } | ||
| // } | ||
| // // _findMinNode(node: BTN<T> | null) { | ||
| // // let cur = node | ||
| // // while (cur && cur.left) { | ||
| // // cur = cur.left | ||
| // // } | ||
| // // return cur | ||
| // // } | ||
| // // 不应该在这里搞这样的逻辑 | ||
| // _remove(node: BTN<T>, value: T) { | ||
| // if (!node) { | ||
| // return null | ||
| // } | ||
| // if (value < node.value) { | ||
| // node.left = this._remove(node.left, value) | ||
| // return node | ||
| // } else if (value > node.value) { | ||
| // node.right = this._remove(node.right, value) | ||
| // return node | ||
| // } else { | ||
| // // 有0个节点 | ||
| // if (!node.left && !node.right) { | ||
| // node = null | ||
| // return node | ||
| // } | ||
| // // 有1个节点 | ||
| // if (!node.left) { | ||
| // node = node.right | ||
| // return node | ||
| // } else if (!node.right) { | ||
| // node = node.left | ||
| // return node | ||
| // } | ||
| // // 有2个节点 | ||
| // let t = this._findMinNode(node.right) | ||
| // node.value = t.value | ||
| // node.right = this._remove(node.right, t.value) | ||
| // return node | ||
| // } | ||
| // } | ||
| // 返回节点的高度。 | ||
| // heightNode(node: BTN<T>): N { | ||
| // return node | ||
| // ? Math.max(this.heightNode(node.left), this.heightNode(node.right)) + 1 | ||
| // : -1 | ||
| // } | ||
| // // 待测试 | ||
| // shortPathNodeLength(node = null, deep = 0) { | ||
| // if (!node) { | ||
| // return deep | ||
| // } else { | ||
| // let queue = new Queue<BTN<T>>() | ||
| // queue.enqueue(node) | ||
| // let len = queue.size() | ||
| // while (len) { | ||
| // let i = 0 | ||
| // while (i < len) { | ||
| // let n = queue.dequeue() | ||
| // if (!n.left && !n.right) { | ||
| // return deep | ||
| // } else { | ||
| // n.left && queue.enqueue(n.left) | ||
| // n.right && queue.enqueue(n.right) | ||
| // } | ||
| // i++ | ||
| // } | ||
| // deep++ | ||
| // len = queue.size() | ||
| // } | ||
| // } | ||
| // } | ||
| // } | ||
| class BinarySearchTree { | ||
| constructor() { | ||
@@ -12,77 +119,22 @@ this.root = null; | ||
| } | ||
| // 先父节点，再左节点，再右节点 | ||
| _preOrderTraverse(cb, node) { | ||
| if (node) { | ||
| cb(node.value); | ||
| this._preOrderTraverse(cb, node.left); | ||
| this._preOrderTraverse(cb, node.right); | ||
| _insertNode(node, newNode) { | ||
| if (newNode.value < node.value) { | ||
| // if (!node.left) { | ||
| // node.left = newNode | ||
| // } else { | ||
| // this._insertNode(node.left, newNode) | ||
| // } | ||
| node.left ? this._insertNode(node.left, newNode) : (node.left = newNode); | ||
| } | ||
| } | ||
| // 整体从左到右依次操作 | ||
| _inOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._inOrderTraverse(cb, node.left); | ||
| cb(node.value); | ||
| this._inOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| // 先左节点，再右节点，再父节点 | ||
| _postOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._postOrderTraverse(cb, node.left); | ||
| this._postOrderTraverse(cb, node.right); | ||
| cb(node.value); | ||
| } | ||
| } | ||
| _findMinNode(node) { | ||
| let cur = node; | ||
| while (cur && cur.left) { | ||
| cur = cur.left; | ||
| } | ||
| return cur; | ||
| } | ||
| _remove(node, value) { | ||
| if (!node) { | ||
| return null; | ||
| } | ||
| if (value < node.value) { | ||
| node.left = this._remove(node.left, value); | ||
| return node; | ||
| } | ||
| else if (value > node.value) { | ||
| node.right = this._remove(node.right, value); | ||
| return node; | ||
| } | ||
| else { | ||
| // 有0个节点 | ||
| if (!node.left && !node.right) { | ||
| node = null; | ||
| return node; | ||
| } | ||
| // 有1个节点 | ||
| if (!node.left) { | ||
| node = node.right; | ||
| return node; | ||
| } | ||
| else if (!node.right) { | ||
| node = node.left; | ||
| return node; | ||
| } | ||
| // 有2个节点 | ||
| let t = this._findMinNode(node.right); | ||
| node.value = t.value; | ||
| node.right = this._remove(node.right, t.value); | ||
| return node; | ||
| node.right | ||
| ? this._insertNode(node.right, newNode) | ||
| : (node.right = newNode); | ||
| // if (!node.right) { | ||
| // node.right = newNode | ||
| // } else { | ||
| // this._insertNode(node.right, newNode) | ||
| // } | ||
| } | ||
| } | ||
| heightNode(node) { | ||
| return node | ||
| ? Math.max(this.heightNode(node.left), this.heightNode(node.right)) + 1 | ||
| : -1; | ||
| } | ||
| } | ||
| class BinarySearchTree extends BaseTree { | ||
| constructor() { | ||
| super(); | ||
| } | ||
| insert(v) { | ||
@@ -97,20 +149,2 @@ let node = this.createNode(v); | ||
| } | ||
| _insertNode(node, newNode) { | ||
| if (newNode.value < node.value) { | ||
| if (!node.left) { | ||
| node.left = newNode; | ||
| } | ||
| else { | ||
| this._insertNode(node.left, newNode); | ||
| } | ||
| } | ||
| else { | ||
| if (!node.right) { | ||
| node.right = newNode; | ||
| } | ||
| else { | ||
| this._insertNode(node.right, newNode); | ||
| } | ||
| } | ||
| } | ||
| // 是否存在 | ||
@@ -134,6 +168,27 @@ search(v) { | ||
| } | ||
| _preOrderTraverse(cb, node) { | ||
| if (node) { | ||
| cb(node.value); | ||
| this._preOrderTraverse(cb, node.left); | ||
| this._preOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _inOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._inOrderTraverse(cb, node.left); | ||
| cb(node.value); | ||
| this._inOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _postOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._postOrderTraverse(cb, node.left); | ||
| this._postOrderTraverse(cb, node.right); | ||
| cb(node.value); | ||
| } | ||
| } | ||
| traverse(cb, order = 'inOrder') { | ||
| switch (order) { | ||
| case 'preOrder': | ||
| this._inOrderTraverse(cb, this.root); | ||
| this._preOrderTraverse(cb, this.root); | ||
| break; | ||
@@ -150,3 +205,6 @@ case 'inOrder': | ||
| let cur = this.root; | ||
| while (cur && cur.left) { | ||
| if (!cur) { | ||
| return undefined; | ||
| } | ||
| while (cur.left) { | ||
| cur = cur.left; | ||
@@ -158,3 +216,6 @@ } | ||
| let cur = this.root; | ||
| while (cur && cur.right) { | ||
| if (!cur) { | ||
| return undefined; | ||
| } | ||
| while (cur.right) { | ||
| cur = cur.right; | ||
@@ -164,77 +225,132 @@ } | ||
| } | ||
| remove(v) { | ||
| this.root = this._remove(this.root, v); | ||
| findMinNode(node) { | ||
| if (!node) { | ||
| return null; | ||
| } | ||
| let cur = node; | ||
| while (cur.left) { | ||
| cur = cur.left; | ||
| } | ||
| return cur; | ||
| } | ||
| } | ||
| class AVLTree extends BinarySearchTree { | ||
| constructor() { | ||
| super(); | ||
| findMaxNode(node) { | ||
| if (!node) { | ||
| return null; | ||
| } | ||
| let cur = node; | ||
| while (cur.right) { | ||
| cur = cur.right; | ||
| } | ||
| return cur; | ||
| } | ||
| insert(v) { | ||
| this._insertNode(this.root, this.createNode(v)); | ||
| } | ||
| _insertNode(node, newNode) { | ||
| _remove(node, value) { | ||
| if (!node) { | ||
| node = newNode; | ||
| return null; | ||
| } | ||
| else if (newNode.value < node.value) { | ||
| node.left = this._insertNode(node.left, newNode); | ||
| if (node.left) { | ||
| // 是否需要平衡 | ||
| if (this.heightNode(node.left) - this.heightNode(node.right) > 1) { | ||
| if (newNode.value < node.left.value) { | ||
| node = this._rotationLL(node); | ||
| } | ||
| else { | ||
| node = this._rotationLR(node); | ||
| } | ||
| } | ||
| } | ||
| if (value < node.value) { | ||
| node.left = this._remove(node.left, value); | ||
| return node; | ||
| } | ||
| else if (newNode.value > node.value) { | ||
| node.right = this._insertNode(node.right, newNode); | ||
| if (node.right) { | ||
| // 是否需要平衡 | ||
| if (this.heightNode(node.right) - this.heightNode(node.left) > 1) { | ||
| if (newNode.value > node.right.value) { | ||
| node = this._rotationRR(node); | ||
| } | ||
| else { | ||
| node = this._rotationRL(node); | ||
| } | ||
| } | ||
| else if (value > node.value) { | ||
| node.right = this._remove(node.right, value); | ||
| return node; | ||
| } | ||
| else { | ||
| // 有0个节点 | ||
| if (!node.left && !node.right) { | ||
| node = null; | ||
| return node; | ||
| } | ||
| // 有1个节点 | ||
| if (!node.left) { | ||
| node = node.right; | ||
| return node; | ||
| } | ||
| else if (!node.right) { | ||
| node = node.left; | ||
| return node; | ||
| } | ||
| // 有2个节点 | ||
| let t = this.findMinNode(node.right); | ||
| node.value = t.value; | ||
| node.right = this._remove(node.right, t.value); | ||
| return node; | ||
| } | ||
| return node; | ||
| } | ||
| // 向左的单旋转 | ||
| _rotationRR(node) { | ||
| let t = node.right; | ||
| node.right = t.left; | ||
| t.left = node; | ||
| return t; | ||
| remove(v) { | ||
| this.root = this._remove(this.root, v); | ||
| } | ||
| // 向右的单旋转 | ||
| _rotationLL(node) { | ||
| let t = node.left; | ||
| node.left = t.right; | ||
| t.right = node; | ||
| return t; | ||
| } | ||
| // 向右的双旋转 | ||
| _rotationLR(node) { | ||
| node.left = this._rotationRR(node.left); | ||
| return this._rotationLL(node); | ||
| } | ||
| // 向左的双旋转 | ||
| _rotationRL(node) { | ||
| node.right = this._rotationLL(node.right); | ||
| return this._rotationRR(node); | ||
| } | ||
| } | ||
| class RedBackTree extends BinarySearchTree { | ||
| constructor() { | ||
| super(); | ||
| } | ||
| } | ||
| export { BaseTree, BinarySearchTree, AVLTree, RedBackTree }; | ||
| // class AVLTree<T> extends BinarySearchTree<T> implements AVLT<T> { | ||
| // constructor() { | ||
| // super() | ||
| // } | ||
| // insert(v: T): void { | ||
| // this._insertNode(this.root, this.createNode(v)) | ||
| // } | ||
| // _insertNode(node: BTN<T>, newNode: BTN<T>): BTN<T> { | ||
| // if (!node) { | ||
| // node = newNode | ||
| // } else if (newNode.value < node.value) { | ||
| // node.left = this._insertNode(node.left, newNode) | ||
| // if (node.left) { | ||
| // // 是否需要平衡 | ||
| // if (this.heightNode(node.left) - this.heightNode(node.right) > 1) { | ||
| // if (newNode.value < node.left.value) { | ||
| // node = this._rotationLL(node) | ||
| // } else { | ||
| // node = this._rotationLR(node) | ||
| // } | ||
| // } | ||
| // } | ||
| // } else if (newNode.value > node.value) { | ||
| // node.right = this._insertNode(node.right, newNode) | ||
| // if (node.right) { | ||
| // // 是否需要平衡 | ||
| // if (this.heightNode(node.right) - this.heightNode(node.left) > 1) { | ||
| // if (newNode.value > node.right.value) { | ||
| // node = this._rotationRR(node) | ||
| // } else { | ||
| // node = this._rotationRL(node) | ||
| // } | ||
| // } | ||
| // } | ||
| // } | ||
| // return node | ||
| // } | ||
| // // 向左的单旋转 | ||
| // _rotationRR(node: BTN<T>) { | ||
| // let t = node.right | ||
| // node.right = t.left | ||
| // t.left = node | ||
| // return t | ||
| // } | ||
| // // 向右的单旋转 | ||
| // _rotationLL(node: BTN<T>) { | ||
| // let t = node.left | ||
| // node.left = t.right | ||
| // t.right = node | ||
| // return t | ||
| // } | ||
| // // 向右的双旋转 | ||
| // _rotationLR(node: BTN<T>) { | ||
| // node.left = this._rotationRR(node.left) | ||
| // return this._rotationLL(node) | ||
| // } | ||
| // // 向左的双旋转 | ||
| // _rotationRL(node: BTN<T>) { | ||
| // node.right = this._rotationLL(node.right) | ||
| // return this._rotationRR(node) | ||
| // } | ||
| // } | ||
| // class RedBackTree<T> extends BinarySearchTree<T> implements RBT<T> { | ||
| // constructor() { | ||
| // super() | ||
| // } | ||
| // } | ||
| export { | ||
| // BaseTree, | ||
| BinarySearchTree, | ||
| // AVLTree, | ||
| // RedBackTree, | ||
| }; |
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
New alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Fixed alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Improved metrics
- Total package byte prevSize
- increased by2.19%
356604
- Lines of code
- increased by3.74%
5764
No dependency changes