二叉排序树和平衡二叉树

二叉排序树又称二叉查找树或二叉搜索树。 它一棵空树或者是具有下列性质:

(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;

(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;

(3)左、右子树也分别为二叉排序树;

查找的时候总是从根节点进行比较然后逐级往下进行。

由于它是一种树形结构,所以相对于顺序存储结构来说,进行插入或者删除操作的时候效率较高,但是其查找性能是是不确定的(依赖于书的形状),例如如果每个节点都只有左孩子而没有右,则查找相当于从头找到尾,而如果每个节点的左右孩子深度差不多相等,则相当于二分查找。

鉴于上述原因,则需要在构造树的形状时尽量左右平衡,以提高查找效率,所以就出现了平衡二叉树(AVL树)

平衡二叉树或为空树,或为如下性质的二叉排序树:

(1)左右子树深度之差的绝对值不超过1;

(2)左右子树仍然为平衡二叉树.

平衡因子BF=左子树深度-右子树深度.

平衡二叉树每个结点的平衡因子只能是1,0,-1。若其绝对值超过1,则该二叉排序树就是不平衡的。

最小不平衡子树:距离插入结点最近,且平衡因子的绝对值大于1的结点为根的子树。

平衡二叉树的构造思想:

构建的过程中,每插入一个结点,先检查是否因为插入而破坏了树的平衡性,若是,则找出最小不平衡子树。在保持二叉排序树的前提下,调整最小不平衡子树中各个结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。

程序的具体实现方法可以参见《大话数据结构》一书

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题39二叉树的深度

题目:输入一颗二叉树的根结点,求该树的深度。从根结点到叶结点一次经过的结点形成树的一条路径,最长路径的长度为树的深度。 分析:本题是一道典型的“分治法”。要...

33350
来自专栏xingoo, 一个梦想做发明家的程序员

二叉排序树的删除操作

算法思想 二叉排序树,删除操作主要针对三种情况。 1 叶子节点-直接删除就可以了 2 没有左孩子的节点-直接嫁接右子树就可以了(没有右孩子的节点-直接嫁接左子树...

27680
来自专栏程序生活

二叉树的深度

题目描述 输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 代码实现 递归实现 # ...

27340
来自专栏灯塔大数据

每周学点大数据 | No.24二叉搜索树回顾(一)

No.24期 二叉搜索树回顾(一) Mr. 王:接下来我们谈一谈外存查找结构。内存中的查找结构最典型的就是二查搜索树了。这里我们先来简单地认识一下关于二叉树...

36850
来自专栏WD学习记录

哈夫曼树(Huffman Tree)

给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带...

25040
来自专栏青玉伏案

算法与数据结构(十一) 平衡二叉树(AVL树)(Swift版)

今天的博客是在上一篇博客的基础上进行的延伸。上一篇博客我们主要聊了二叉排序树,详情请戳《二叉排序树的查找、插入与删除》。本篇博客我们就在二叉排序树的基础上来聊聊...

28270
来自专栏编程理解

数据结构(六):红黑树

级别的查询、插入和删除节点复杂度。相对于 AVL 树单纯的对每个节点的平衡因子进行判断,红黑树给节点赋予了颜色属性,并通过对树中节点的颜色进行限制,来保持整棵...

23120
来自专栏向治洪

ArrayList和LinkedList的区别

一般大家都知道ArrayList和LinkedList的大致区别: 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构...

21190
来自专栏xcywt

《大话数据结构》树以及赫夫曼编码的例子

第六章 树 6.2 树的定义 树(Tree)的n个结点的有限集。当n=0时,称为空树。 任意一个非空树中: 1)有且仅有一个特定的称为根(root)的结点 2)...

46460
来自专栏kevindroid

leetcode110 Balanced Binary Tree

16150

扫码关注云+社区

领取腾讯云代金券