Last active
April 4, 2023 06:45
-
-
Save mrchaofan/ce3682cdd84070598e85536c164fc53f to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * @typedef {{ | |
| * level: number | |
| * data: number | |
| * left: TreeNode | |
| * right: TreeNode | |
| * }} TreeNode | |
| */ | |
| /** | |
| * @type {TreeNode} | |
| */ | |
| const NULL_NODE = { | |
| level: 0, | |
| } | |
| NULL_NODE.left = NULL_NODE.right = NULL_NODE | |
| Object.freeze(NULL_NODE) | |
| /** | |
| * | |
| * @param {number} data | |
| * @returns {TreeNode} | |
| */ | |
| function createTreeNode (data) { | |
| return { | |
| level: 1, | |
| data, | |
| left: NULL_NODE, | |
| right: NULL_NODE, | |
| } | |
| } | |
| class AATree { | |
| /** | |
| * | |
| * @param {TreeNode} node | |
| */ | |
| static skew (node) { | |
| if (node !== NULL_NODE & node.left.level === node.level) { | |
| const nodeLeft = node.left | |
| node.left = nodeLeft.right | |
| nodeLeft.right = node | |
| return nodeLeft | |
| } | |
| return node | |
| } | |
| /** | |
| * | |
| * @param {TreeNode} node | |
| */ | |
| static split (node) { | |
| if (node !== NULL_NODE && node.right.right.level === node.level) { | |
| const nodeRight = node.right | |
| node.right = nodeRight.left | |
| nodeRight.left = node | |
| ++nodeRight.level | |
| return nodeRight | |
| } | |
| return node | |
| } | |
| /** | |
| * @param {TreeNode} parent | |
| * @param {any} data | |
| */ | |
| static insert (parent, data) { | |
| if (parent === NULL_NODE) { | |
| const node = createTreeNode(data) | |
| return node | |
| } | |
| if (data < parent.data) { | |
| parent.left = this.insert(parent.left, data) | |
| } | |
| if (data > parent.data) { | |
| parent.right = this.insert(parent.right, data) | |
| } | |
| parent = this.skew(parent) | |
| parent = this.split(parent) | |
| return parent | |
| } | |
| /** | |
| * | |
| * @param {TreeNode} parent | |
| * @param {number} data | |
| * @param {{ | |
| * lastNode: TreeNode | |
| * deleteNode: TreeNode | |
| * }} context | |
| */ | |
| static remove (parent, data, context) { | |
| if (parent !== NULL_NODE) { | |
| context.lastNode = parent | |
| if (data < parent.data) { | |
| parent.left = this.remove(parent.left, data, context) | |
| } else { | |
| context.deleteNode = parent | |
| parent.right = this.remove(parent.right, data, context) | |
| } | |
| if (context.lastNode === parent) { | |
| if (context.deleteNode !== NULL_NODE && context.deleteNode.data === data) { | |
| context.deleteNode.data = parent.data | |
| context.deleteNode = NULL_NODE | |
| parent = parent.right | |
| } | |
| } else if (parent.left.level < parent.level - 1 || parent.right.level < parent.level - 1) { | |
| --parent.level | |
| if (parent.right.level > parent.level) { | |
| parent.right.level = parent.level | |
| } | |
| parent = this.skew(parent) | |
| parent.right = this.skew(parent.right) | |
| parent.right.right = this.skew(parent.right.right) | |
| parent = this.split(parent) | |
| parent.right = this.split(parent.right) | |
| } | |
| } | |
| return parent | |
| } | |
| /** | |
| * | |
| * @param {TreeNode} node | |
| */ | |
| static isNullNode (node) { | |
| return node === NULL_NODE | |
| } | |
| /** | |
| * | |
| * @param {TreeNode} parent | |
| * @param {number[]} results | |
| */ | |
| static inorderVisit (parent, results = []) { | |
| if (parent !== NULL_NODE) { | |
| if (parent.left !== NULL_NODE) { | |
| this.inorderVisit(parent.left, results) | |
| } | |
| results.push(parent.data) | |
| if (parent.right !== NULL_NODE) { | |
| this.inorderVisit(parent.right, results) | |
| } | |
| } | |
| return results | |
| } | |
| constructor () { | |
| this.root = NULL_NODE | |
| } | |
| /** | |
| * | |
| * @param {number} data | |
| */ | |
| insert (data) { | |
| this.root = AATree.insert(this.root, data) | |
| } | |
| /** | |
| * | |
| * @param {number} data | |
| */ | |
| remove (data) { | |
| this.root = AATree.remove(this.root, data, { | |
| lastNode: NULL_NODE, | |
| deleteNode: NULL_NODE, | |
| }) | |
| } | |
| /** | |
| * | |
| * @param {number[]} results | |
| * @returns {number[]} | |
| */ | |
| inorderVisit (results = []) { | |
| return AATree.inorderVisit(this.root, results) | |
| } | |
| } | |
| const aaTree = new AATree() | |
| aaTree.insert(1) | |
| aaTree.insert(2) | |
| aaTree.insert(3) | |
| aaTree.insert(4) | |
| aaTree.insert(5) | |
| aaTree.insert(6) | |
| aaTree.insert(7) | |
| aaTree.insert(8) | |
| aaTree.insert(9) | |
| aaTree.insert(10) | |
| aaTree.insert(11) | |
| aaTree.insert(12) | |
| aaTree.insert(13) | |
| aaTree.remove(2) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment