BaldIsImpossible的博客

八大数据结构——红黑树（七）

BaldIsImpossible — Fri, 12 Mar 2021 09:50:22 +0800

八大数据结构——红黑树（七）目录八大数据结构——红黑树（七）二叉搜索树2-4树红黑树的定义和插入红黑树的删除红黑树演示网站红黑树与AVL树面试中关于红黑树代码实现树是数据结构中非常重要的一项，有关树的数据结构有许多种，本文重点研究的是红黑树。关于红黑树，是二叉树范畴里的高级数据结构，内容十分的多，网上各种文章参差不齐，经过我的血泪史，读者可以通过以下文章，完整的了解红黑树，并且最后附上Java实现代码。二叉搜索树红黑树是建立在二叉搜索树基础上的，如果您还不了解，请看八大数据结构——二叉搜索树（七

八大数据结构——哈夫曼树（七）

BaldIsImpossible — Tue, 09 Mar 2021 15:03:36 +0800

八大数据结构——哈夫曼树（七）目录八大数据结构——哈夫曼树（七）基础定义哈夫曼树的构造哈夫曼树编码哈夫曼树解码代码实现完整代码树是数据结构中非常重要的一项，有关树的数据结构有许多种，本文重点研究的是哈夫曼树（最优二叉树）。基础定义路径：对于一棵子树中的任意两个不同的结点，如果从一个结点出发，按层次自上而下沿着一个个树枝能到达另一结点，称它们之间存在着一条路径。可用路径所经过的结点序列表示路径，路径的长度等于路径上的结点个数减1。权重：无论是节点还是路径都可以带有一个权重，通常可以是一个数值。这

八大数据结构——平衡二叉树（七）

BaldIsImpossible — Sun, 07 Mar 2021 15:58:49 +0800

八大数据结构——平衡二叉树（七）目录八大数据结构——平衡二叉树（七）二叉树的旋转Java代码实现完整代码树是数据结构中非常重要的一项，有关树的数据结构有许多种，本文重点研究的是平衡二叉树，并且在二叉搜索树的基础上写的，如果不了解二叉搜索树，请移步二叉搜索树。平衡二叉树定义：在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。特点： 1.本身首先是一棵二叉搜索树。 2.带有平衡条件：每个结点的左右子树的高度之差的绝

树的前序，中序，后序遍历。

BaldIsImpossible — Sat, 06 Mar 2021 21:42:45 +0800

目录定义与解释递归代码实现非递归代码实现定义与解释前序遍历：前序遍历（VLR）， [1] 是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。中序遍历：中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。后序遍历：后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉

八大数据结构——二叉搜索树（七）

BaldIsImpossible — Sat, 06 Mar 2021 20:00:32 +0800

八大数据结构——二叉搜索树（七）目录八大数据结构——二叉搜索树（七）Java代码实现完整代码树是数据结构中非常重要的一项，有关树的数据结构有许多种，本文重点研究的是二叉搜索树。二叉搜索树定义：二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。树结构，顾名

八大数据结构——队列（六）

BaldIsImpossible — Wed, 03 Mar 2021 09:13:54 +0800

八大数据结构——队列（六）目录八大数据结构——队列（六）java代码实现完整代码常用的主要有八大类型：1.数组（Array）2.栈（Stack）3.链表（Linked List）4.图（Graph）5.散列表（哈希表）（Hash）6.队列（Queue）7.树（Tree）8.堆（Heap）。队列定义（百度解释）：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行

八大数据结构——栈（二）

BaldIsImpossible — Wed, 03 Mar 2021 09:12:01 +0800

八大数据结构——栈（二）目录八大数据结构——栈（二）java代码实现完整代码常用的主要有八大类型：1.数组（Array）2.栈（Stack）3.链表（Linked List）4.图（Graph）5.散列表（哈希表）（Hash）6.队列（Queue）7.树（Tree）8.堆（Heap）。 **栈定义（百度解释）： ** 栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。可以把栈理解为一个箱子，四周都是封上的，只有

八大数据结构——哈希表（五）

BaldIsImpossible — Sat, 27 Feb 2021 14:16:50 +0800

import java.util.Enumeration; import java.util.NoSuchElementException; //哈希表，基于“开放链地址法”的冲突解决方法 public class HashTable { // 定义存储容器,表长如果改变，原来的哈希算法也要调整，情况复杂，这里不予考虑，所以表长初始化就不给改变。 private HashNode[] array; // 记录已存储元素个数

八大排序算法——基数排序（八）

BaldIsImpossible — Thu, 25 Feb 2021 20:40:25 +0800

//基数排序 public class RadixSort { public void radixSort(int[] data, int left, int right) { if (left < 0 || right > data.length - 1 || left >= right) { return; } int maxDigit = getMaxDigit(data); int mo

八大排序算法——归并排序（七）

BaldIsImpossible — Thu, 25 Feb 2021 19:36:25 +0800

//归并排序 public class MergeSort { // 不借助辅助数组实现 public void mergeSort(int[] data, int left, int right) { if (left < 0 || right > data.length - 1 || left >= right) { return; } int mid = (right - left) / 2

八大排序算法——快速排序（六）

BaldIsImpossible — Thu, 25 Feb 2021 19:35:16 +0800

//快速排序(随机选取基准），基于最左基准点的实现 public class QuickSort { private int quickSort(int[] data, int left, int right) { if (left < 0 || right > data.length - 1 || left >= right) { return -1; } int index = left;//设置左边的为基

八大排序算法——冒泡排序（五）

BaldIsImpossible — Thu, 25 Feb 2021 19:33:54 +0800

//冒泡排序 public class BubbleSort { public void bubbleSort(int[] data, int left, int right) { if (left < 0 || right > data.length - 1 || left >= right) { return; } int count = 0;//记录已完成的轮数，n个数排序，需要n-1轮

八大排序算法——堆排序（四）

BaldIsImpossible — Thu, 25 Feb 2021 19:32:53 +0800

//堆排序 //堆排序其实就是构建一个大顶堆或小顶堆，这和堆的实现差不多 public class HeapSort { // 升序排列就构建一个大顶堆，每次取堆顶元素放到末尾。 // 降序排列就构建一个小顶堆，每次取堆顶元素放到末尾。 public void maxHeapSort(int[] data, int left, int right) { if (left < 0 || right > data.length - 1 || lef

八大排序算法——直接选择排序（三）

BaldIsImpossible — Thu, 25 Feb 2021 19:31:42 +0800

//直接排序 public class StraightSelectSort { public void straightSelectSort(int[] data, int left, int right) { if (left < 0 || right > data.length - 1 || left >= right) { return; } int index = 0;//记录元素下标 //

八大排序算法——希尔排序（二）

BaldIsImpossible — Thu, 25 Feb 2021 19:30:19 +0800

//希尔排序 public class ShellSort { public void shellSort(int[] data, int left, int right) { if (left < 0 || right > data.length - 1 || left >= right) { return; } int gap, i, j, temp; // 用gap不断进行分

八大排序算法——直接插入排序（一）

BaldIsImpossible — Thu, 25 Feb 2021 19:29:02 +0800

//直接插入排序 // 这里使用记录索引，并移箱子的形式进行。 public class StraightInsertionSort { public void straightInsertionSort(int[] data, int left, int right) { if (left < 0 || right > data.length - 1 || left >= right) { return; }

八大数据结构——堆（八）

BaldIsImpossible — Tue, 23 Feb 2021 16:40:06 +0800

import java.util.NoSuchElementException; //实现一个最大堆 public class MaxHeap { private Type[] elements;//存储数据单元 private int size;//当前指针位置 private static final int Default_size = 10;//默认大小 public MaxHeap() { elements = (Type

七大查找算法——分块查找（五）

BaldIsImpossible — Tue, 23 Feb 2021 14:11:28 +0800

//分块查找 //O(log2n)~O(n)，块内无序，块与块有序。 //分块查找又称索引顺序查找，它是顺序查找的一种改进方法。 // 　　算法思想：将n个数据元素"按块有序"划分为m块（m ≤ // n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2 // 块中任一元素又都必须小于第3块中的任一元素，…… // 　　算法流程： // 　　step1 先选取各块

七大查找算法——斐波那契查找（四）

BaldIsImpossible — Tue, 23 Feb 2021 14:10:38 +0800

//斐波那契查找 //该查找mid = left + f[k-1] - 1;不涉及除法，如果该数列长度正好等于一个斐波那契数-1，那么理论情况要比有除法的二分查找法快。 //同样要求有序数列，也是对二分查找的一种改进，用黄金分割来拆分。复杂度分析：最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。 //黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1 // .618:1。 //斐

七大查找算法——插值查找（三）

BaldIsImpossible — Tue, 23 Feb 2021 14:09:33 +0800

//插值查找 //基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。 // 　　注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。 // 反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。 // 　　复杂度分析：查找成功或者失败的时间复杂度均为O(log2(log2n))。 public class InterpolationSearch {