前文介绍了 ， 二叉树、二叉排序树 ， 需要了解的不妨关注下小JIA 。
文章插图
【算法--平衡二叉树AVL原理分析以及代码实现】
AVL是一种高度平衡的二叉排序树 。对于任意节点左子树与右子树高度差不超过1 ， AVL的高度与节点数量为O（logn）关系 。平衡因子等于左子树高度减去右子树高度 。AVL所有节点的平衡因子只可能是-1、0、1 。因此当添加元素或删除元素时有可能会破会这种平衡 ， 所以需要维护 。失去平衡主要有四种情况 ， 分别为LL、LR、RR和RL 。
AVL 的节点定义public class AVLTreeNode<T extends Comparable<T>> { private T key; //关键字(键值) private int height; //高度 private AVLTreeNode<T> left; //左孩子 private AVLTreeNode<T> right; //右孩子 public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) { this.key = key; this.left = left; this.right = right; this.height = 0; } ...... }
推荐阅读
- 比特币用到的算法知识
- 面试官：手撕十大排序算法，你会几种？
- 解读递归算法原理和效率
- 百度升级烽火算法2.0，提升打击网站劫持覆盖范围
- 喝茶的智者必须了解平衡的方法
- 浅谈Java并发编程之CAS算法策略
- 「C语言」常用算法
- 神奇的暴雪哈希算法
- 建议收藏 程序员都应该知道的算法复杂度速查表
- 图解各路分布式ID生成算法