二叉搜索树
二叉搜索树
特点
基本的数据结构不能高效且兼顾静态查找与动态修改,而二叉搜索树则可以实现
查找
//查找算法
public BinNode<Integer> search(Integer e){
return searchIn(_root,e,_hot = null);
}
//hot查找成功时,指向数字对应的节点;
//查找失败时,指向空节点
//引入哨兵,查找成功与否都指向命中节点,只不过失败时是假想存在,而—_hot总是指向名字节点的父亲
protected BinNode<Integer> searchIn(BinNode<Integer> v,Integer e,BinNode<Integer> hot){
if (v == null ||((int)e == (int)v.data)) return v;
hot = v;
return searchIn((((int)e < (int)v.data) ? v.lc : v.rc),e,hot);
}
插入
//插入算法
public BinNode<Integer> insert(Integer e){
BinNode<Integer> x = search(e);
if (x == null){
x = new BinNode<Integer>(e,_hot);
_size++;
updateHeightAbove(x);
}
return x;
}
插入
//删除算法
public Boolean remove(Integer e){
BinNode<Integer> x = search(e);
if (x == null) return false;
removeAt(x,_hot);
_size--;
updateHeightAbove(_hot);
return true;
}
//情况一,单节点的情况
public BinNode<Integer> removeAt(BinNode<Integer> x,BinNode<Integer> hot){
BinNode<Integer> w = x;
BinNode<Integer> succ = null;
if (!(HasLChild(x))) succ = x = x.rc; else if (!(HasRChild(x))) succ = x = x.lc; else {
w = w.succ();
swap(x.data,w.data);
BinNode<Integer> u = w.parent;
if (u == x){
u.rc= succ = w.rc;
} else {
u.lc = succ = w.rc;
}
}
hot = w.parent;
if (succ != null) succ.parent = hot;
return succ;
}
//情况二、双节点的情况
private void swap(Integer a,Integer b){
Integer c = a;
a = b;
b = c;
}
全部
package com.atguigu.self;
/**
* @anthor shkstart
* @create 2020-08-07 8:29
*/
public class BST<Integer> extends BinTree<Integer>{
public BinNode<Integer> _hot;
//查找算法
public BinNode<Integer> search(Integer e){
return searchIn(_root,e,_hot = null);
}
//hot查找成功时,指向数字对应的节点;
//查找失败时,指向空节点
//引入哨兵,查找成功与否都指向命中节点,只不过失败时是假想存在,而—_hot总是指向名字节点的父亲
protected BinNode<Integer> searchIn(BinNode<Integer> v,Integer e,BinNode<Integer> hot){
if (v == null ||((int)e == (int)v.data)) return v;
hot = v;
return searchIn((((int)e < (int)v.data) ? v.lc : v.rc),e,hot);
}
//插入算法
public BinNode<Integer> insert(Integer e){
BinNode<Integer> x = search(e);
if (x == null){
x = new BinNode<Integer>(e,_hot);
_size++;
updateHeightAbove(x);
}
return x;
}
//删除算法
public Boolean remove(Integer e){
BinNode<Integer> x = search(e);
if (x == null) return false;
removeAt(x,_hot);
_size--;
updateHeightAbove(_hot);
return true;
}
//情况一,单节点的情况
public BinNode<Integer> removeAt(BinNode<Integer> x,BinNode<Integer> hot){
BinNode<Integer> w = x;
BinNode<Integer> succ = null;
if (!(HasLChild(x))) succ = x = x.rc; else if (!(HasRChild(x))) succ = x = x.lc; else {
w = w.succ();
swap(x.data,w.data);
BinNode<Integer> u = w.parent;
if (u == x){
u.rc= succ = w.rc;
} else {
u.lc = succ = w.rc;
}
}
hot = w.parent;
if (succ != null) succ.parent = hot;
return succ;
}
//情况二、双节点的情况
private void swap(Integer a,Integer b){
Integer c = a;
a = b;
b = c;
}
//节点旋转变化算法
protected BinNode<Integer> rotateAt(BinNode<Integer> v){
BinNode<Integer> p = v.parent;
BinNode<Integer> g = p.parent;
//视v、p、g相对位置分为四种情况
if (IsLChild(p)){
if (IsLChild(v)){
p.parent = g.parent;
return connect34( v, p, g, v.lc, v.rc, p.rc, g.rc );
} else {
v.parent = g.parent;
return connect34( p, v, g, p.lc, v.lc, v.rc, g.rc );
}
} else {
if (IsRChild(v)){
p.parent = g.parent;
return connect34( g, p, v, g.lc, p.lc, v.lc, v.rc );
} else {
v.parent = g.parent;
return connect34( g, v, p, g.lc, v.lc, v.rc, p.rc );
}
}
}
//按照‘3+4’结构链接3个节点及四颗子树,返回重组之后的局部子树根节点位置
//子树根节点与上层节点之间的双向联接,均须由上层调用者完成
protected BinNode<Integer> connect34(BinNode<Integer> a,BinNode<Integer> b,BinNode<Integer> c,BinNode<Integer> T0,BinNode<Integer> T1,BinNode<Integer> T2,BinNode<Integer> T3){
a.lc = T0;
if (T0 != null) T0.parent = a;
a.rc = T1;
if (T1 != null){
T1.parent = a;
updateHeight(a);
}
c.lc = T2;
if (T0 != null) T2.parent = c;
c.rc = T1;
if (T3 != null){
T3.parent = c;
updateHeight(c);
}
b.lc = a;
a.parent = b;
b.rc = c;
c.parent = b;
updateHeight(b);
return b;
}
//在左右孩子中取更高者
protected BinNode<Integer> tallerChild(BinNode<Integer> x){
if (stature(x.lc) > stature(x.rc)){
return x.lc;
} else if(stature(x.lc) < stature(x.rc)){
return x.rc;
} else{
return IsLChild(x) ? x.lc : x.rc;
}
}
}
平衡二叉搜索树
概念
实现
插入
public BinNode<Integer> insert(Integer e){
BinNode<Integer> x = search(e);
if (x != null) return x;
BinNode<Integer> xx = new BinNode<Integer>(e,_hot);
x = xx;
_size++;
for (BinNode<Integer> g = _hot;g != null;g = g.parent){
if (!AvlBalanced(g)){
if (IsRoot(g)){
_root = rotateAt(tallerChild(tallerChild(g)));
} else {
if (IsLChild(g)){
g.parent.lc = rotateAt(tallerChild(tallerChild(g)));
} else {
g.parent.rc = rotateAt(tallerChild(tallerChild(g)));
}
}
break;
} else {
updateHeight(g);
}
}
return xx;
}
删除
public Boolean remove(Integer e){
BinNode<Integer> x = search(e);
if (x ==null) return false;
removeAt(x,_hot);
_size--;
for (BinNode<Integer> g = _hot; g != null; g = g.parent){
if (! AvlBalanced(g)){
if (IsRoot(g)){
g = _root = rotateAt(tallerChild(tallerChild(g)));
} else {
if (IsLChild(g)){
g = g.parent.lc = rotateAt(tallerChild(tallerChild(g)));
} else {
g = g.parent.rc = rotateAt(tallerChild(tallerChild(g)));
}
}
}
updateHeight(g);
}
return true;
}
必要方法
//按照‘3+4’结构链接3个节点及四颗子树,返回重组之后的局部子树根节点位置
//子树根节点与上层节点之间的双向联接,均须由上层调用者完成
protected BinNode<Integer> connect34(BinNode<Integer> a,BinNode<Integer> b,BinNode<Integer> c,BinNode<Integer> T0,BinNode<Integer> T1,BinNode<Integer> T2,BinNode<Integer> T3){
a.lc = T0;
if (T0 != null) T0.parent = a;
a.rc = T1;
if (T1 != null){
T1.parent = a;
updateHeight(a);
}
c.lc = T2;
if (T0 != null) T2.parent = c;
c.rc = T1;
if (T3 != null){
T3.parent = c;
updateHeight(c);
}
b.lc = a;
a.parent = b;
b.rc = c;
c.parent = b;
updateHeight(b);
return b;
}
//在左右孩子中取更高者
protected BinNode<Integer> tallerChild(BinNode<Integer> x){
if (stature(x.lc) > stature(x.rc)){
return x.lc;
} else if(stature(x.lc) < stature(x.rc)){
return x.rc;
} else{
return IsLChild(x) ? x.lc : x.rc;
}
}
//节点旋转变化算法
protected BinNode<Integer> rotateAt(BinNode<Integer> v){
BinNode<Integer> p = v.parent;
BinNode<Integer> g = p.parent;
//视v、p、g相对位置分为四种情况
if (IsLChild(p)){
if (IsLChild(v)){
p.parent = g.parent;
return connect34( v, p, g, v.lc, v.rc, p.rc, g.rc );
} else {
v.parent = g.parent;
return connect34( p, v, g, p.lc, v.lc, v.rc, g.rc );
}
} else {
if (IsRChild(v)){
p.parent = g.parent;
return connect34( g, p, v, g.lc, p.lc, v.lc, v.rc );
} else {
v.parent = g.parent;
return connect34( g, v, p, g.lc, v.lc, v.rc, p.rc );
}
}
}
全部
package com.atguigu.self;
/**
* @anthor shkstart
* @create 2020-08-07 11:01
*/
public class AVL<Integer> extends BST<Integer>{
public BinNode<Integer> insert(Integer e){
BinNode<Integer> x = search(e);
if (x != null) return x;
BinNode<Integer> xx = new BinNode<Integer>(e,_hot);
x = xx;
_size++;
for (BinNode<Integer> g = _hot;g != null;g = g.parent){
if (!AvlBalanced(g)){
if (IsRoot(g)){
_root = rotateAt(tallerChild(tallerChild(g)));
} else {
if (IsLChild(g)){
g.parent.lc = rotateAt(tallerChild(tallerChild(g)));
} else {
g.parent.rc = rotateAt(tallerChild(tallerChild(g)));
}
}
break;
} else {
updateHeight(g);
}
}
return xx;
}
public Boolean remove(Integer e){
BinNode<Integer> x = search(e);
if (x ==null) return false;
removeAt(x,_hot);
_size--;
for (BinNode<Integer> g = _hot; g != null; g = g.parent){
if (! AvlBalanced(g)){
if (IsRoot(g)){
g = _root = rotateAt(tallerChild(tallerChild(g)));
} else {
if (IsLChild(g)){
g = g.parent.lc = rotateAt(tallerChild(tallerChild(g)));
} else {
g = g.parent.rc = rotateAt(tallerChild(tallerChild(g)));
}
}
}
updateHeight(g);
}
return true;
}
public Boolean Balanced(BinNode<Integer> x){
return stature(x.lc) == stature(x.rc);
}
public int BalFac(BinNode<Integer> x){
return stature(x.lc) - stature(x.rc);
}
public Boolean AvlBalanced(BinNode<Integer> x){
return ((-2 < BalFac(x)) && ( BalFac(x) < 2));
}
}