备案 网站名称,怎样在百度上注册自己的店铺,产品推广计划怎么写,网页界面设计作品推荐1. BST二叉查找树
1.1 BST二叉查找树的特性
左子树上所有结点的值均小于或等于它的根结点的值。右子树上所有结点的值均大于或等于它的根结点的值。左、右子树也分别为二叉排序树。
1.2 BST二叉查找树的缺点
二叉查找树是有缺点的#xff0c;在不断插入的时候#xff0c;…1. BST二叉查找树
1.1 BST二叉查找树的特性
左子树上所有结点的值均小于或等于它的根结点的值。右子树上所有结点的值均大于或等于它的根结点的值。左、右子树也分别为二叉排序树。
1.2 BST二叉查找树的缺点
二叉查找树是有缺点的在不断插入的时候有可能出现这样一种情况很容易“退化”成链表如果bst 树的节点正好从大到小的插入此时树的结构也类似于链表结构这时候的查询或写入耗时与链表相同。 为了避免这种特殊的情况发生引入了平衡二叉树AVL和红黑树red-black tree
2. AVL平衡二叉树
平衡二叉树也叫AVL发明者名字简写也属于二叉搜索树的一种与其不同的是AVL通过机制保证其自身的平衡。 AVL树是最先发明的自平衡二叉查找树。 在AVL树中任何节点的两个子树的高度最大差别为1所以它也被称为高度平衡树。 增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。 2.1 AVL树的特性
AVL树本质上还是一棵二叉搜索树它有以下特性
特性1 对于任何一颗子树的root根结点而言它的左子树任何节点的key一定比root小而右子树任何节点的key 一定比root大特性2对于AVL树而言其中任何子树仍然是AVL树特性3每个节点的左右子节点的高度之差的绝对值最多为1
在插入、删除树节点的时候如果破坏了以上的原则AVL树会自动进行调整使得以上三条原则仍然成立。
2.2 AVL树的平衡功能
举个例子下左图为AVL树最长的2节点与最短的8节点高度差为1
当插入一个新的节点后根据上面第一条原则它会出现在2节点的左子树但这样一来就违反了原则3。 此时AVL树会通过节点的旋转进行进行平衡
AVL调整的过程称之为左旋和右旋左旋就是逆时针转右旋是顺时针转
2.3 AVL平衡的调整过程
调整的过程
确定旋转支点pivot这个旋转支点就是失去平衡这部分树在自平衡之后的根节点平衡的调整过程需要根据pivot它来进行旋转。我们只关注失衡子树的根结点 及它的子节点和孙子节点即可。判断AVL失衡的类型包含左左结构失衡LL型失衡、右右结构失衡RR型失衡、左右结构失衡LR型失衡、右左结构失衡RL型失衡根据失衡的类型进行相应的旋转
2.3.1 场景1LL失衡-左左结构失衡右旋
在结点Root的 左结点L 的 左子树L 上做了插入元素的操作我们称这种情况为 左左型 我们应该进行右旋转。
2.3.2 场景2RR型失衡右右结构失衡左旋
在结点Root的 右结点R 的 右子树R 上做了插入元素的操作我们称这种情况为右右型 我们应该进行左旋转。
2.3.3 场景3 LR型失衡左右失衡左旋右旋
在结点Root的 左结点L 的 右子树R 上做了插入元素的操作我们称这种情况为左右型 我们应该进行左旋转右旋转。
2.3.4 场景4RL失衡: 右左结构 右旋左旋
在结点Root的 右结点R 的 左子树L 上做了插入元素的操作我们称这种情况为右左型 我们应该进行右旋转左旋转。
3. 代码实现详细注解
3.1 基本结构操作
package mainimport fmt// AVL树的节点
type Node struct {Key intHeight intLeft *NodeRight *Node
}type AVLTree struct {Root *Node
}// 返回节点的高度
func height(n *Node) int {if n nil {return 0}return n.Height
}func max(a, b int) int {if a b {return a}return b
}// 返回当前节点的平衡因子
func getBalance(n *Node) int {if n nil {return 0}return height(n.Left) - height(n.Right)
}// 右旋
func rightRotate(root *Node) *Node {//pivot是新的根节点T2是要转移的子树的根pivot : root.LeftT2 : pivot.Rightpivot.Right rootroot.Left T2// 重新计算两个调整后的节点高度root.Height max(height(root.Left), height(root.Right)) 1pivot.Height max(height(pivot.Left), height(pivot.Right)) 1return pivot
}// 右旋
func leftRotate(root *Node) *Node {//pivot是新的根节点T2是要转移的子树的根pivot : root.RightT2 : pivot.Leftpivot.Left rootroot.Right T2// 重新计算两个调整后的节点高度root.Height max(height(root.Left), height(root.Right)) 1pivot.Height max(height(pivot.Left), height(pivot.Right)) 1return pivot
}// 查找
func (t *AVLTree) Search(key int) *Node {return search(t.Root, key)
}func search(node *Node, key int) *Node {if node nil {return nil}if key node.Key {return node}if key node.Key {return search(node.Left, key)}return search(node.Right, key)
}3.2 插入操作
func (t *AVLTree) Insert(key int) {t.Root insert(t.Root, key)
}func insert(node *Node, key int) *Node {// 1. 找到插入节点的位置if node nil {return Node{Key: key, Height: 1}}if key node.Key {node.Left insert(node.Left, key)} else if key node.Key {node.Right insert(node.Right, key)} else {//重复的key是不被允许的return node}// 2. 更新新插入节点的祖先节点的高度node.Height max(height(node.Left), height(node.Right)) 1// 3. 获得当前节点的平衡因子balance : getBalance(node)// 4. 平衡调整// 4.1说明新插入的节点插入到了当前节点的左节点的左孩子需要进行右旋if balance 1 key node.Left.Key {return rightRotate(node)}// 4.2说明新插入的节点插入到了当前节点的右节点的右孩子需要进行左旋if balance -1 key node.Right.Key {return leftRotate(node)}// 4.3说明新插入的节点插入到了当前节点的左节点的右孩子需要进行左旋右旋if balance 1 key node.Right.Key {node.Left leftRotate(node.Left)return rightRotate(node)}// 4.4说明新插入的节点插入到了当前节点的右节点的左孩子需要进行右旋左旋if balance -1 key node.Left.Key {node.Right rightRotate(node.Right)return leftRotate(node)}// 4.5 不要需要进行平衡调整return node
}3.3 删除操作
func (t *AVLTree) Delete(key int) {t.Root delete(t.Root, key)
}func delete(node *Node, key int) *Node {if node nil {return nil}// 1. 找到要删除的节点if key node.Key {node.Left delete(node.Left, key)} else if key node.Key {node.Right delete(node.Right, key)} else {// 被删除的节点是叶子节点或者只有一个孩子节点if node.Left nil {return node.Right} else if node.Right nil {return node.Left}// 被删除的节点下面还有两个孩子节点// 先找到被删除节点下面最小的值temp : minValueNode(node.Right)// 将最小的值放到当前节点node.Key temp.Key// 递归删除最小值node.Right delete(node.Right, temp.Key)}if node nil {return node}// 2. 更新新插入节点的祖先节点的高度node.Height max(height(node.Left), height(node.Right)) 1// 3. 获得当前节点的平衡因子balance : getBalance(node)// 4. 平衡调整// 4.1说明新删除的节点导致当前节点的平衡因子出了问题// 判断是当前节点左节点的左孩子造成的需要进行右旋if balance 1 getBalance(node.Left) 0 {return rightRotate(node)}// 4.2说明新删除的节点导致当前节点的平衡因子出了问题// 判断是当前节点右节点的右孩子造成的需要进行左旋if balance -1 getBalance(node.Right) 0 {return leftRotate(node)}// 4.3说明新删除的节点导致当前节点的平衡因子出了问题// 判断是当前节点左节点的右孩子造成的需要进行左旋右旋if balance 1 getBalance(node.Left) 0 {node.Left leftRotate(node.Left)return rightRotate(node)}// 4.4说明新删除的节点导致当前节点的平衡因子出了问题// 判断是当前节点右节点的左孩子造成的需要进行右旋左旋if balance -1 getBalance(node.Right) 0 {node.Right rightRotate(node.Right)return leftRotate(node)}// 4.5 不要需要进行平衡调整return node
}func minValueNode(node *Node) *Node {current : nodefor current.Left ! nil {current current.Left}return current
}3.4 测试
func main() {tree : AVLTree{}// 插入节点tree.Insert(10)tree.Insert(20)tree.Insert(30)tree.Insert(40)tree.Insert(50)tree.Insert(60)tree.Insert(70)// 层次遍历fmt.Println(LevelOrder(tree.Root))tree.Delete(10)tree.Delete(20)tree.Delete(30)fmt.Println(LevelOrder(tree.Root))
}// LevelOrder 返回层次遍历的结果按层分组
func LevelOrder(root *Node) [][]int {result : make([][]int, 0)if root nil {return result}// 使用队列来存储节点queue : []*Node{root}for len(queue) 0 {// 当前层的节点数levelSize : len(queue)// 存储当前层的值currentLevel : make([]int, 0, levelSize)// 遍历当前层的所有节点for i : 0; i levelSize; i {// 获取队首节点node : queue[0]queue queue[1:] // 出队// 将当前节点的值加入当前层的结果中currentLevel append(currentLevel, node.Key)// 将子节点加入队列if node.Left ! nil {queue append(queue, node.Left)}if node.Right ! nil {queue append(queue, node.Right)}}// 将当前层的结果加入最终结果result append(result, currentLevel)}return result
}层次遍历的结果符合预期
