package com.leon.cc;
import com.leon.util.Stack;
/**
* @author : Leon
* @since : 2013-10-9
* @see :
*/
public class Tree {
Node root = new Node();
public void insert(String str) {
Node node = search_node(root, str);
node.insert(str);
while (need_split(node)) {
if (node == root) {
node = node.split();
root = node;
}
else {
node = node.split();
}
}
}
public void delete(String str) {
Node node = contain(str);
Node leaf = null;
if (!node.is_leaf()) {
leaf = tree_successor(node, str);
int index = node.index_item(str);
String temp = node.values[index];
node.values[index] = leaf.values[0];
leaf.values[0] = temp;
}
else {
leaf = node;
}
leaf.delete(str);
if (leaf.item_size == 0) {
fix(leaf);
}
}
private void fix(Node n) {
if (n.parent == null) {
root = n.disConnect(0);
}
else {
Node p = n.parent;
int[] ary = new int[3];
int index = p.index_child(n);
if (has_2item_sibling(n, ary)) {
if (p.item_size == 2) {
if (index == 0) {
if (ary[1] == 2) {
leftRotate(0, n);
}
else {
leftRotate(0, n);
leftRotate(1, n.parent.childs[1]);
}
}
else if (index == 1) {
if (ary[2] == 2) {
leftRotate(1, n);
}
else {
rightRotate(1, n);
}
}
else {
if (ary[1] == 2) {
rightRotate(2, n);
}
else {
rightRotate(2, n);
rightRotate(1, n.parent.childs[1]);
}
}
}
else {
if (index == 0) {
leftRotate(0, n);
}
else {
rightRotate(1, n);
}
}
}
else {
if (p.item_size == 2) {
if (index == 0) {
mergeRight(0, n);
}
else if (index == 1) {
mergeLeft(1, n);
}
else {
mergeLeft(2, n);
}
}
else {
if (index == 0) {
mergeRight(0, n);
}
else {
mergeLeft(1, n);
}
fix(p);
}
}
}
}
private void mergeLeft(int i, Node n) {
Node child = null;
Node p = n.parent;
if (!n.is_leaf()) {
child = n.childs[0];
n.delete_child(0);
}
p.delete_child(i);
if (i == 1) {
p.childs[0].insert(p.values[0]);
p.delete(p.values[0]);
if (child != null) {
p.childs[0].insert_child(2, child);
}
}
else {
int sibling_size = p.item_size;
p.childs[1].insert(p.values[sibling_size - 1]);
p.delete(p.values[sibling_size - 1]);
if (child != null) {
p.childs[1].insert_child(2, child);
}
}
}
private void mergeRight(int i, Node n) {
Node child = null;
Node p = n.parent;
if (!n.is_leaf()) {
child = n.childs[0];
n.delete_child(0);
}
p.delete_child(0);
p.childs[0].insert(p.values[0]);
p.delete(p.values[0]);
if (child != null) {
p.childs[0].insert_child(0, child);
}
}
private boolean has_2item_sibling(Node n, int[] ary) {
Node p = n.parent;
ary[0] = p.childs[0].item_size;
ary[1] = p.childs[1].item_size;
if (p.item_size == 2) {
ary[2] = p.childs[2].item_size;
}
for (int i = 0; i < ary.length; i++) {
if (ary[i] == 2) {
return true;
}
}
return false;
}
private void leftRotate(int index, Node n) {
if (index == 0) {
n.insert(n.parent.values[0]);
n.parent.delete(n.parent.values[0]);
n.parent.insert(n.parent.childs[1].values[0]);
n.parent.childs[1].delete(n.parent.childs[1].values[0]);
if (!n.is_leaf()) {
Node node = n.parent.childs[1].delete_child(0);
n.insert_child(1, node);
}
}
else {
n.insert(n.parent.values[1]);
n.parent.delete(n.parent.values[1]);
n.parent.insert(n.parent.childs[2].values[0]);
n.parent.childs[2].delete(n.parent.childs[2].values[0]);
if (!n.is_leaf()) {
Node node = n.parent.childs[2].delete_child(0);
n.insert_child(1, node);
}
}
}
private void rightRotate(int index, Node n) {
if (index == 2) {
n.insert(n.parent.values[1]);
n.parent.delete(n.parent.values[1]);
int sibling_size = n.parent.childs[1].item_size;
n.parent.insert(n.parent.childs[1].values[sibling_size - 1]);
n.parent.childs[1].delete(n.parent.childs[1].values[sibling_size - 1]);
if (!n.is_leaf()) {
Node node = n.parent.childs[1].delete_child(sibling_size);
n.insert_child(0, node);
}
}
else {
n.insert(n.parent.values[0]);
n.parent.delete(n.parent.values[0]);
int sibling_size = n.parent.childs[0].item_size;
n.parent.insert(n.parent.childs[0].values[sibling_size - 1]);
n.parent.childs[0].delete(n.parent.childs[0].values[sibling_size - 1]);
if (!n.is_leaf()) {
Node node = n.parent.childs[0].delete_child(sibling_size);
n.insert_child(0, node);
}
}
}
public Node tree_successor(Node node, String str) {
if (!node.is_leaf()) {
int index = node.index_item(str);
Node child = node.childs[index + 1];
return tree_mins(child);
}
return node;
}
private Node tree_mins(Node child) {
Node temp = child;
while (!temp.is_leaf()) {
temp = temp.childs[0];
}
return temp;
}
public Node contain(String str) {
Node current = root;
while (!current.contain(str)) {
if (current.item_size == 2) {
String small = current.values[0];
String large = current.values[1];
if (str.compareTo(small) < 0) {
current = current.childs[0];
}
else if (str.compareTo(small) >= 0 && str.compareTo(large) <= 0) {
current = current.childs[1];
}
else {
current = current.childs[2];
}
}
else {
String small = current.values[0];
if (str.compareTo(small) < 0) {
current = current.childs[0];
}
else {
current = current.childs[1];
}
}
}
return current;
}
public boolean need_split(Node node) {
return node.item_size > 2 ? true : false;
}
public Node search_node(Node node, String str) {
if (is_leaf(node)) {
return node;
}
else {
if (node.item_size == 2) {
String small = node.values[0];
String large = node.values[1];
if (str.compareTo(small) < 0) {
Node next = create_node(node, 0);
return search_node(next, str);
}
else if (str.compareTo(small) >= 0 && str.compareTo(large) <= 0) {
Node next = create_node(node, 1);
return search_node(next, str);
}
else {
Node next = create_node(node, 2);
return search_node(next, str);
}
}
else {
String small = node.values[0];
if (str.compareTo(small) < 0) {
Node next = create_node(node, 0);
return search_node(next, str);
}
else {
Node next = create_node(node, 1);
return search_node(next, str);
}
}
}
}
private Node create_node(Node node, int i) {
Node child = node.childs[i];
if (child == null) {
child = new Node();
node.childs[i] = child;
child.parent = node;
}
return child;
}
public boolean is_leaf(Node node) {
return node.childs[0] == null;
}
public static void main(String[] args) {
Tree t = new Tree();
String[] str = new String[] { "horse", "cow", "pig", "seal", "rat", "dog", "goat", "elephant", "fish",
"rooster", "zebra", "roach", "cat", "hen", "llama", "aardvark", "hog", "donkey", "rhino", "hippo",
"tiger", "lamb", "lion", "leopard", "lynx", "kitty", "ant", "ape", "animal" };
for (int i = 0; i < str.length; i++) {
t.insert(str[i]);
}
t.delete("animal");
t.delete("aardvark");
t.delete("cat");
t.delete("ape");
t.delete("donkey");
t.delete("ant");
t.delete("hog");
t.delete("hen");
t.delete("fish");
t.delete("goat");
t.delete("hippo");
t.delete("kitty");
t.delete("cow");
t.delete("dog");
t.delete("elephant");
t.delete("tiger");
t.delete("zebra");
t.delete("horse");
t.delete("rat");
t.delete("rhino");
t.delete("pig");
t.delete("seal");
t.delete("lynx");
t.delete("roach");
t.delete("lion");
t.delete("llama");
t.delete("lamb");
t.delete("rooster");
t.delete("leopard");
String rs = t.toString();
System.out.println(rs);
}
public String toString() {
if (root == null) {
return null;
}
StringBuilder sb = new StringBuilder();
sb.append("digraph g {\n");
sb.append("\tnode[shape = record, width = .1, height = .1];\n");
Stack<Node> stack = new Stack<Node>();
int k = 0;
Stack<Integer> k_stack = new Stack<Integer>();
stack.push(root);
k_stack.push(k);
sb.append("\tnode" + k + "[label = \"{<n> " + root.getName() + " }\", color = lightgray, style = filled];\n");
while (!stack.is_empty()) {
Node parent = stack.pop();
String parentNode = "node" + k_stack.pop();
for (int i = 0; i < parent.childs.length; i++) {
if (parent.childs[i] != null) {
String childNode = "node" + (++k);
sb.append("\t" + childNode + "[label = \"{<n> " + parent.childs[i].getName()
+ " }\", color = lightgray, style = filled];\n");
sb.append("\t" + parentNode + ":n->" + childNode + ":n;\n");
stack.push(parent.childs[i]);
k_stack.push(k);
}
}
}
sb.append("}\n");
return sb.toString();
}
}
class Node {
String[] values = new String[3];
int item_size;
Node[] childs = new Node[4];
Node parent;
public Node(String str) {
values[0] = str;
item_size++;
}
public String getName() {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < item_size; i++) {
sb.append(values[i] + " ");
}
return sb.toString();
}
public Node() {
}
public boolean contain(String str) {
for (int i = 0; i < item_size; i++) {
if (values[i].equals(str)) {
return true;
}
}
return false;
}
public int insert(String str) {
int pos = item_size;
for (int i = item_size - 1; i >= 0; i--) {
if (values[i].compareTo(str) > 0) {
values[i + 1] = values[i];
pos = i;
}
}
values[pos] = str;
item_size++;
return pos;
}
public void delete(String str) {
int index = index_item(str);
for (int i = index; i < item_size; i++) {
values[i] = values[i + 1];
}
item_size--;
}
public void insert_child(int index, Node node) {
for (int i = childs.length - 2; i >= index; i--) {
childs[i + 1] = childs[i];
}
childs[index] = node;
childs[index].parent = this;
}
public Node delete_child(int index) {
Node node = childs[index];
for (int i = index; i < childs.length - 1; i++) {
childs[i] = childs[i + 1];
}
node.parent = null;
return node;
}
public boolean is_leaf() {
return childs[0] == null;
}
public int index_child(Node node) {
for (int i = 0; i < childs.length; i++) {
if (childs[i].equals(node)) {
return i;
}
}
return -1;
}
public int index_item(String str) {
for (int i = 0; i < item_size; i++) {
if (values[i].equals(str)) {
return i;
}
}
return -1;
}
public Node disConnect(int index) {
Node result = childs[index];
if (result != null) result.parent = null;
childs[index] = null;
return result;
}
public void connect(int index, Node child) {
childs[index] = child;
if (child != null) child.parent = this;
}
public Node split() {
Node left = this;
String middle = values[1];
Node right = new Node(values[2]);
left.values[1] = null;
left.values[2] = null;
left.item_size = 1;
if (parent == null) {
parent = new Node(middle);
parent.connect(0, left);
parent.connect(1, right);
}
else {
int index = parent.insert(middle);
parent.insert_child(index + 1, right);
}
if (!is_leaf()) {
Node child1 = disConnect(2);
Node child2 = disConnect(3);
right.connect(0, child1);
right.connect(1, child2);
}
return parent;
}
}
分享到:
相关推荐
算法导论 2-3tree 课堂资料 new york University
下载后ubuntu 终端安装命令:dpkg -i device-tree-compiler_1.4.7-3ubuntu2_amd64.deb 直接安装,外网下载太慢上传备用
ReactD3树 React D3 Tree是一个组件,可让您利用的tree布局,以最小的设置将层次结构数据(例如,族谱,组织结构图,文件目录)表示为交互式树形图。 是否想了解v2中的更改? 查看v2发行说明。 寻找v1? 请...
device-tree-xlnx-xilinx-v2018.3
更新日志 更新时间2020/12/02修复初步修改数据不渲染问题对应版本:vue-okr-tree@1.0.5 ...基于Vue 2的组织架构树组件 安装 # use npm npm i vue-okr-tree # use yarn yarn add vue-okr-tree 快速开始 import { Vu
2-3 tree 298 2-3-4 tree 299 Queaps 301 Fusion tree 305 Bx-tree 309 Heaps 312 Heap 312 Binary heap 315 Binomial heap 321 Fibonacci heap 326 2-3 heap 331 Pairing heap 331 Beap 334 Leftist tree 335 Skew ...
2-3-树 2-3个树的数据结构复杂度O(log(n))。 希望这对其他人有帮助。
主要介绍了vue el-tree 默认展开第一个节点的实现代码,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下
给你inorder的栈操作步骤,让你写出postorder后的序列。 http://blog.csdn.net/xkzju2010/article/details/46325457
zm-tree-org介绍一个简易版组织架构图,组件依赖于vue-org-tree, 在此基础上将部分源代码进行优化修改。可鼠标拖动拖拽,以及鼠标滚轮缩放,并且支持拖动节点改变树结构。安装npm install zm-tree-org --save# or ...
Select2-to-Tree是对Select2(一个流行的选择框库)的扩展: : 。 尽管Select2非常通用,但它仅支持单层嵌套。 参见 : 由于创建嵌套选项时Select2会退回到,因此仅支持单级嵌套。 不能保证任何其他级别的嵌套都...
红黑树的发明者关于红黑树的演化过程的介绍,是最好的理解红黑树的资料。
device-tree-xlnx-xilinx-v2016.3.zip SDK --> Xilinx tools --> Repositories --> 添加device-tree-xlnx。
2—3树的建立,插入,删除,清空等功能的实现
安装使用npm安装插件: npm install --save vue-json-tree-view 然后,在您的Application JavaScript中,添加: import TreeView from "vue-json-tree-view"Vue . use ( TreeView ) 做完了用法将tree-view元素放到...
2、勾选全选,则资源全部添加到右侧,左侧的则显示为空 3、保存后点击编辑,左侧显示未分配的资源,右侧显示已分配的资源 4、后台给到的数据是:所有的资源(多维数组)和已分配的资源(一维数组,包含(半勾选)...
{name: '上海分部', id: 2, pid: 0, children: []}, {name: '成都分部', id: 3, pid: 0}, {name: '广州分部', id: 4, pid: 0}, {name: '沈阳分部', id: 5, pid: 0}, {name: '张三', id: 6, pid: 0, isLeaf: ...
React虚拟粘性树 ... root : { name : 'Root' , children : [ 'child1' , 'child2' , 'child3' ] , depth : 0 } , child1 : { name : 'Child 1' , children : [ 'child4' ] , depth : 1 } , child2 : { n
AutoJs源码-AvlTree。本资源购买前提醒:本源码都是实际autojs项目模板,安装好autojs直接运行即可打开。1、支持低版本autojs。2、资源仅供学习与参考,请勿用于商业用途,否则产生的一切后果将由您自己承担!。3、...
|演示页面演示Gif使用技术画布版本结合使用D3.js和Canvas可以更有效地绘制organizationChart。 使用unique-color方式... component ( 'vue-tree' , VueTree ) 3.使用组件3.1基本用法见代码< template> < div clas