- 浏览: 120801 次
- 性别:
- 来自: 上海
最新评论
2-3-4 平衡树是一种搜索树。每个节点可能会有2,3,4个子节点,对应可能会有1,2,3个数据。子节点数=数据数 + 1,不可能有空节点。
插入数据时,数据均插入叶子节点,树在向下遍历以得到恰当的叶子节点时,每遇到满的节点,则进行节点分裂,当分裂向上累积致根节点位置,根节点分裂,所有叶子节点的层高都增加一层,以此原理来保证树的平衡。
此树没有实现删除数据的算法,如果需要,可考虑将数据标志为作废的方式,以避免真正的删除时的复杂。
插入的数据为了简便起见,假设均为Integer,且不会重复。
方法ordinal是升序打印,为的是测试。
Tree.main 函数提供一个简短的测试。
Node类为辅助类,管理单个节点的操作。
Tree为2-3-4树,管理节点与节点之间的操作。其他的平衡数可以参见红黑树
关于简单的二叉搜索树,请参见(Tree )。
class Node { private Integer[] values = new Integer[3]; //存放数据 private Node[] children = new Node[4]; //存放子节点引用 private int size; //当前有效数据数量 private Node parent; //当前节点的父节点 Node() {} Node(Integer i) { values[0] = i; size = 1; } int insert(Integer value) { //将数据插入有序数组 assert size < values.length; int pos = size; while(pos > 0 && values[pos - 1] > value) { values[pos] = values[pos - 1]; pos--; } values[pos] = value; size ++; return pos; } Node getChildByValue(Integer value) { //根据给定数据的关键字,寻找恰当的子节点 for(int i=0; i<size; i++) { if(values[i] > value) return children[i]; } return children[size]; } //根据给定子节点的索引值,得到对应的子节点 Node getChildByIndex(int index) { return children[index]; } int find(Integer value) { for(int i=0; i<size; i++) { if(values[i].equals(value)) return i; } return -1; } Integer removeMax() { return values[--size]; } //删除当前节点内最大的数据,并返回之 //根据给定子节点的索引值,删除与其的对应节点之间的父子关系 Node removeChild(int index) { Node result = children[index]; if(result != null)result.parent = null; children[index] = null; return result; } //在当前节点中,在指定的索引值之后插入相应的子节点,之后的原有的子节点全部向后平移 void insertChild(int index, Node child) { for(int i=size; i>index + 1; i--) children[i] = children[i-1]; children[index+1] = child; if(child != null)child.parent = this; } //在当前节点中,在指定的索引值的位置置入相应子节点 void setChild(int index, Node child) { children[index] = child; if(child != null) child.parent = this; } int size() { return size; } boolean isFull() { return size == values.length; } boolean isLeaf() { return children[0] == null; } Node getParent() { return parent; } Integer getValue(int index) { return values[index]; } }
class Tree { private Node root = new Node(); //根节点 public void insert(Integer value) { //将数据插入树中 Node current = root; //从根向下开始寻找恰当的叶子节点 while(!current.isLeaf()) { if(current.isFull()) current = split(current); //如果下行过程遇到满的节点,分裂之 current = current.getChildByValue(value); } if(current.isFull()) { //如果最终找到的叶子节点是满的,先分裂之 current = split(current); current = current.getChildByValue(value); } current.insert(value); //在叶子节点插入数据 } public boolean contains(Integer value) { Node current = root; while(!current.isLeaf()) { if(current.find(value) != -1) return true; current = current.getChildByValue(value); } return current.find(value) != -1; } public void ordinal() { //安升序排列输入树中所有的数据 ordinal(root); } private void ordinal(Node current) { for(int i=0; i<current.size(); i++) { if(!current.isLeaf()) ordinal(current.getChildByIndex(i)); System.out.println(current.getValue(i)); } if(!current.isLeaf()) ordinal(current.getChildByIndex(current.size())); } private Node split(Node current) { //分裂算法 Node parent = current.getParent(); //寻找当前节点的父节点 if(parent == null) parent = new Node(); //将当前节点拆分成左节点,右节点,中间的数据,其右节点是个新节点 Node nodeLeft = current; Node nodeRight = new Node(current.removeMax()); Integer middle = current.removeMax(); //断开当前节点中的第2,3子节点,并加入右字节中 Node child1 = nodeLeft.removeChild(2); Node child2 = nodeLeft.removeChild(3); nodeRight.setChild(0,child1); nodeRight.setChild(1,child2); int index = parent.insert(middle); //将中间的数据加入其父节点,并得到插入的位置 if(current == root) { //如果当前节点是根节点,则在新的父节点中加入左右节点 parent.setChild(0,nodeLeft); parent.setChild(1,nodeRight); root = parent; //重置根节点 } else parent.insertChild(index,nodeRight); //否则,在父节点中指定位置后插入右节点 return parent; //返回父节点 } public static void main(String[] args) { Tree t = new Tree(); t.insert(5); t.insert(6); t.insert(7); t.insert(8); t.insert(9); t.insert(10); t.insert(30); t.insert(50); t.insert(11); t.insert(17); t.insert(19); t.insert(54); t.insert(66); t.insert(72); t.insert(89); t.insert(92); t.insert(40); t.insert(28); t.insert(13); t.insert(14); t.insert(16); t.ordinal(); } }
评论
3 楼
arust
2008-05-28
学习一下
2 楼
dboylx
2008-04-29
支持~~~学习中,希望楼主继续~~
1 楼
桔红糕
2008-04-20
oh my god一看就觉得有点头晕!!
但是~~
我一定认真研读,有不明白的地方还请shen老师耐心教诲!
但是~~
我一定认真研读,有不明白的地方还请shen老师耐心教诲!
发表评论
-
Tree 红黑树
2008-05-01 17:23 2653红黑树是一种二叉平衡 ... -
Tree 2-3 平衡搜索树
2008-04-25 00:21 2300与2-3-4树 相似,2-3 平衡树是 ... -
Graph 图-邻接表法
2008-04-17 00:08 2966用邻接表法表示的双向图(改单向容易,只要修改connect,d ... -
Graph 图-邻接矩阵法
2008-04-16 22:56 3466用邻接矩阵法表示的双向图(改单向容易,只要修改connect, ... -
Heap 堆
2008-04-16 00:28 1431这里的堆不是java中内存分配的堆。只是一种数据结构。 堆是二 ... -
HashTable 基于链表地址法
2008-04-15 00:49 1624功能上于前面两个HashTable(-) ,HashTable ... -
HashTable 基于开放地址法(二)
2008-04-14 19:40 1979与前一个HashTable 基本相同(方法说明请参照它),只是 ... -
HashTable 基于开放地址法
2008-04-13 22:59 1548该HashTable基于定常数组的开放地址法,搜索时采用线性探 ... -
Tree 二叉搜索树
2008-04-11 00:03 1663每个节点最多两个子节点,其中左边节点的值小于该节点的值,右边节 ... -
PriorityQueue 优先级队列
2008-04-06 17:57 3412提供一个基于链表的优先级队列,为了简便,只存储整数,假设数值越 ... -
PriorityQueue 优先级队列
2008-04-06 16:57 4319提供一个基于定长数组的优先级队列,为了简便,只存储整数,假设数 ... -
Queue 队
2008-04-06 13:36 1501指定最大值的队,底层用数组实现构造函数:指定最大容量put:放 ... -
ArrayStack 栈
2008-04-06 12:00 1265用Array实现的栈结构,功能与LinkedStack一致编程 ... -
Array 可变长可变维数组
2008-04-06 11:25 1818一个可以变长,变维的数组(只可以变大),用来替代多维数组基本做 ... -
StackDLink 双向链表
2008-04-05 23:20 1121用LinkedStack实现的双向链表,功能与DLink一致就 ... -
LinkedList 列表
2008-04-05 19:16 1429列表的简单实现,只能存储非负整数List 也属于ADT(抽象数 ... -
ArrayList 列表
2008-04-05 19:01 1180列表的简单实现,只能存储非负整数List 也属于ADT(抽象数 ... -
LinkedQueue 队
2008-04-05 18:43 1827实现了队的最简单功能:先进现出队属于ADT(抽象数据类型),其 ... -
DLink 双向双端链表
2008-04-05 18:06 1463DLink 实现一个简单的双向双端链表与Link一样,假定其之 ... -
LinkedStack 栈
2008-04-05 17:45 1091LinkedStack栈属于ADT(抽象数据类型),其提供同样 ...
相关推荐
它是什么样的(平衡树,线性列表等)? 在哪里以及如何使用(应用程序)? 可以对其执行哪些操作(搜索,删除,添加,插入等)? 操作的理论复杂度是什么( O(log(n))搜索, O(n^2)插入等)? 有关该项目的其他...
2-3树是平衡搜索树的一种形式,类似于二叉树,其中某些节点具有2个密钥和3个子代,而不是仅1个密钥和2个子代。 为了实现,我们不是每个节点都有可变数量的键,而是创建一个红黑树:一个二进制树,其中的节点可以被...
2-3棵树是平衡的(所有叶顶距树根的高度都相同)。 在哪里以及如何使用(应用程序)? 操作:查找密钥,添加密钥,删除密钥,合并和拆分密钥。 理论操作的复杂性:在搜索O(log(n))插入O(log(n))删除在O(log(n)) ...
- [5-4 二叉搜索树](5.4_binarySearchTree.py) - [5-5 平衡二叉树](5.5_avlTree.py) - [5-6 红黑树](5.6_rbTree.py) - [5-7 trie](5.7_trie.py) - [5-8 双数组字典树](5.8_datree.py) - [5-9 哈夫曼树](5.9_huffman...
平衡二叉排序树的在平衡因子绝对值等于2时开始调整到绝对值为1或0,在平衡因子绝对值为2时,二叉排序树会出现四种不同的情况的树形,因此这时需要分别单独讨论来降低平衡因子。 1.2.7 平衡二叉树的调整方法 平衡...
//若因为插入而使得二叉排序树失去平衡,则做平衡旋转处理 //taller反映树是否长高 if(!T) { //插入新结点,树长高,taller为true T=new AvlNode; T->data=num; T->lchild=T->rchild=NULL; T->bf...
第15章 平衡搜索树 15.1 AVL树 15.1.1 定义 15.1.2 AVL树的高度 15.1.3 AVL树的描述 15.1.4 AVL搜索树的搜索 15.1.5 AVL搜索树的插入 15.1.6 AVL搜索树的删除 15.2 红-黑树 15.2.1 基本概念 15.2.2 红-黑树的描述 ...
第10章 2-3-4树和外部存储 2-3-4树的介绍 Tree234专题applet 2-3-4树的Java代码 2-3-4树和红-黑树 2-3-4树的效率 2-3树 外部存储 小结 问题 实验 编程作业 第11章 哈希表 哈希化简介 开放地址法 ...
第10章 2-3-4树和外部存储 2-3-4树的介绍 Tree234专题applet 2-3-4树的Java代码 2-3-4树和红-黑树 2-3-4树的效率 2-3树 外部存储 小结 问题 实验 编程作业 第11章 哈希表 哈希化简介 开放地址法 ...
节点ds JavaScript中常见的数据结构和基本算法实现目录链接栈树木二叉树二进制搜索树自平衡二叉搜索树AVL树替罪羊树红黑树B树B +树2-3棵2-3-4树堆二进制堆弱堆二项式堆斐波那契堆图形其他节点双节点BinaryTreeNode ...
问题:AVL树目的:了解平衡二叉搜索树的端到端知识,以及如何将其有效地用于解决各种问题。 任务:通过以下操作实现AVL树。 要实施的操作: Operations Complexity 1. Insertion O(log N) 2. Deletion O(log N) 3. ...
它是什么样的(平衡树,线性列表等)? 在哪里以及如何使用(应用程序)? 可以对其执行哪些操作(搜索,删除,添加,插入等)? 操作的理论复杂度是什么( O(log(n))搜索, O(n^2)插入等)? 有关该项目的其他...
数据结构是计算机科学中的一个重要概念,它指的是计算机中存储、...常见的树结构包括二叉树、平衡树(如AVL树)、红黑树等。 6. **图(Graph)**:用于表示物件之间的多对多关系。图由节点(或顶点)和边组成,边可以是
AVL实验室目的本实验的重点是自平衡二进制搜索树。背景在计算机科学中,AVL树是一种自平衡二进制搜索树,它是第一个发明的此类数据结构。 在AVL树中,任何节点的两个子树的高度最多相差一个。 在平均和最坏情况下,...
2-binary_tree_insert_right.c 插入一个节点作为另一个节点的右子节点 3-binary_tree_delete.c 删除整个二叉树 4-binary_tree_is_leaf.c 检查节点是否为叶子 5-binary_tree_is_root.c 检查给定节点是否为根 6-...
数据结构数据结构-C ++实现C ++模板实现常用数据结构,包括向量,链表,栈,数量,二叉树,二叉搜索树,平衡二叉树,优先权(堆),图,排序算法等。 《数据结构与算法实战》,课程可在该链接查看: : 。本仓库代码...
(2)在二叉平衡树上插入结点(ins_AVLtree) 和删除结点(del_AVLtree) (3)在 B-树上插入结点(Ins_BTree) 和 删除结点(Del_BTree) (4)在 B+树上插入结点(Ins_PBTree) 和 删除结点(Del_PBTree) 12. 内部排序 ...
(2)在二叉平衡树上插入结点(ins_AVLtree) 和删除结点(del_AVLtree) (3)在 B-树上插入结点(Ins_BTree) 和 删除结点(Del_BTree) (4)在 B+树上插入结点(Ins_PBTree) 和 删除结点(Del_PBTree) 12. 内部排序 ...
Tree BFS:面向水平的数学,水平关系 树 DFS : 一些准备方法 策略 1(掌握):一次一个主题。 即要使用链表,解决所有与链表相关的问题 策略 2(暴露):为问题设计一种方法,然后比较解决方案。 不熟悉时的代码...
(2)在二叉平衡树上插入结点(ins_AVLtree) 和删除结点(del_AVLtree) (3)在 B-树上插入结点(Ins_BTree) 和 删除结点(Del_BTree) (4)在 B+树上插入结点(Ins_PBTree) 和 删除结点(Del_PBTree) 12. 内部排序 ...