在二叉搜索树(BST)的基础上,要实现一颗平衡树,可以使用2-3树的方式,2-3树的直接实现,相对比较复杂
,因此算法的研究者们提出了红-黑树的实现方式。
package com.test; public class RedBlackTree<Key extends Comparable<Key>, Value> { private static final boolean RED = true; private static final boolean BLACK = false; private Node root; private class Node { private Key key; private Value value; private boolean color; private Node left, right; public Node(Key key, Value value, boolean color) { super(); this.key = key; this.value = value; this.color = color; } } private boolean isRed(Node x) { if (x == null) return false; return x.color == RED; } private Node rotateLeft(Node h) { Node x = h.right; h.right = x.left; x.left = h; x.color = h.color; h.color = RED; return x; } private Node rotateRight(Node h) { Node x = h.left; h.left = x.right; x.right = h; x.color = h.color; h.color = RED; return x; } private void flipColors(Node h) { h.color = RED; h.left.color = BLACK; h.right.color = BLACK; } public void put(Key key, Value val) { root = put(root, key, val); } private Node put(Node h, Key key, Value val) { if (h == null) { return new Node(key, val, RED); } int cmp = key.compareTo(h.key); if (cmp < 0) { h.left = put(h.left, key, val); } else if (cmp > 0) { h.right = put(h.right, key, val); } else { h.value = val; } if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); if (isRed(h.left) && isRed(h.right)) flipColors(h); return h; } public Value get(Key key) { Node x = root; while (x != null) { int cmp = key.compareTo(x.key); if (cmp < 0) { x = x.left; } else if (cmp > 0) { x = x.right; } else { return x.value; } } return null; } }
相关推荐
AVL二叉平衡树删除--标准版AVL二叉平衡树删除--标准版AVL二叉平衡树删除--标准版AVL二叉平衡树删除--标准版
按照红黑平衡树的原理,实现的一个二叉树,key value的模板类,实现了数据的添加和快速的查找等功能
权重平衡树实现, 加权平衡树(WBTs)是一种可以用来实现集合、字典(映射)和序列的平衡树。这些树结构在20世纪70年代被Nievergelt和Reingold作为有界限的自平衡树或BB[α]树提出。让这些结构普及的是高德纳。 就像...
史上最简单的平衡树——无旋Treap.pdf
若干平衡树的C语言实现,支持插入删除,数查排名,排名查数,查询前驱后继
C语言 二叉平衡树实现学生管理系统,用文件保存学生信息,可以实现学生信息的显示、查找、插入、删除、保存等。
平衡二叉树-红黑树的实现
首先实现BST二叉搜索树,在BST的基础上做出AVL树,有插入、删除、查询、调整平衡的功能,而且可以和BST比较的过程。By Michael Zhou
用C++实现的平衡树的插入和删除操作,查询操作没实现。测试数据量比较大,可以根据需要在insert和remove方法里面修改打印的东西
fruit --treep平衡树 Treap=Tree+Heap。Treap本身是一棵二叉搜索树,它的左子树和右子树也分别是一个Treap,和一般的二叉搜索树不同的是,Treap纪录一个额外的数据,就是优先级。Treap在以关键码构成二叉搜索树的...
使用C++实现BST,可以进行插入,删除节点等操作
实现了红黑树、AVL树的基本功能增删改查。学习交流,共同进步
平衡树的c++实现,有添加元素和删除元素功能,可以在增加或删除元素过程中保持平衡树
实现二叉平衡树的相关运算算法。并在此基础上完成如下功能:1、由{4,9,0,1,8,6,3,5,2,7}创建一颗AVL树b并以括号表示输出。2、在b中分别删除关键字为8和2 的结点,并以括号表示法输出删除后的AVL树
红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。
严蔚敏数据结构中二叉平衡树的实现,教材中的有点小bug
平衡树treap的思想
求平衡树的算法的c语言实现,带测试用例,适合算法学习用来做参考使用
1 引入k-d树的目的 2 K-d树的定义 3 K-d树的基本操作:构造 插入 删除 查询 4 K-d树的应用
一个关于红黑平衡树的代码C++的