二叉树和平衡二叉树的思考与实现
我们先来看一下百度百科中对树的定义:
树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构
成的。集合中的元素称为树的结点,所定义的关系称为父子关系。父子关系在树的结点
之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位,这个结点称
为该树的根结点,或称为树根。
1.每个结点有零个或多个子结点
2.没有父结点的结点称为根结点
3.每一个非根结点有且只有一个父结点
4.除了根结点外,每个子结点可以分为多个不相交的子树
树的种类
我们现在经常接触到的树种类是:二叉树、平衡二叉树、红黑树等
特点:二叉树在树的特点上拥有了其节点顺序是五序的。
二叉树实际上是最为简单的树,在实现时只需要去考虑节点的顺序问题,所以我们在进行插入操作时只需要去考虑节点的大小就是可以的。
1.肯定需要一个Node节点,来存储节点数据。
public static class Node<K, V> {
Node<K, V> parent;//父节点
Node<K, V> left;//左子节点
Node<K, V> right;//右子节点
K key;
V value;
Node(K key, V value, Node<K, V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
2.增加一个root节点、一个被volatile修饰的int参数来作为节点数量
3.首先实现添加操作,在实现删除操作时不需要考虑由于树的最低高度和最大高度而
导致要调整树的问题,只需要去考虑插入时如何放置节点的问题
4.然后实现查询操作,查询操作只需要去判断value的大小然后决定是向左子树/右子
树遍历
5.最后实现删除操作,首先要查询出要删除的node节点,然后就是进行节点的操作,
--如果其left 和 right 节点为null,则将left 和 right 节点中含有node节
点的父节点中指向为null
--如果其left 节点不为null,则将最小的left 节点移到要删除的node节点的位置
,node节点的left 和right节点指向为null,等待GC回收.
--如果left节点含有right节点,则把right节点移到要删除的node节点的位置,
node节点的left 和right节点指向为null,等待GC回收.
将最小的节点的父节点的含有自节点指向设为null,防止出现死循环
平衡二叉树其要保证任意节点的子树的高度差都小于等于1。
实现思路
1.需要一个Node节点,来存储数据
public static class Node<V> {
// root节点的level为1,其子节点的level递增
int level;//层级
Node<V> parent;//父节点
Node<V> left;//左子节点
Node<V> right;//右子节点
V value;
Node(V value, Node<V> parent, int level) {
this.value = value;
this.parent = parent;
this.level = level;
}
}
2.先来实现添加操作,因为在添加的操作中我们需要考虑通过自旋来保证平衡二叉树
的特性。
可以通过判断我们添加的节点是属于右子树还是左子树的区域,来确定如果发生失衡,
其失衡的区域。因为在添加数据时会有可能出现是左子树失衡,但是其失衡节点是在
右节点的情况,针对这种情况就是需要做特殊处理的。当然,右子树也一样。
·先来说下左子树和右子树普通失衡时的右旋和左旋是怎么处理?
通过for循环来实现
1.尝试将parent作为失衡节点,用来右旋
2.如果右/左旋结束之后仍然失衡,则将parent节点的父节点作为失衡节点,用来右旋
3.如果仍然失衡则将parent节点的祖父节点作为失衡节点,用来右/左旋
4.获取parent节点时依次取改节点的父节点
5.调整节点时要调整节点的level层级
·在来说下特殊情况的处理特殊处理?
在左子树特殊失衡的情况中,通过for循环来解决,首先尝试将parent节点作为失
衡节点来进行左旋处理,然后判断parent节点的左右子节点的大小,将左右子节点
中值大的节点与parent节点交换位置
在右子树特殊失衡的情况中,通过for循环来解决,首先尝试将parent节点作为失
衡节点来进行右旋处理,然后判断parent节点的左右子节点的大小,将左右子节点
中值大的节点与parent节点交换位置
平衡二叉树的获取、移除和设置操作这里就不在进行分享,因为在二叉树的实现过程中,最为困难的还是怎么处理树的失衡比较困难,所以只是主要分享了一下处理思路。