proxy.golang.org : github.com/lujin123/algorithms/data-structure/golang
* 非递归实现的一个AVL树 这是对递归版本的优化： 插入：优化插入节点时候回溯计算节点高度和旋转操作，旋转的操作是一个常量（0，1，2），而对高度的调整其实也是一个常量（最多两次）， 因为插入一个节点，会有两个结果： a. 子树依旧保持平衡，无需旋转操作，就只需要调整高度即可，而增加节点可能会导致父节点高度变化，也可能不会变化，如果变化了，就调整继续回溯，如果不变化，直接结束即可 b. 子树不平衡，这时候就需要通过旋转来平衡，可以是一次或者两次旋转，这样会导致子树高度-1，这时候就抵消了增加节点带了的父节点的高度变化，所以旋转后可以直接结束，无需回溯 删除：在找到待删除的节点后，判断子树的数量： a. 左右子树不全：找到存在的子树，连接到当前节点的父节点即可 b. 左右子树全都有： 这时候需要找一个节点做替换，可以先判断下左右子树的高度，就找子树比较高的那边的节点代替，如果是左子树，则找最大节点，如果是右子树，则找最小节点，找到后交换内容之后按照a去走 删除后平衡父节点，重新计算高度，只有在高度相同并且子树平衡的情况下停止回溯，否则继续回溯，重新计算高度 * 二叉查找树实现 1. Insert 2. Delete 3. Find 4. FindMax 5. FindMin
Registry
-
Source
- Documentation
- JSON
- codemeta.json
purl: pkg:golang/github.com/lujin123/algorithms/data-structure/golang
Keywords:
datastructures
, golang
, leetcode
, python
License: MIT
Latest release: 10 months ago
Namespace: github.com/lujin123/algorithms/data-structure
Stars: 0 on GitHub
Forks: 0 on GitHub
See more repository details: repos.ecosyste.ms
Last synced: 10 months ago