引入
如果二叉排序树用不好,就会退化成斜树,实现算法性能退化成了 O(n)
定义
1.首先是二叉排序树
2.平衡二叉树要求每个节点的左子树和右子树的高度差至多等于 1,这个高度(深度)差的值叫做平衡因子 BF,也就是说 BF 的值不能大于1,否则就不是平衡二叉树。
实现原理
和二叉排序树差不多,只不过每次插入元素后,需要检查树的平衡性,如果平衡性遭到破坏,则需要通过左旋/右旋来调整平衡性。
参考网站
https://xueyuanjun.com/post/21006
如果二叉排序树用不好,就会退化成斜树,实现算法性能退化成了 O(n)
1.首先是二叉排序树
2.平衡二叉树要求每个节点的左子树和右子树的高度差至多等于 1,这个高度(深度)差的值叫做平衡因子 BF,也就是说 BF 的值不能大于1,否则就不是平衡二叉树。
和二叉排序树差不多,只不过每次插入元素后,需要检查树的平衡性,如果平衡性遭到破坏,则需要通过左旋/右旋来调整平衡性。
https://xueyuanjun.com/post/21006