We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
能够保持平衡的BST
根据左右子树的高度差(大于2),来解决旋转的类型。
旋转类似链表的操作(断链插入)
将目标元素的值与比目标元素大一位的元素进行替换=>更新目标:删除目标元素大一位的元素
大小顺序: a < b < c < d < f < g
矩形的高度代表了树的高度
红色=>蓝色:代表了节点的变化
转化前:
转化后:
转化1前:
转化1后:
转化2前:
转化2后:
参考修改代码:
class AVLNode { constructor(val) { this.val = val this.left = null this.right = null this.height = 1 } getKey() {} } const BLANCE_STATE = { UNBALANCE_LEFT: 2, UNBALANCE_RIGHT: -2, SLIGHT_UNBALANCE_LEFT: 1, SLIGHT_UNBALANCE_RIGHT: -1, BALANCE: 0 } class AVLTree { constructor() { this.root = null } //RR _leftRotate(node) { const res = node.right ;[res.left, node.right] = [node, res.left] this._updateHeigh(node) return res } //LL _rightRotate(node) { const res = node.left ;[res.right, node.left] = [node, res.right] this._updateHeigh(node) return res } //LR _leftRightRotate(node) { node.left = this._updateHeigh(this._leftRotate(node.left)) return this._rightRotate(node) } //RL _rightLeftRotate(node) { node.right = this._updateHeigh(this._rightRotate(node.right)) return this._leftRotate(node) } _getHeight(node) { return node !== null ? node.height : 0 } _updateHeigh(node) { node.height = Math.max(this._getHeight(node.left), this._getHeight(node.right)) + 1 return node } insert(val) { this.root = this._insertNode(this.root, val) } _insertNode(node, val) { if (node === null) return new AVLNode(val) if (node.val === val) return node if (node.val < val) { node.right = this._insertNode(node.right, val) } else if (node.val > val) { node.left = this._insertNode(node.left, val) } return this._toBalance(node) } _toBalance(node) { if (node === null) return null const BalanceState = this._getBalanceState(node) if (BalanceState === BLANCE_STATE.UNBALANCE_LEFT) { const leftNodeBalanceState = this._getBalanceState(node.left) if (leftNodeBalanceState == BLANCE_STATE.SLIGHT_UNBALANCE_RIGHT) { return this._updateHeigh(this._leftRightRotate(node)) } else { return this._updateHeigh(this._rightRotate(node)) } } else if (BalanceState === BLANCE_STATE.UNBALANCE_RIGHT) { const rightNodeBalanceState = this._getBalanceState(node.right) if (rightNodeBalanceState == BLANCE_STATE.SLIGHT_UNBALANCE_LEFT) { return this._updateHeigh(this._rightLeftRotate(node)) } else { return this._updateHeigh(this._leftRotate(node)) } } return this._updateHeigh(node) } _getBalanceState(node) { return this._getHeight(node.left) - this._getHeight(node.right) } remove(val) { if (this.search(val) === null) return false this.root = this._removeNode(this.root, val) return true } _removeNode(node, val) { if (node.val > val) node.left = this._removeNode(node.left, val) else if (node.val < val) node.right = this._removeNode(node.right, val) else if (node.val == val) { if (node.left == null) return node.right else if (node.right == null) return node.left else { let next = this.getNext(val) node.val = next.val // 转为删除next节点 node.right = this._removeNode(node.right, node.val) } } return this._doBalance(node) } search(val) { let node = this.root while (node) { if (node.val === val) return node else if (node.val > val) node = node.right else node = node.left } return null } getNext(val) { let res = null, node = this.root while (node) { if (node.val <= val) node = node.right else if (node.val > val) { res = node node = node.left } } return res } } function arrayToBBST(nums) { let avlTree = new AVLTree() for (let i = 0; i < nums.length; i++) { avlTree.insert(nums[i]) } return avlTree }
ES6的JavaScript数据结构实现之树(二叉搜索树、AVL树、红黑树)
JS 二分递归 + AVL树
The text was updated successfully, but these errors were encountered:
No branches or pull requests
AVL树
能够保持平衡的BST
分析
旋转
根据左右子树的高度差(大于2),来解决旋转的类型。
旋转类似链表的操作(断链插入)
删除
将目标元素的值与比目标元素大一位的元素进行替换=>更新目标:删除目标元素大一位的元素
图
大小顺序: a < b < c < d < f < g
矩形的高度代表了树的高度
红色=>蓝色:代表了节点的变化
LL
转化前:
转化后:
RR
转化前:
转化后:
LR
转化1前:
转化1后:
转化2前:
转化2后:
RL
转化1前:
转化1后:
转化2前:
转化2后:
代码实现
参考修改代码:
参考
ES6的JavaScript数据结构实现之树(二叉搜索树、AVL树、红黑树)
JS 二分递归 + AVL树
The text was updated successfully, but these errors were encountered: