Contents
  1. 1. 引言
    1. 1.1. 树的字段
  2. 2. AVL树的“增”
  3. 3. 引用

本篇博客主要基于这篇博客的扩展,建议阅读前先阅读这篇博文,这篇博文详细介绍AVL树的实现原理,完整代码在githubavl.go文件中

浅谈”树”这种数据结构
Github
可视化页面

引言

AVL树是在对二叉搜索树的一种优化,通过构造一棵高度平衡的二叉搜索树从而实现提高空间利用率,所以在了解如何实现之前,必须了解如何构造一棵二叉搜索树,你可以阅读我的这篇博客了解如何构建一棵二叉搜索树,虽然我是用Go来实现的,但是不必了解太多Go方面的知识,我在博客中尽量使用图片的方式来介绍实现原理

二叉搜索树实现原理

由于AVL树本质上也是一棵二叉搜索树,查找并不会改变树的性质,所以AVL的查找也是同二叉搜索树的查询相同,所以这里就重点介绍如何实现“增”和“删”

树的字段

在开始介绍如何实现“增”、“删”之前,我想提一下AVL树的存贮字段,在wiki上面的AVL和很多资料上面,AVL的树结构分别由下面四个组成: Val、 Left*、Right*、Parent*。

Val代表树存贮的值,Left、Right、Parent代表三个指针,分别指向左子树,右子树,父亲,而在我的实现中,我去掉了父亲指针,对于讲解来说,使用一个父指针能很好的解决从子遍历到父亲的经过,但在实际的应用中,我们完全可以使用一个列表存贮从父亲到儿子之间的值,这样的话,能实现一样的功能,而且能节省存贮空间(每个子树都少了一个父指针),但是相应的程序也变得比较复杂起来。

虽然我在讲解的过程中会直接获取节点的父节点,但是在实际的代码实现中,是通过获取从列表中获取该节点的父节点。

AVL树的“增”

引用

https://en.wikipedia.org/wiki/AVL_tree

Contents
  1. 1. 引言
    1. 1.1. 树的字段
  2. 2. AVL树的“增”
  3. 3. 引用