多叉树:2-3-4树
平衡树多叉树,每个节点最多有4个子节点和3个数据项,2,3,4的含义是指一个节点可能含有的子节点的个数,效率比红黑树稍差.一般不允许出现重复关键字值.2-3-4树有以下特征:
1、有一个数据项的节点总是有2个子节点(称为2-节点)
2、有两个数据项的节点总是有3个子节点(称为3-节点)
3、有三个数据项的节点总是有4个子节点(称为4-节点)
简单的说,非叶节点的子节点树总是比它含有的数据项多1,叶节点可能含有一个,两个或三个数据项.空叶节点不存在.2-3-4树的规则如下:
1、第一个子节点的关键字值小于父节点第一个数据项
2、第二个子节点的关键字值小于父节点第二个数据项并大于第一个数据项
3、第三个子节点的关键字值小于父节点第三个数据项并大于第二个数据项
4、最后一个节点的关键字值大于父节点第三个数据项
插入操作:
查找时没有碰到满节点时,插入很简单.找到合适的叶节点后,只要把新数据项插入进去就可以了.可能会涉及到在一个节点中移动一个或两个其他的数据项.如果节点已经满了,插入就变得复杂了.发生这种情况时,节点必须分裂以保持树的平衡.把要分裂节点中的数据项设为A,B,C
1、创建一个新的节点,他是要分裂节点的兄弟节点,在要分裂节点的右边.
2、数据项C移动到新节点中.
3、数据项B移到要分裂节点的父节点中(如果要分裂的节点是根节点,就再创建一个新节点指 向根,并将要分裂的节点连接上去).
4、要分裂节点的最右边的两个子节点连接到新的兄弟节上
删除操作:
还是很蛋疼的操作,依然建议打作废标记...
最后,是关于红黑树的,虽然两种树看上去不一样,但是在数学上确实属于同构的,2-3-4树也能转化为一颗红黑树.
2-3-4树转化为红黑树规则:
1、把每个2-节点转化为红黑树的黑色节点.
2、把每个3-节点转化成一个子节点和一个父节点，子节点有两个自己的子节点，父节点 有另一个子节点，子节点涂成红色，父节点涂成黑色.
3、把每个4-节点转化成一个父节点,两个子节点和四个孙子节点,子节点涂成红色,父节点涂成黑色.
tree代码:
public class Item { private int key; private Object value; private boolean valid; public Item(){}; public Item(int key,Object value){ this.key = key; this.value = value; this.valid = true; } public int getKey() { return key; } public Object getValue() { return value; } public void setValue(Object value) { this.value = value; } public boolean isValid() { return valid; } public void setValid(boolean valid) { this.valid = valid; }}