ACM国家集训队论文集8资源-CSDN文库

共17个文件

ppt：10个

doc：6个

pdf：1个

ACM国家集训队论文集8

需积分: 5 18 浏览量 2010-05-19 12:20:48 上传评论收藏 2.41MB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

国家集训队论文集8.rar （17个子文件）

国家集训队2007论文集

day1

5.杨沐《浅析信息学中的“分”与“合”》.doc 446KB

1.高逸涵《与圆有关的离散化方法》.doc 127KB

1.高逸涵《与圆有关的离散化方法》.ppt 211KB

3.仇荣琦《欧拉回路性质与应用探究》.doc 725KB

10.陈启峰《Size Balanced Tree》.ppt 687KB

7.袁昕颢《动态树问题及其应用》.ppt 1015KB

2.王晓珂《解析一类组合游戏》.doc 1.72MB

6.李宇骞《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》.ppt 608KB

4.余江伟《如何解决好动态统计问题》.ppt 475KB

9.王欣上《浅谈基于分层思想的网络流算法》.ppt 399KB

10.陈启峰《Size Balanced Tree》.pdf 225KB

2.王晓珂《解析一类组合游戏》.ppt 296KB

5.杨沐《浅析信息学中的“分”与“合”》.ppt 535KB

9.王欣上《浅谈基于分层思想的网络流算法》.doc 302KB

3.仇荣琦《欧拉回路性质与应用探究》.ppt 340KB

6.李宇骞《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》.doc 210KB

8.杨哲《凸完全单调性的一个加强与应用》.ppt 397KB

Size Balanced Tree

Chen Qifeng (Farmer John)

Zhongshan Memorial Middle School, Guangdong, China

Email:344368722@QQ.com

December 29, 2006

Abstract

This paper presents a unique strategy for maintaining balance in

dynamically changing Binary Search Trees that has optimal expected behavior at

worst. Size Balanced Tree is, as the name suggests, a Binary Search Tree (abbr.

BST) kept balanced by size. It is simple, efficient and versatile in every aspect. It

is very easy to implement and has a straightforward description and a

surprisingly simple proof of correctness and runtime. Its runtime matches that of

the fastest BST known so far. Furthermore, it works much faster than many

other famous BSTs due to the tendency of a perfect BST in practice. It supports

not only typical primary operations but also Select and Rank.

Key Words And Phrases

Size Balanced Tree

SBT

Maintain

This paper is dedicated to the memory of Heavens.

1 Introduction

Before presenting Size Balanced Trees it is necessary to explicate Binary Search

Trees and rotations on BSTs, Left-Rotate and Right-Rotate.

1.1 Binary Search Tree

Binary Search Tree is a significant kind of advanced data structures. It supports

many dynamic-set operations, including Search, Minimum, Maximum, Predecessor,

Successor, Insert and Delete. It can be used both as a dictionary and as a priority

queue.

A BST is an organized binary tree. Every node in a BST contains two children at

most. The keys for compare in a BST are always stored in such a way as to satisfy the

binary-search-tree property:

Let x be a node in a binary search tree. Then the key of x is not less than

that in left subtree and not larger than that in right subtree.

For every node t we use the fields of left[t] and right[t] to store two pointers to its

children. And we define key[t] to mean the value of the node t for compare. In

addition we add s[t], the size of subtree rooted at t, to keep the number of the nodes in

that tree. Particularly we call 0 the pointer to an empty tree and s[0]=0.

1.2 Rotations

In order to keep a BST balanced (not degenerated to be a chain) we usually

change the pointer structure through rotations to change the configuration, which is a

local operation in a search tree that preserves the binary-search-tree property.

Figure1.1: The operation Left-Rotate(x) transforms the configuration of the two

nodes on the right into the configuration on the left by changing a

constant number of pointers. The configuration on the left can be

transformed into the configuration on the right by the inverse

operation, Right-Rotate(y).

1.2.1 Pseudocode Of Right-Rotate

The Right-Rotate assumes that the left child exists.

Right-Rotate (t)

1 k←left[t]

2 left[t] ←right[k]

3 right[k] ←t

4 s[k] ←s[t]

5 s[t] ←s[left[t]]+s[right[t]]+1

6 t←k

1.2.2 Pseudocode Of Left-Rotate

The Left-Rotate assumes that the right child exists.

Left-Rotate (t)

1 k←right[t]

2 right[t] ←left[k]

3 left[k] ←t

4 s[k] ←s[t]

5 s[t] ←s[left[t]]+s[right[t]]+1

6 t←k

2 Size Balanced Tree

Size Balanced Tree (abbr. SBT) is a kind of Binary Search Trees kept balanced

by size. It supports many dynamic primary operations in the runtime of O(logn):

Insert(t,v) Inserts a node whose key is v into the SBT rooted at t.

Delete(t,v) Deletes a node whose key is v from the SBT rooted at t. In the case

that no such a node in the tree, deletes the node searched at last.

Find(t,v) Finds the node whose key is v and returns it.

Rank(t,v) Returns the rank of v in the tree rooted at t. In another word, it is one

plus the number of the keys which are less than v in that tree.

Select(t,k) Returns the node which is ranked at the kth position. Apparently it

includes operations of Get-max and Get-min because Get-min is

equivalent to Select(t,1) and Get-max is equivalent to Select(t,s[t])

Pred(t,v) Returns the node with maximum key which is less than v.

Succ(t,v) Returns the node with minimum key which is larger than v.

Commonly every node of a SBT contains key, left, right and extra but useful

updated field: its size, which has been defined in the former introduction. The kernel

of a SBT is divided into two restrictions on size:

For every node pointed by t in a SBT, we guarantee that

Property(a):

]]][[[]]],[[[]][[ tleftrightstleftleftstrights ≥

Property(b):

]]][[[]]],[[[]][[ trightleftstrightrightstlefts ≥

Figure 2.1:The nodes L and R are left and right children of the

node T. The Subtrees A and B, C and D are left and

right subtrees of the nodes L and R respectively.

Correspond to properties (a) and (b),

][][],[&][][],[ LsDsCsRsBsAs ≤

≤

3 Maintain

Assume that we need to insert a node whose key is v into a BST. Generally we

use the following procedure to accomplish the mission.

Simple-Insert (t,v)

1 If t=0 then

2 t←NEW-NODE(v)

3 Else

4 s[t] ←s[t]+1

5 If v<key[t] then

6 Simple-Insert(left[t],v)

7 Else

8 Simple-Insert(right[t],v)

After the execution of Simple-Insert properties (a) and (b) are probably not

satisfied. In that case we need to maintain the SBT.

The vital operation on a SBT is a unique procedure, Maintain. Maintain(t) is

used to maintain the SBT rooted at t. The hypothesis that the subtrees of t are SBT is

applied before the performance.

Since properties (a) and (b) are symmetrical we only discuss the case that

restriction (a) is violated in detail.

Case 1: s[left[left[t]]>s[right[t]]

In this case that s[A]>s[R] correspond to Figure 2.1 after Insert(left[t],v), we can

execute the following instructions to repair the SBT:

(1) First perform Right-Rotate(T). This operation transforms Figure 2.1 into Figure

3.1;

Figure 3.1: All the nodes are defined the same as in Figure 2.1.

(2) And then sometimes it occurs that the tree is still not a SBT because s[C]>s[B]

or s[D]>s[B] by any possibility. So it is necessary to implement Maintain(T).

(3) In succession the configuration of the right subtree of the node L might be

changed. Because of the possibility of violating the properties it is needful to

run Maintain(L) again.

Case 2: s[right[left[t]]>s[right[t]]

In this case that s[B]>s[R] correspond to Figure 3.2 after Insert(left[t],v), the

maintaining is kind of complicated than that in case 1. We can carry out the following

operations for repair.

评论收藏

内容反馈

Sunday

粉丝: 634
资源: 41

ACM国家集训队论文集8

ACM国家集训队论文集（第二卷）

ACM国家集训队论文合集

ACM国家集训队论文集（第一卷）

ACM国家集训队论文集（第三卷）

ACM国家集训队2006论文集

ACM国家集训队论文集

2007年 ACM国家集训队论文集

2006年 ACM国家集训队论文集

acm国家集训队2008年论文合集

ACM国家集训队2013论文集

ACM国家集训队2002论文集

ACM国家集训队2009论文集

ACM国家集训队论文集1

acm国家集训队2007年论文合集

acm国家集训队2006年论文合集

acm 国家集训队2004论文集_周源 poj

ACM国家集训队2008论文集

ACM国家集训队1999论文集

ACM国家集训队2007论文集

ACM国家集训队2005论文集

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

NPPJSONViewer.zip

GD32替换STM32注意事项.pdf

XCP协议的规范文档

VS2015安装证书，JavaScript_ProjectSystem.msi，JavaScript_LanguageService.msi

CANoe通过CAPL脚本实现自动测试

蓝牙BLE协议中文版.pdf

最新资源

Qt 5实现串口调试助手（源工程文件、0积分下载）