AVL

Documentation

Index

• type AvlTree
  • func NewAVLTree() *AvlTree
  • func (tree *AvlTree) Add(value int)
  • func (tree *AvlTree) Find(value int) *AvlTreeNode
  • func (tree *AvlTree) FindMaxValue() *AvlTreeNode
  • func (tree *AvlTree) FindMinValue() *AvlTreeNode
  • func (tree *AvlTree) MidOrder()
• type AvlTreeNode
  • func LeftRightRotation(node *AvlTreeNode) *AvlTreeNode
  • func LeftRotation(Root *AvlTreeNode) *AvlTreeNode
  • func RightLeftRotation(node *AvlTreeNode) *AvlTreeNode
  • func RightRotation(Root *AvlTreeNode) *AvlTreeNode
  • func (node *AvlTreeNode) BalanceFactor() int
  • func (node *AvlTreeNode) UpdateHeight()
• type KV

Types

type AvlTree

type AvlTree struct {
	Root *AvlTreeNode // 树根节点
}

AvlTree AVL树

func NewAVLTree

func NewAVLTree() *AvlTree

NewAVLTree 初始化一个AVL树

func (*AvlTree) Add

func (tree *AvlTree) Add(value int)

func (*AvlTree) Find

func (tree *AvlTree) Find(value int) *AvlTreeNode

Find 查找指定节点

func (*AvlTree) FindMaxValue

func (tree *AvlTree) FindMaxValue() *AvlTreeNode

FindMaxValue 找出最大值的节点

func (*AvlTree) FindMinValue

func (tree *AvlTree) FindMinValue() *AvlTreeNode

FindMinValue 找出最小值的节点

func (*AvlTree) MidOrder

func (tree *AvlTree) MidOrder()

MidOrder 中序遍历

type AvlTreeNode

type AvlTreeNode struct {
	Value  int          // 值
	Times  int          // 值出现的次数
	Height int          // 该节点作为树根节点，树的高度，方便计算平衡因子
	Left   *AvlTreeNode // 左子树
	Right  *AvlTreeNode // 右字树
	// contains filtered or unexported fields
}

AvlTreeNode AVL节点

func LeftRightRotation

func LeftRightRotation(node *AvlTreeNode) *AvlTreeNode

LeftRightRotation 先左后右旋操作

func LeftRotation

func LeftRotation(Root *AvlTreeNode) *AvlTreeNode

LeftRotation 单左旋操作

func RightLeftRotation

func RightLeftRotation(node *AvlTreeNode) *AvlTreeNode

RightLeftRotation 先右后左旋操作

func RightRotation

func RightRotation(Root *AvlTreeNode) *AvlTreeNode

RightRotation 单右旋操作

func (*AvlTreeNode) BalanceFactor

func (node *AvlTreeNode) BalanceFactor() int

BalanceFactor 计算平衡因子

func (*AvlTreeNode) UpdateHeight

func (node *AvlTreeNode) UpdateHeight()

UpdateHeight 更新节点的树高度

type KV

type KV struct {
	// contains filtered or unexported fields
}

KV 节点