AVL树仍然是一棵二叉查找树。
平衡是指对AVL树的任意结点来说，其左子树和右子树的高度之差的绝对值不超过1。
平衡因子是指左子树和右子树的高度之差。
因此需要在树的结构中加入一个变量height
左旋的三个步骤：
①让B的左子树成为A的右子树
②让A成为B的左子树
③将根结点设定为结点B
右旋则把左旋代码里的lchild改为rchild，rchild改为lchild就行了
LL、LR、RR、RL：
在这个基础上，由于需要从插入的结点开始从下往上判断结点是否平衡，因此需要在每个insert函数之后更新当前子树的高度，并在这之后根据树型是LL型、LR型、RR型、RL型之一来进行平衡的操作：
Avl 平衡树 实现记录 Avl平衡二叉树和搜索二叉树基本实现原理相同，在搜索二叉树的基础上添加树平衡的操作--单...
本文主要包括以下内容： 平衡二叉树的概念 AVL树 插入操作保持AVL树的平衡 删除操作保持AVL树的平衡 平衡二...
平衡⼆二叉树( AVL 树) 平衡⼆二叉树(Self-Balancing Binary Search Tree 或...
本章内容 平衡二叉树定义 AVL树实现 一、平衡二叉树（AVL树定义） 能够在key插入时一直保持平衡的二叉查找树...
平衡二叉树( AVL 树) 平衡二叉树(Self-Balancing Binary Search Tree 或 H...
AVL树 概念：AVL树称为平衡二叉树，对于平衡二叉树，他的每个节点的左子树和右子树之差不能超过1，如果插入或者删...
AVL树 平衡二叉树是一颗自平衡的搜索二叉树，树内任何节点的左右子树的高度差不超过1。 非AVL树的几种模型 右旋...
Huffman 树 概念 树的构造 Huffman 源码 AVL 树(平衡二叉树) 概念 平衡因子 二叉树上节点的...
AVL树（平衡二叉树） AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，...
平衡二叉树的基本操作 1066 Root of AVL Tree
本文标题：平衡二叉树(AVL树)
本文链接：https://www.haomeiwen.com/subject/jrvdkltx.html
网友评论